Generate Permutations of List with Repeated Elements

Generate permutations of list with repeated elements

This web page looks promising.

def next_permutation(seq, pred=cmp):
    """Like C++ std::next_permutation() but implemented as
    generator. Yields copies of seq."""
    def reverse(seq, start, end):
        # seq = seq[:start] + reversed(seq[start:end]) + \
        #       seq[end:]
        end -= 1
        if end <= start:
            return
        while True:
            seq[start], seq[end] = seq[end], seq[start]
            if start == end or start+1 == end:
                return
            start += 1
            end -= 1
    if not seq:
        raise StopIteration
    try:
        seq[0]
    except TypeError:
        raise TypeError("seq must allow random access.")
    first = 0
    last = len(seq)
    seq = seq[:]
    # Yield input sequence as the STL version is often
    # used inside do {} while.
    yield seq[:]
    if last == 1:
        raise StopIteration
    while True:
        next = last - 1
        while True:
            # Step 1.
            next1 = next
            next -= 1
            if pred(seq[next], seq[next1]) < 0:
                # Step 2.
                mid = last - 1
                while not (pred(seq[next], seq[mid]) < 0):
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                # Step 3.
                reverse(seq, next1, last)
                # Change to yield references to get rid of
                # (at worst) |seq|! copy operations.
                yield seq[:]
                break
            if next == first:
                raise StopIteration
    raise StopIteration

>>> for p in next_permutation([int(c) for c in "111222"]):
...     print p
... 
[1, 1, 1, 2, 2, 2]
[1, 1, 2, 1, 2, 2]
[1, 1, 2, 2, 1, 2]
[1, 1, 2, 2, 2, 1]
[1, 2, 1, 1, 2, 2]
[1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 2, 1]
[1, 2, 2, 1, 1, 2]
[1, 2, 2, 1, 2, 1]
[1, 2, 2, 2, 1, 1]
[2, 1, 1, 1, 2, 2]
[2, 1, 1, 2, 1, 2]
[2, 1, 1, 2, 2, 1]
[2, 1, 2, 1, 1, 2]
[2, 1, 2, 1, 2, 1]
[2, 1, 2, 2, 1, 1]
[2, 2, 1, 1, 1, 2]
[2, 2, 1, 1, 2, 1]
[2, 2, 1, 2, 1, 1]
[2, 2, 2, 1, 1, 1]
>>> 

---

2017-08-12

Seven years later, here is a better algorithm (better for clarity):

from itertools import permutations

def unique_perms(series):
    return {"".join(p) for p in permutations(series)}

print(sorted(unique_perms('1122')))

Generating permutations with repetitions

You are looking for the Cartesian Product.

In mathematics, a Cartesian product (or product set) is the direct product of two sets.

In your case, this would be {1, 2, 3, 4, 5, 6} x {1, 2, 3, 4, 5, 6}.
itertools can help you there:

import itertools
x = [1, 2, 3, 4, 5, 6]
[p for p in itertools.product(x, repeat=2)]
[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 1), (2, 2), (2, 3), 
 (2, 4), (2, 5), (2, 6), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), 
 (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (5, 1), (5, 2), (5, 3), 
 (5, 4), (5, 5), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)]

To get a random dice roll (in a totally inefficient way):

import random
random.choice([p for p in itertools.product(x, repeat=2)])
(6, 3)

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

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)]

all permutations from 2 lists but with a condition on the amount of elements

I want to try to write a general-purpose answer here in the hope of having a good canonical target for duplicate questions in the future.

Combinatoric Fundamentals in Python with itertools

Reordering and Replacement (Repetition)

It's important to understand how the various combinatoric iterators provided by itertools work and how they differ.

Let's consider a simple candidate set A = [1, 2, 3, 4], from which we want to draw "combinations" (as question-askers will usually put it) of three elements.

>>> A = [1,2,3,4]

itertools.combinations selects with no reordering (i.e., each output value will appear in the same order as in the input) and no repetition of the result values. This therefore produces only 4 results:

>>> list(itertools.combinations(A, 3))
[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

itertools.permutations means that the results can appear in any order, i.e. a given subset of the input will appear multiple times in the output in different orders.

>>> list(itertools.permutations(A, 3)) # 24 results omitted for brevity

The four combinations appear in six orders each, for 24 total results.

itertools.combinations_with_replacement selects without reordering, but allows elements from the input to be chosen more than once:

>>> list(itertools.combinations_with_replacement(A, 3)) # 20 results omitted for brevity

There are four results where each element is chosen three times, six where a double is followed by a single (which must be higher), six where a single is followed by a double, plus the four combinations of all singles. Counting the results for this in the general case is not easy.

If you want to allow repetitions and reordering in your output results, you can use itertools.product:

>>> list(itertools.product(A, repeat=3)) # 64 results omitted for brevity

Simply, each of three times we freely choose from the four elements, for 4 * 4 * 4 = 64 results.

itertools.product implements what is called the Cartesian product. In general, it pulls one element each from multiple specified sequences. But generating "permutations with replacement" is the same thing as pulling one element each from the same sequence multiple times, so the repeat keyword is offered as a convenient shortcut for this operation - so you don't have to specify the sequence multiple times. I mean, you could write itertools.product(*[A]*3), but that's ugly.

What about repetition in the candidate set?

This isn't related to OP's question as asked; but for completeness, it's important to understand that none of these functions care about elements of the candidate set being equal, or even identical:

>>> x = object()
>>> candidates = [x, x, x, x]
>>> results = list(itertools.combinations(candidates, 3))
>>> len(results)
4
>>> results[0] == results[1] == results[2] == results[3]
True

How can we implement constraints?

The simplest way is to generate an inclusive result (in OP's case, by joining the a and b candidates together, and generating a product of 10 of those) and filter out things that don't meet the requirements. However, this is inefficient and can be ugly (we need to analyze an output tuple to figure out whether its elements meet the conditions - in OP's case, whether they were drawn from a or from b. If you do want to take an approach like this, I generally recommend writing a generator function:

def OP_problem():
    for result in itertools.product(a+b, repeat=10):
        a_count = len(x for x in result if x in a)
        # the trick is that every element was either from a or b;
        # so "at least 3 a's and at least 3 b's" is equivalent to
        # "at least 3 a's and at most 7 a's".
        if 3 <= a_count <= 7:
            yield result

or in simple enough cases, a generator expression:

(
    # maybe you don't think this is simple enough :)
    result for result in itertools.product(a+b, repeat=10)
    if 3 <= len(x for x in result if x in a) <= 7
)

Usually it's better to try to break the problem down into smaller pieces and put the results together. For example, the documentation has a recipe for computing power sets that simply chains the results for combinations of 0 elements, 1 element etc. up to all the elements. (Another way is to find the cartesian product of N booleans, each representing whether or not to include a given element, and then translate them into subsets.)

In our case, we can separately find the results for each count of a elements. Let's consider the case of 5 elements from each list; it should be clear how to generalize that and combine the results (hint: use itertools.chain.from_iterable, as shown in the powerset recipe in the documentation).

Difficult cases: partitions and position selection

There's one advanced technique I want to showcase here, in order to solve the problem of selecting 5 elements from a and 5 elements from b and intermingling them. The idea is simply that we select positions where the a's will go, out of all the possible positions (i.e., indices into a sequence of 10 elements), and for each, generate the corresponding output results. Those positions are combinations without replacement (do you understand why?) of the possible index values.

Thus, something like:

def make_combination(letter_positions, chosen_letters, chosen_digits):
    result = [None] * 10
    for letter, position in zip(chosen_letters, letter_positions):
        result[position] = letter
    # Figure out where the digits go, using set arithmetic to find the
    # remaining positions, then putting them back in ascending order.
    digit_positions = sorted(set(range(10)) - set(chosen_letters))
    for digit, position in zip(chosen_digits, digit_positions):
        result[position] = digit
    assert None not in result
    return tuple(result)

def five_letters_and_five_digits():
    letters = 'abcdefghijklmnopqrstuvwxyz'
    digits = '0123456789'
    # It's not *easy*, but it's fairly elegant.
    # We separately generate the letter positions, letter selection
    # and digit selection, using `product` to get the cartesian product
    # of *those* possibilities; then for each of those, we translate
    # into a desired output - using `starmap` to iterate.
    return itertools.starmap(
        make_combination, 
        itertools.product(
            itertools.combinations(range(10), 5),
            itertools.product(letters, repeat=5),
            itertools.product(digits, repeat=5)
        )
    )
                

The technique of choosing positions is also useful for solving partitioning problems. The idea is simply that you choose positions where the partitions go (for N elements there will generally be N-1 places to put them), as combinations - either with (if zero-size partitions are allowed) or without (otherwise) replacement.

How do I generate all permutations of a list?

Use itertools.permutations from the standard library:

import itertools
list(itertools.permutations([1, 2, 3]))

---

Adapted from here is a demonstration of how itertools.permutations might be implemented:

def permutations(elements):
    if len(elements) <= 1:
        yield elements
        return
    for perm in permutations(elements[1:]):
        for i in range(len(elements)):
            # nb elements[0:1] works in both string and list contexts
            yield perm[:i] + elements[0:1] + perm[i:]

A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

And another, based on itertools.product:

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

---

Related Topics