CODEWITHSUNDEEP
pythonpermutationpython-itertools
user9102437
user9102437

Reputation: 742

Generate permutations of size n from given list, where each permutations must contain all of the original values, possibly repeated

I was trying to create a small script that will take the list of elements and create all the possible permutations of its contents, while all those permutations may have repetitions and have to be of size n and contain all the original values. I tried to use the itertools library but they don't have anything of use. Is there something simple I can do to achieve that?

Here is an example for the list [0,1,2] and n=3:

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

For n=4, something like [0,1,1,2] will also be allowed in the output.

Upvotes: 1

Views: 767

Answers (2)

Brian61354270
Brian61354270

Reputation: 14423

The behavior you described can be implemented with the following function:

def perms_with_duplicates(lst: list, n: int) -> Iterator:
    """
    Generate permutations of ``lst`` with length ``n``. 
    If ``n`` is greater than the length of ``lst``, then the
    resulting permutations will include duplicate elements 
    from ``lst``. All of the original elements of ``lst``
    are guaranteed to appear in each output permutation.
    """
    
    # Number of duplicate entries that the permutations can include.
    num_dupl = max(n - len(lst) + 1, 1)
    
    return itertools.permutations(lst * num_dupl, n)

Alternatively, if you need this to work over any sequence, instead of just for lists, you could use

def perms_with_duplicates(seq: Sequence, n: int) -> Iterator:
    """
    Generate permutations of ``seq`` with length ``n``. 
    If ``n`` is greater than the length of `seq`, then the
    resulting permutations will include duplicate elements 
    from ``seq``. All of the original elements of ``seq``
    are guaranteed to appear in each output permutation.
    """
    
    # Number of duplicate entries that the permutations can include.
    num_dupl = max(n - len(seq) + 1, 1)

    it_dupl =  itertools.chain.from_iterable(
        itertools.repeat(seq, num_dupl)
    )
    
    return itertools.permutations(it_dupl, n)

Both functions behave as follows. Note that for n less than or equal to the length of the input sequence, the functions behave exactly like itertools.permutations.

>>> l = [0, 1, 2]

>>> list(perms_with_duplicates(l, 3))                                                                                                
[(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]

>>> len(list(perms_with_duplicates(l, 4)))
360

>>> list(perms_with_duplicates(l, 4))                                                                                                
[(0, 1, 2, 0),
 (0, 1, 2, 1),
 (0, 1, 2, 2),
 (0, 1, 0, 2),
 (0, 1, 0, 1),
 ...
 (1, 2, 1, 0),
 (1, 2, 1, 0),
 (1, 2, 1, 2),
 (1, 2, 0, 0),
 (1, 2, 0, 1),
 ...
 (2, 1, 0, 2)]

Upvotes: 1

smci
smci

Reputation: 33938

There is itertools.combinations_with_replacement(). [New in 3.1]

If the sequence length n is equal to number of unique elements, as in your example, then trivially there can be no repetitions, so this would reduce to itertools.permutations()

Else for the general case, use a list comprehension to filter the raw output from itertools.combinations_with_replacement():

from itertools import combinations_with_replacement

elems = [0,1,1,2]

[comb for comb in combinations_with_replacement(elems, 4) if all(el in comb for el in elems)]

[(0, 0, 1, 2), (0, 0, 1, 2), (0, 1, 1, 2), (0, 1, 1, 2), (0, 1, 2, 2), (0, 1, 1, 2), (0, 1, 2, 2)]

Upvotes: 0

Related Questions