python permutations with more randomization

Question

I'm trying to generate permutation from a list of indices, currently, I am using itertools.permutation. It's okay, except I need a really random nature of the indices as I will not be able to select all the permutations, but a very short subset of the total set (initial ones) for simulation.

For itertools.permutation: The permutation tuples are emitted in lexicographic ordering according to the order of the input iterable. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

import itertools
for ind, idxs in enumerate(itertools.permutations(range(5))):
  print(ind)
  print(idxs)
  print('--------')

0
(0, 1, 2, 3, 4)
--------
1
(0, 1, 2, 4, 3)
--------
2
(0, 1, 3, 2, 4)
--------
3
(0, 1, 3, 4, 2)
--------
4
(0, 1, 4, 2, 3)
--------
5
(0, 1, 4, 3, 2)
--------
6
(0, 2, 1, 3, 4)
--------
7
(0, 2, 1, 4, 3)
--------
8
(0, 2, 3, 1, 4)
--------
9
(0, 2, 3, 4, 1)
--------
10
(0, 2, 4, 1, 3)
--------
11
(0, 2, 4, 3, 1)
--------
12
(0, 3, 1, 2, 4)
--------
13
(0, 3, 1, 4, 2)
--------

One solution definitely comes to my mind is to shuffle the list each time to get a random order, but that makes the idea of permutation obsolete, which is not desired as there is a chance that the same sample will be generated more than once. The permutation should be generated iteratively, so I can not just do list(itertools.permutation..) as this will make a really unnecessary long list.

Check this out https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list — Sup, Aug 16 '21 at 15:51
This problem is one of the most complex tasks for computation. Remember `n!` has the highest order of growth. I hope you need this task only for a small problem size. — Sup, Aug 16 '21 at 15:56
@Sup which of the answer gives a randomized list? I don't think it is directly answered there. — Zabir Al Nazi, Aug 16 '21 at 15:56
We don't need to do all the `n!` computation, considering we can iteratively generate the permutations. Yeah, `n!` is pretty large, but as it's a simulation problem, the solution will run on a server, but still, it's important to optimize, the itertools does everything except giving a random order each time. — Zabir Al Nazi, Aug 16 '21 at 15:59
I don't think you can keep track of the randomization without keeping the entire result in memory. Else we may end up repeating the already generated permutation. I really like your question, if you can do it without the space complexity consideration, you actually would have solved P=NP millennium problem. — Sup, Aug 16 '21 at 16:17
Maybe you can pull some idea frome here: https://github.com/markpiffer/pypourri — Vroomfondel, Aug 16 '21 at 17:01
If you were randomly generating permutations, Is it a problem to keep a set of permutations already seen in order to avoid duplicates? — VPfB, Aug 16 '21 at 17:35
In Monte-Carlo simulations, generally you don't worry about the (small) risk of getting the same object twice, as long as your random method gives you a *representative sample* of all possible objects. As mentioned by Sup, this unicity constraint forces you to keep the whole history in memory and search it repetitively, and that's expensive. If you remove the constraint, the problem is simple and can be solved with just `random.sample()`. — jpmarinier, Aug 16 '21 at 19:04
I think, random shuffling is the way to go. Thanks, everyone for the comments. — Zabir Al Nazi, Aug 17 '21 at 13:36

score 0 · Accepted Answer · answered Aug 16 '21 at 16:10

One way would be to shuffle before and/or after you generate the permutations.

For reference:

import itertools
import random
a = list(range(3))
print("original =",a)
random.shuffle(a)
print("shuffled =",a)
permutations = list(itertools.permutations(a))
print("permutations of shuffled array =",permutations)
random.shuffle(permutations)
print("shuffled permutations of shuffled array =",permutations)

original = [0, 1, 2]
shuffled = [1, 0, 2]
permutations of shuffled array = [(1, 0, 2), (1, 2, 0), (0, 1, 2), (0, 2, 1), (2, 1, 0), (2, 0, 1)]
shuffled permutations of shuffled array = [(0, 1, 2), (2, 0, 1), (2, 1, 0), (1, 0, 2), (1, 2, 0), (0, 2, 1)]

score 0 · Answer 2 · answered Aug 17 '21 at 11:21

0

Generate random permutations : if you only use a small number k of them, the chance you take twice the same is k/n!.

answered Aug 17 '21 at 11:21

Jean Valj

119
4

Corralien · Answer 3 · 2021-08-16T17:12:55.053

-1

Use random.sample:

permutations = list(itertools.permutations(range(5)))
permutation = random.sample(permutations, k=4)

# run 1
>>> random.sample(permutations, k=4)
[(0, 4, 1, 2, 3), (4, 0, 1, 3, 2), (3, 2, 0, 4, 1), (1, 2, 3, 4, 0)]

# run 2
>>> random.sample(permutations, k=4)
[(2, 1, 4, 0, 3), (0, 3, 4, 1, 2), (3, 1, 4, 0, 2), (0, 3, 4, 2, 1)]

# run 3
>>> random.sample(permutations, k=4)
[(3, 4, 1, 0, 2), (3, 0, 1, 2, 4), (0, 4, 1, 2, 3), (3, 4, 2, 0, 1)]

# and so on

edited Aug 16 '21 at 17:12

answered Aug 16 '21 at 15:44

Corralien

109,409
8
28
52

Thanks for the answer, but it uses `list` to first create the full permutation list, is it not very suboptimal considering I only need a small subset from the initial permutations? – Zabir Al Nazi Aug 16 '21 at 15:49
Just for demonstration purpose... Once the list is generated, keep it in variable. – Corralien Aug 16 '21 at 17:10

python permutations with more randomization

3 Answers3