5

From the Python documentation for random.shuffle, which takes a list and randomizes the order if its elements:

Note that for even rather small len(x), the total number of permutations of x is larger than the period of most random number generators; this implies that most permutations of a long sequence can never be generated.

Is this true of any language, since the limitation seems dependent on the random number generator? Is it possible to write a function that can generate any possible permutation of an arbitrarily long list?

Colin
  • 10,447
  • 11
  • 46
  • 54
  • I assume you mean "feasible" not "possible". – Joel Cornett May 19 '12 at 02:52
  • I did mean feasible, but now I'm curious if it's not feasible, but is possible, what kind of insanity are we talking about? – Colin May 19 '12 at 02:58
  • 4
    See http://stackoverflow.com/questions/3062741/maximal-length-of-list-to-shuffle-with-python-random-shuffle and http://mail.python.org/pipermail/python-dev/2006-June/065815.html (follow the thread, it's a real, if not too serious, problem). – TryPyPy May 19 '12 at 02:58
  • 1
    @TryPyPy that python-dev thread ends with Tim Peters claiming to have removed the note, and refusing to put it back - but it is still there, per the OP's link, and is also in the current dev version's documentation. Is there a rest of this story? – lvc May 19 '12 at 03:38
  • 1
    Ah, found it: http://mail.python.org/pipermail/python-ideas/2009-March/003671.html – lvc May 19 '12 at 03:51

2 Answers2

5

See http://mail.python.org/pipermail/python-ideas/2009-March/003670.html . The exact length that it starts being a problem at is dependent on the PRNG, but the basic problem will always apply.

The previous question that @TryPyPy linked to is also focused on Python, but the accepted answer explains quite well why it will always happen. To paraphrase, you can imagine a naive shuffle algorithm working this way:

  1. Generate a list, p, of all possible permutations of the input
  2. Get a random number, x, from your PRNG
  3. The shuffled list is p[x]

If p is longer than the list of all possible xs that the PRNG can produce, some of the permutations are unreachable.

Since fancy shuffle algorithms are, at their core, a way of doing this without having to generate every possible permutation before discarding all but one of them, the only way around this is to have a source of true randomness.

lvc
  • 34,233
  • 10
  • 73
  • 98
2

Yes, it is possible. You can write a permutation generator that uses random.SystemRandom for all of your decisions.

The downside of this is that your program may have to halt for an arbitrarily long time while your operating system collects more entropy for you to use.

btilly
  • 43,296
  • 3
  • 59
  • 88