Python permutations for array of elements with specific repetitions

Question

How would I compute permutations of an array of elements, each repeated for a certain number of times within the permutation, in the fastest possible way?

For example:

elements = [0, 1]
repetitions = [2, 3]

I want it to return the 10 unique permutations:

[(0, 0, 1, 1, 1), (0, 1, 0, 1, 1), (1, 0, 1, 0, 1) ....]

Do you have only 0 and 1 in your elements vector or do you want any random integer ? — Erwan, Aug 11 '18 at 12:56
These are called multisets and can be generated with `multiset_permutations ` from `sympy` . — Joseph Wood, Aug 11 '18 at 14:22

Thierry Lathuille · Accepted Answer · 2018-08-11T18:11:32.020

Here is a solution: the idea is to find all possible indices where we can put the first element, then to recursively find the possible indices for the remaining ones. This way, we are guaranteed to generate directly unique outputs.

from itertools import combinations


def combs(elements, repetitions, index=0, indices_left=None, already_set=None):
    if indices_left is None:
        already_set = [None] * sum(repetitions)
        indices_left = set(range(sum(repetitions)))

    element = elements[index]
    number = repetitions[index]

    for indices_choice in combinations(indices_left, number):
        currently_set = already_set[:]
        for i in indices_choice:
            currently_set[i] = element
        remaining_indices = indices_left - set(indices_choice)
        if not remaining_indices:
            yield currently_set
        else:
            yield from combs(elements, repetitions, index+1, remaining_indices, currently_set)

With your example input, this gives us:

elements = [0, 1]
repetitions = [2, 3]

for comb in combs(elements, repetitions):
    print(comb)

# [0, 0, 1, 1, 1]
# [0, 1, 0, 1, 1]
# [0, 1, 1, 0, 1]
# [0, 1, 1, 1, 0]
# [1, 0, 0, 1, 1]
# [1, 0, 1, 0, 1]
# [1, 0, 1, 1, 0]
# [1, 1, 0, 0, 1]
# [1, 1, 0, 1, 0]
# [1, 1, 1, 0, 0]

Another example with more elements:

elements = [0, 1, 2]
repetitions = [2, 3, 2]

c = combs(elements, repetitions)

print(next(c))
# [0, 0, 1, 1, 1, 2, 2]

print(next(c))
# [0, 0, 1, 1, 2, 1, 2]

print(len(list(combs(elements, repetitions))))
# 210

A little speed test:

elements = [0, 1]
repetitions = [10, 10]

a = list(combs(elements, repetitions))
print(len(a))
# 184756

%timeit list(combs(elements, repetitions))
# 1.15 s ± 5.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Julien Cochennec · Answer 2 · 2018-08-11T12:44:28.830

It's not a complete answer but the general idea. I'm almost sure there's no simple way to do this without recursivity and combination (itertools). Let's say you have defined your data, elements and repetitions.

n is the size of elements
s is the sum of all terms of repetitions, so it is the final number of elements of each permutations you're looking for.

You have to make a recurrence I guess, that would translate into a recursive function. En is the array of elements. Rn is the array of repetitions. So En-1 is the array of the n-1 first elements and Rn-1 first elements. If you know the solution for En-1 and Rn-1, you just have to calculate a combination with the itertools package, see here. With your example, you know E2 and R2 right? I'll try to find time to write the code, I don't know how much you're familiar with recursivity, it can be hard to understand.

from itertools import combinations

def multipleElementsPermutations(elements, repetitions): #elements is En, repetitions is Rn
    if len(elements) != len(repetitions) or len(elements) <2 or len(repetitions) <2:
        return None 
    elif len(elements) == 2:
        #Write some code using itertools to solve the case n=2
        return list(permutations(elements[0]*repetitions[0] + elements[1]*repetitions[1], repetitions[0]+repetitions[1]))
    else:
        last_element = elements[-1]
        last_repetition = repetitions[-1]
        #Here thus function will call itself with the n-1 arguments
        previous_case_solution = multipleElementsPermutation(
            elements[:-1], #En-1
            repetitions[:-1] #Rn-1
        )
        #Write some code here to find different ways to add last element

Sorry for not having time to write the full solution. It is more a math problem than a code problem I guess.

Using the idea of Erwan below, maybe this code would work :

from itertools import permutations

n = len(elements)
repeated_elements_array = [element[i]*repetition[i] for i in range(n)]
repeated_elements_list = []
for repeated_elements in repeated_elements_array:
    repeated_elements_list += repeated_elements
s = 0
for repetition in repetitions:
    s += repetition
solution = permutations(repeated_elements_list, s)

Erwan · Answer 3 · 2018-08-11T13:06:58.120

You can use permutations from itertools module

>>> from itertools import permutations
>>> list(permutations([0]*2 + [1]*3, 5))
[(0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0)]

A more automatic versions :

>>> e = [0, 1]
>>> r = [2, 3]
>>> b = sum([[i]*j for i, j in zip(e, r)], [])
>>> list(permutations(b, len(b)))
[(0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 0, 1, 1, 1), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 0, 1, 1), (0, 1, 0, 1, 1), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (0, 1, 1, 0, 1), (0, 1, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 0, 1, 1), (1, 0, 0, 1, 1), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 0, 1, 0, 1), (1, 0, 1, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 0, 0, 1), (1, 1, 0, 1, 0), (1, 1, 1, 0, 0), (1, 1, 1, 0, 0)]

Edit: as noted by @JosephWood If you don't want duplicate (00111 can appear several times) look at here

Edit2: If you only have 0,1 in your elements and you don't want duplicate, you could use binary representation like that (j for j in ([i%2, i//2%2, i//4%2, i//8%2, i//16%2] for i in range(0, 2**5)) if sum(j)==3). I don't know if it's faster or not.

Nice, so maybe we can find a solution with elements – Julien Cochennec Aug 11 '18 at 12:36 — Julien Cochennec, Aug 11 '18 at 12:36

Krishna · Answer 4 · 2018-08-11T14:53:24.787

0

similar to @Erwan, it works also:

import itertools as it
elements = [0, 1]
repetitions = [2, 3]
arr = []
for j,i in enumerate(repetitions):
   arr = arr +[elements[j]]*i

set(list(it.permutations(arr)))

edited Aug 11 '18 at 14:53

answered Aug 11 '18 at 13:44

Krishna

6,107
2
40
43

This code produces 120 tuples, while there are only 10 distinct outputs. – Thierry Lathuille Aug 11 '18 at 14:48
@ThierryLathuille corrected. thanks. – Krishna Aug 11 '18 at 14:54
The problem is, though, that your code needs to generate a very large number of identical permutations, all stored in memory, before you start to remove duplicates with `set()`. This will very quickly become impratical: for example, for `repetitions = [10, 10]`, you would need to generate a list of 2432902008176640000 (2.4e18) items, which is impossible because of the time and space needed, while there are only 184756 unique permutations. – Thierry Lathuille Aug 11 '18 at 18:03

Python permutations for array of elements with specific repetitions

4 Answers4