4
$\begingroup$

The following code produces lists of sublists with maximum length 5 that shuffle zeros around an ordered list (here {1,2}). It produces all permutations while keeping the ordering of the list {1,2} within the permutations:

mylst[K_]:=Select[Drop[Tuples[{0,1,2},K],1],Total[#]==3&&Count[#,1]==1&&#[[Position[#,x_/;!TrueQ[x==0],{1},1,Heads->False][[1,1]]]]!=2&]
mylst /@ Range[5]

Each of mylst[K] generates $K(K-1)/2$ terms.

Is there a better way to code mylst?

$\endgroup$
7
$\begingroup$

Just for fun, here is the pattern based version

mylst2[K_] := ReplaceList[
  ConstantArray[0, K],
  {a___, x_, b___, y_, c___} :> {a, 1, b, 2, c}
  ]
$\endgroup$
  • $\begingroup$ Thanks for the simplified version! Seems really compact way to do the same task! $\endgroup$ – Chen Stats Yu Jan 9 '15 at 13:26
  • 1
    $\begingroup$ @ChenStatsYu Surprising! Rule based solutions often have poor complexity, I guess in this case it works... $\endgroup$ – C. E. Jan 9 '15 at 13:38
  • 1
    $\begingroup$ mylst2[200]; // AbsoluteTiming (yours) VS mylst3[200]; // AbsoluteTiming (Carlo's), it's about {0.078000, Null} VS {0.780001, Null}. Nearly 10 times. $\endgroup$ – Chen Stats Yu Jan 9 '15 at 13:46
  • 1
    $\begingroup$ No, I think your solution is better Pickett. I forfeit! $\endgroup$ – Carlo Jan 9 '15 at 13:55
  • 1
    $\begingroup$ @ChenStatsYu It isn't. $\endgroup$ – C. E. Jan 9 '15 at 16:12
5
$\begingroup$
mylst2[K_] := Map[
    ReplacePart[#, FirstPosition[#, 2] -> 1] &,
    Permutations[PadRight[{2, 2}, K]]
]

This might not be what you want for K == 0. But it has much better complexity (quadratic vs exponential).

$\endgroup$
  • $\begingroup$ That will do! I dont really use the case $K=0$. $\endgroup$ – Chen Stats Yu Jan 9 '15 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.