i have an array of 27 elements,and i don't want to generate all permutations of array (27!) i need 5000 randomly choosed permutations,any tip will be useful...
+2
A:
itertools.permutations. It's a generator, so it won't create the whole list of permutations. You could skip randomly until you've got 5000.
PiotrLegnica
2010-01-23 19:14:14
Might take a long time to do using this method....
Mark Byers
2010-01-23 19:14:43
That's not really "random", since `itertools` creates them in a defined order, and there are a finite number of permutations. What would be better is to do the following: (1) determine **how many** permutations there are (call this number `N`), (2) then generate 5,000 distinct random indices in the range `0..N-1`, (3) pick the permutations from the itertools.permutations generator which correspond to these indices.
John Feminella
2010-01-23 19:16:43
Yeah, I know it's not the best. First time I read the question I somehow didn't notice that 'randomly chosen' part. I won't delete it, maybe someone searching for "how to generate permutations of array in python?" will find it useful.
PiotrLegnica
2010-01-23 19:35:41
A:
You may want the itertools.permutations() function. Gotta love that itertools module!
NOTE: New in 2.6
ironfroggy
2010-01-23 19:14:54
+4
A:
import random
perm_list = []
for i in range(5000):
temp = range(27)
random.shuffle(temp)
perm_list.append(temp)
print(perm_list)
10888869450418352160768000000 I love big numbers! :)
AND
10888869450418352160768000001 is PRIME!!
EDIT:
#with duplicates check as suggested in the comment
perm_list = set()
while len(perm_list)<5000:
temp = range(27)
random.shuffle(temp)
perm_list.add(tuple(temp)) # `tuple` because `list`s are not hashable. right Beni?
print perm_list
WARNING: This wont ever stop if RNG is bad!
TheMachineCharmer
2010-01-23 19:16:25
To also check for duplicates as Mark suggests, use a `perms = set()`, `perms.add(tuple(temp))`, and `while len(perms) < 5000` instead of the for loop.
Beni Cherniavsky-Paskin
2010-01-23 19:45:56
@Beni I didn't follow your `tuple(temp)` suggestion at first but then I understood that I was a fool!! Thanks man!
TheMachineCharmer
2010-01-23 19:57:22
+7
A:
To generate one permutation use random.shuffle and store a copy of the result. Repeat this operation in a loop and each time check for duplicates (there probably won't be any though). Once you have 5000 items in your result set, stop.
To address the point in the comment, Python's random module is based on the Mersenne Twister and has a period of 2**19937-1, which is considerably larger than 27! so it should be suitable for your use.
Mark Byers
2010-01-23 19:17:12
+1, but note that `random.shuffle` has a serious weakness: the period of most RNGs is smaller than the total number of permutations as _n_ gets larger. That means that almost all of the possible permutations for a large enough _n_ cannot ever be generated, so this isn't truly random.
John Feminella
2010-01-23 19:32:58
Indeed, John. Python's random generator has a period of 2**19937-1 though so it is probably good enough. Another nitpick is that for true random numbers you would need a true random source (e.g. from radioactive decay), Python's random module provides only pseudo-random numbers. But in common usage when people say 'random' what they really mean is 'pseudo-random', and I assume this is what the poster here means.
Mark Byers
2010-01-23 19:35:03
+1 Cool! It's a big die with 10888869450418352160768000000 faces probability of any one of them turning up is 1/10888869450418352160768000000. Duplicates NO WAY!!
TheMachineCharmer
2010-01-23 19:39:45
A:
# apermindex should be a number between 0 and factorial(len(alist))
def perm_given_index(alist, apermindex):
for i in range(len(alist)-1):
apermindex, j = divmod(apermindex, len(alist)-i)
alist[i], alist[i+j] = alist[i+j], alist[i]
return alist
call like perm_given_index(['a','b','c'], 3)
i think this uses the Lehmer code for the permutation as the values of j match that
Dan D
2010-07-13 21:59:20