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$

2 Answers 2

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$
10
  • $\begingroup$ Thanks for the simplified version! Seems really compact way to do the same task! $\endgroup$ Commented Jan 9, 2015 at 13:26
  • 1
    $\begingroup$ @ChenStatsYu Surprising! Rule based solutions often have poor complexity, I guess in this case it works... $\endgroup$
    – C. E.
    Commented Jan 9, 2015 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$ Commented Jan 9, 2015 at 13:46
  • 1
    $\begingroup$ No, I think your solution is better Pickett. I forfeit! $\endgroup$
    – Carlo
    Commented Jan 9, 2015 at 13:55
  • 1
    $\begingroup$ @ChenStatsYu It isn't. $\endgroup$
    – C. E.
    Commented Jan 9, 2015 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$
1
  • $\begingroup$ That will do! I dont really use the case $K=0$. $\endgroup$ Commented Jan 9, 2015 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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