3
$\begingroup$

What is an efficient way to create a list of (psudo)randomly chosen permutations?

I'm trying to create a list like below:

x = 5;
RandomChoice[Permutations[Range[1, x]], {x}]

{{1, 2, 4, 5, 3}, {5, 3, 1, 2, 4}, {5, 2, 3, 1, 4}, {1, 3, 2, 4, 5}, {3, 2, 4, 5, 1}}

However, this eats up a lot of memory and doesn't work after x=11.

Each sub-list does not necessarily have to be unique, but in this case it was.

$\endgroup$
0
5
$\begingroup$

As far as I can tell from the problem description you can simply shuffle the list as many times as needed, since duplicate permutations are allowed:

(* thanks ybeltukov for tweaks *)
f[n_, m_] := Table[RandomSample @ #, {m}] & @ Range @ n

Example:

f[5, 3]
{{5, 3, 1, 4, 2}, {3, 4, 2, 5, 1}, {2, 1, 5, 3, 4}}
$\endgroup$
1
  • 1
    $\begingroup$ Even more efficient f3[n_, m_] := Table[RandomSample@#, {m}] &@Range@n :) $\endgroup$ – ybeltukov Sep 12 '14 at 11:00
4
$\begingroup$

mrandomperms[n_, m_]:= Table[PermutationList[RandomPermutation[n]], {m}]

Was my initial answer, but, as pointed out by Mr. Wizard, PermutationList should be given $n$ as a second argument, since otherwise it will give the wrong answer if $n$ is a fixed point. Also, Table can be eliminated for elegance and efficiency, leaving one with:

mrandomperms[n_, m_]:= PermutationList[#, n]& /@ RandomPermutation[n, m]

$\endgroup$
1
  • $\begingroup$ @Mr.Wizard Re second, true. Re first, PermutationList seems to work fine for me without the second arg (I checked before posting the answer), but now that I read the documentation I see that it is not guaranteed to work if the last element is a fixed point, so you are right. $\endgroup$ – Igor Rivin Sep 12 '14 at 2:53

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.