Chaotic permutations

Question

Is there any alorithm, which provides a chaotic permutation of a given list in a reasonable time? Im using Python, but I am concerned, that the given shuffle function will not provide a good solution, due a length of 1.1 Millions elements in the given list.

I did some googling and did not find any usefull results, would be really surprised if there is anything like this, but I would really appreciate an answer

How much time is "reasonable"? How much time did `shuffle` take when you tried it? — rici, Apr 16 '17 at 00:13
It took longer then 10 minutes,then I cancelled. This is way too long. I need to do this around 1000 times, it would be okay, if this would take around multiple hours. A runtime of 30 seconds for one permutation would be good enough, but more would be way too much — Illidor, Apr 16 '17 at 00:29
In that case, you need to provide more information. On my not-so-powerful laptop, `time python -c 'from random import shuffle'$'\n''a=list(range(1100000));shuffle(a)` took 0.6 seconds. (It takes slightly longer if I make `a` a list of lists, but not much longer.) — rici, Apr 16 '17 at 00:35
Im sorry, thats my bad, the long time was due to an attempt to print the shuffled list, which takes obviously way more time then shuffling the list. But I am still concerned, that the created permutations are not "safe" in this way, that ,like in the documentation stated, not every permutation can occure, due to the len(list)!, which is bigger then the period of the standard random generator, which is 2**19937-1, but the workaround would be, to create a random function with a bigger period then 1.1 million!, but I don't think this is possible, or? — Illidor, Apr 16 '17 at 00:49
It's true that it is not possible to get every possible shuffle. But so what? The number of possible shuffles you can get is larger than the number of atoms in the known universe. It is not so large as 1,100,000 factorial, but nothing is, so there's no point worrying about it. (Also worth nothing that 2**19937-1 is a lot bigger than 1.1 million :) ) — rici, Apr 16 '17 at 00:52
Yeah, I will probably go along with this, thank you for your help, kind stranger! — Illidor, Apr 16 '17 at 00:54

score 1 · Accepted Answer · answered Apr 16 '17 at 00:54

1

Use shuffle. It is fast enough and adequately chaotic for any practical purpose.

answered Apr 16 '17 at 00:54

rici

234,347
28
237
341

score 1 · Answer 2 · edited May 23 '17 at 12:02

Just wanted to address the ways of generating a shuffle in such a way that all combinations are possible. As you noted pseudo-random number generators are limited by the number of combinations you can create out of them. To create true shuffle you need true RNG.

Step 1: Use an online RNG to get enough random numbers to satisfy the entropy requirements (i.e. retrieve log(n!)/wordsize number of RNs). See https://softwareengineering.stackexchange.com/questions/76822/i-need-a-true-random-number-generator-web-service for more details

Step 2: Once you have a long enough RN, say k, the problem then becomes creating kth permutation. Search internet and you will find plenty of solutions. Eg. Given n and k, return the kth permutation sequence

Chaotic permutations

2 Answers2