What's the best way to generate unique permutations in Python?

Joan_Venge_51816 0
Viewed 287

I have 2 choices between 0 and 1 for each item where I will have N elements sequenced one after another generating a unique combination.

So something like these (sequence length=10):

0, 1, 0, 1, 0, 1, 0, 1, 0, 1
0, 0, 0, 1, 0, 1, 0, 1, 0, 1
0, 1, 1, 1, 0, 1, 0, 1, 0, 1
1, 1, 1, 1, 0, 1, 0, 1, 0, 1

As you see these are all unique permutations. I will have 10000 of these permutations (for example). But the key info is I don't need all the permutations, but rather only save a limited set of them, and ideally out of order, so it's a bit more "random".

My current solution is to generate random numbers between 0 and 1, and append them in an array up to N elements. Then turn this array into a string and if this string is not already added to my list above, then add this, otherwise repeat the same step to generate a different permutation.

So that means using a while loop.

Is there a smarter, or more elegant way to do this?

combinations combinatorics sequence random python
1 Answers
  • This is a binary number and each unique binary number correspond to a unique decimal.
  • With 10 places, there are 2^10 = 1024 unique.
  • Choose 10 from these 1024 without replacement
  • Convert decimal to its binary

Generate 5 unique samples each of 10 digits

import numpy as np
n_digits = 10
n_sample = 5
for c in np.random.choice(np.power(2,n_digits), size=n_sample, replace=False):
  c = int("{0:b}".format(c))
  print (str(c).zfill(n_digits))

Sample run

0100011110
0110110011
0100110001
1110011100
1110101011

Edit:

The above code is fast but will not scale to larger digits due to np.power(2,n_digits) resulting in overflow as well np.random.choice will run out of memory.

For scaling it to very large sequences we can use a bit slow but very decent mechanism like below

n_digits = 200
n_sample = 10000
choices = []
cache = {}
while len(choices) < n_sample:
    c = np.random.randint(0,2,(n_digits))
    k = c.tostring()
    if not k in cache:
        cache[k] = True
        choices.append(c)

%timeit returned

27.4 ns ± 10.1 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

which is pretty decent.

choices is list of numpy arrays and if you want to convert it into text you can use

for i in range(len(choices)):
    choices[i] = np.array2string(choices[i], separator='')[1:-1].replace("\n", "").replace(" ", "")
user_4239260
Related