Generate all permutations where length of a permutation > # of elements in Python

Question

I want to generate permutations (tuples) from these elements:

[None, 0, 1, 2]. 

I want each permutation to have length 5 and always contain 3 Nones. An example of one such permutation:

(None, 0, None, None, 1).

I have currently created this algorithm in Python 3.x:

[state for state in list(set(it.permutations((None, None, None, 0, 0, 1, 1, 2, 2), 5))) if state.count(None)==3]

However, I feel this algorithm is sub-optimal (and, well, ugly) and I am not entirely sure it is even correct. Are there any better solutions? I have perused NumPy, but found nothing that would help me.

Thanks for the help!

Answer 1

You can create a recursive function:

def group(d, current = [], in_place = [None, 3]):
  need, _occurs = in_place
  if len(current) == 5 and current.count(need) == _occurs:
    yield current
  else:
    for i in d:
      _c = current+[i]
      if len(_c) <= 5 and _c.count(need) <= _occurs:
        yield from group(d, current = _c)

Output:

[[None, None, None, 0, 0], [None, None, None, 0, 1], [None, None, None, 0, 2], [None, None, None, 1, 0], [None, None, None, 1, 1], [None, None, None, 1, 2], [None, None, None, 2, 0], [None, None, None, 2, 1], [None, None, None, 2, 2], [None, None, 0, None, 0], [None, None, 0, None, 1], [None, None, 0, None, 2], [None, None, 0, 0, None], [None, None, 0, 1, None], [None, None, 0, 2, None], [None, None, 1, None, 0], [None, None, 1, None, 1], [None, None, 1, None, 2], [None, None, 1, 0, None], [None, None, 1, 1, None], [None, None, 1, 2, None], [None, None, 2, None, 0], [None, None, 2, None, 1], [None, None, 2, None, 2], [None, None, 2, 0, None], [None, None, 2, 1, None], [None, None, 2, 2, None], [None, 0, None, None, 0], [None, 0, None, None, 1], [None, 0, None, None, 2], [None, 0, None, 0, None], [None, 0, None, 1, None], [None, 0, None, 2, None], [None, 0, 0, None, None], [None, 0, 1, None, None], [None, 0, 2, None, None], [None, 1, None, None, 0], [None, 1, None, None, 1], [None, 1, None, None, 2], [None, 1, None, 0, None], [None, 1, None, 1, None], [None, 1, None, 2, None], [None, 1, 0, None, None], [None, 1, 1, None, None], [None, 1, 2, None, None], [None, 2, None, None, 0], [None, 2, None, None, 1], [None, 2, None, None, 2], [None, 2, None, 0, None], [None, 2, None, 1, None], [None, 2, None, 2, None], [None, 2, 0, None, None], [None, 2, 1, None, None], [None, 2, 2, None, None], [0, None, None, None, 0], [0, None, None, None, 1], [0, None, None, None, 2], [0, None, None, 0, None], [0, None, None, 1, None], [0, None, None, 2, None], [0, None, 0, None, None], [0, None, 1, None, None], [0, None, 2, None, None], [0, 0, None, None, None], [0, 1, None, None, None], [0, 2, None, None, None], [1, None, None, None, 0], [1, None, None, None, 1], [1, None, None, None, 2], [1, None, None, 0, None], [1, None, None, 1, None], [1, None, None, 2, None], [1, None, 0, None, None], [1, None, 1, None, None], [1, None, 2, None, None], [1, 0, None, None, None], [1, 1, None, None, None], [1, 2, None, None, None], [2, None, None, None, 0], [2, None, None, None, 1], [2, None, None, None, 2], [2, None, None, 0, None], [2, None, None, 1, None], [2, None, None, 2, None], [2, None, 0, None, None], [2, None, 1, None, None], [2, None, 2, None, None], [2, 0, None, None, None], [2, 1, None, None, None], [2, 2, None, None, None]]

Answer 2

Here's how I'd approach it if I really didn't want to generate and filter out a bunch of inappropriate entries:

You need 0 to 3 Nones (call that number n1), followed by one non-None item from the list, followed by 0 to 3-n1 Nones (n2), followed by a second non-None item from the list, followed by 3-n1-n2 Nones.

states = []
for (i1, i2) in permutations((0,1,2), 2):
    for n1 in range(4):
        for n2 in range(4-n1):
            states.append((None,)*n1 + (i1,) + (None,)*n2 + (i2,) + (None,)*(3-n1-n2))

Answer 3

Assuming (from the output of your code and the fact you deliberately added multiple copies of 0, 1, and 2) that you're doing 'permutations with replacement', or basically the Cartesian product with your 3 Nones requirement, I'd do something like:

def tien_gen(size, values, number_of_nones):
    to_fill = size - number_of_nones
    for locs in itertools.combinations(range(size), to_fill):
        for fill_values in itertools.product(values, repeat=to_fill):
            out = [None] * size
            for loc, fill_value in zip(locs, fill_values):
                out[loc] = fill_value
            yield tuple(out)

which matches your output:

In [137]: result = list(tien_gen(5, [0,1,2], 3))

In [138]: len(result)
Out[138]: 90

In [139]: result
Out[139]: 
[(0, 0, None, None, None),
 (0, 1, None, None, None),
 (0, 2, None, None, None),
 (1, 0, None, None, None),
 [...]
 (None, 0, None, 1, None),
 (None, 0, None, 2, None),
 (None, 1, None, 0, None),
 [...]
 (None, 2, None, 1, None),
 (None, 2, None, 2, None),
 (None, 0, None, None, 0),
 (None, 0, None, None, 1),
 [...]
 (None, None, None, 1, 2),
 (None, None, None, 2, 0),
 (None, None, None, 2, 1),
 (None, None, None, 2, 2)]

In [140]: orig = [state for state in list(set(it.permutations((None, None, None, 0, 0, 1, 1, 2, 2), 5))) if state.count(None)==3]

In [141]: len(result) == len(orig) and set(result) == set(orig)
Out[141]: True

For small sizes the advantages are limited, but for larger ones, this way you avoid generating any tuple that you don't use, and since it's a generator, you don't have to materialize them all if you don't want to.

Answer 4

Conceptually, I think the easiest "efficient" algorithm might be explained as: First generate the permutations of length 2. Then, insert 3 instances of None in all possible ways.

However, it is more efficient to instead: First, generate all indices where you want your two elements to be. Then, for each set of indices for each permutation of length 2, substitute these elements in the given indices.

from itertools import combinations, permutations, product

base_list = [None] * 5
values = [0, 1, 2]

all_indices = combinations(range(5), 2)
all_perms = permutations(values, 2)

for (i, j), (x, y) in product(all_indices, all_perms):
    list_copy = base_list[:]
    list_copy[i] = x
    list_copy[j] = y
    print(list_copy)

# [0, 1, None, None, None]
# [0, 2, None, None, None]
# ...
# [None, None, None, 2, 0]
# [None, None, None, 2, 1]

This should be readily extensible for inputs of different lengths.

def inserted_permutations(size, values, insert_count, default=None):
    base = [default] * size
    all_indices = combinations(range(size), insert_count)
    all_perms = permutations(values, insert_count)
    for indices, values in product(all_indices, all_perms):
        base_copy = base[:]
        for index, value in zip(indices, values):
            base_copy[index] = value
        yield base_copy

Answer 5

from itertools import product

elemets = [None, 0, 1, 2]
l = product(elemets, repeat=5)
s = set(p for p in l if p.count(None) == 3)

print(s)

Output:

{(None, None, None, 0, 2), (None, None, 0, None, 2), (1, 2, None, None, None), (0, None, None, 1, None), (1, None, 2, None, None), (1, None, None, 2, None), (None, 2, 1, None, None), (None, None, None, 2, 1), (None, None, 2, None, 1), (None, None, None, 1, 1), (None, 0, None, 0, None), (None, 0, 0, None, None), (None, 1, None, None, 1), (2, 1, None, None, None), (2, None, None, 1, None), (None, 0, None, None, 1), (None, 0, None, 1, None), (0, None, None, 0, None), (0, None, 0, None, None), (None, None, 1, 1, None), (1, None, None, 1, None), (2, None, None, 2, None), (2, None, 2, None, None), (None, None, 2, None, 0), (None, None, None, 2, 0), (None, None, None, 1, 2), (0, 0, None, None, None), (None, 0, None, None, 0), (2, 0, None, None, None), (None, None, 0, 1, None), (None, None, 1, 2, None), (None, 0, None, 2, None), (None, 0, 2, None, None), (0, 1, None, None, None), (None, 2, None, 2, None), (None, 2, 2, None, None), (None, 1, None, 1, None), (None, None, 1, None, 0), (2, None, None, None, 2), (2, 2, None, None, None), (2, None, None, 0, None), (2, None, 0, None, None), (None, 1, None, 2, None), (None, 1, 2, None, None), (0, None, 1, None, None), (0, None, None, None, 1), (None, None, None, 0, 1), (None, None, 0, None, 1), (None, 2, None, 1, None), (None, 0, None, None, 2), (None, None, 1, None, 1), (2, None, 1, None, None), (2, None, None, None, 1), (None, None, 0, 2, None), (1, None, None, None, 0), (None, 1, None, None, 2), (None, 0, 1, None, None), (0, None, None, None, 2), (None, 2, None, None, 2), (0, None, None, None, 0), (None, None, 0, 0, None), (None, None, 2, 2, None), (None, None, None, 0, 0), (None, None, 0, None, 0), (None, 2, None, 0, None), (None, 2, 0, None, None), (1, None, 1, None, None), (None, None, 1, None, 2), (2, None, None, None, 0), (0, 2, None, None, None), (1, None, None, 0, None), (1, None, None, None, 1), (1, None, 0, None, None), (None, None, 1, 0, None), (None, 1, None, 0, None), (None, 1, 0, None, None), (None, None, 2, 1, None), (None, 2, None, None, 1), (1, 1, None, None, None), (None, None, None, 2, 2), (1, None, None, None, 2), (0, None, None, 2, None), (0, None, 2, None, None), (None, 1, 1, None, None), (None, None, None, 1, 0), (None, None, 2, None, 2), (None, 1, None, None, 0), (None, None, 2, 0, None), (1, 0, None, None, None), (None, 2, None, None, 0)}