How to Generate All Permutations of a List

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)

Algorithm to generate all possible permutations of a list?

Basically, for each item from left to right, all the permutations of the remaining items are generated (and each one is added with the current elements). This can be done recursively (or iteratively if you like pain) until the last item is reached at which point there is only one possible order.

So with the list [1,2,3,4] all the permutations that start with 1 are generated, then all the permutations that start with 2, then 3 then 4.

This effectively reduces the problem from one of finding permutations of a list of four items to a list of three items. After reducing to 2 and then 1 item lists, all of them will be found.

Example showing process permutations using 3 coloured balls:

(from https://en.wikipedia.org/wiki/Permutation#/media/File:Permutations_RGB.svg - https://commons.wikimedia.org/wiki/File:Permutations_RGB.svg)

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 to generate all permutations of a ListListString?

Use CollectionUtils.permutations

public static void showAllPermuteByCommons(List<String> list) {
    CollectionUtils.permutations(list) //
            .stream() //
            .forEach(System.out::println);
}

Or backtrack

public static void permute(List<String> list, int left, int right) {
    if (left == right) {
        System.out.println(Arrays.toString(list.toArray()));
        return;
    }
    for (int j = left; j <= right; j++) {
        Collections.swap(list, left, j);
        permute(list, left + 1, right);
        Collections.swap(list, left, j);
    }
}

public static void showAllPermute(List<String> list) {
    int size = list.size();
    permute(list, 0, size - 1);
}

Test

List<List<String>> list = new ArrayList<>();
list.add(Arrays.asList("Test", "Test 1", "Test 2"));
list.add(Arrays.asList("Apple", "Sandwich", "Banana"));
list.add(Arrays.asList("Cake", "Ice Cream", "Fruit"));

// list.forEach(t -> showAllPermuteByCommons(t));
list.forEach(t -> showAllPermute(t));

Ouput

[Test, Test 1, Test 2]
[Test, Test 2, Test 1]
[Test 2, Test, Test 1]
[Test 2, Test 1, Test]
[Test 1, Test 2, Test]
[Test 1, Test, Test 2]
[Apple, Sandwich, Banana]
[Apple, Banana, Sandwich]
[Banana, Apple, Sandwich]
[Banana, Sandwich, Apple]
[Sandwich, Banana, Apple]
[Sandwich, Apple, Banana]
[Cake, Ice Cream, Fruit]
[Cake, Fruit, Ice Cream]
[Fruit, Cake, Ice Cream]
[Fruit, Ice Cream, Cake]
[Ice Cream, Fruit, Cake]
[Ice Cream, Cake, Fruit]

How to create all permutations starting from a list of words

Pᴇʜ and Tragamor both interpret your question as a request for all permutations of four words. I interpret your question as a request for all permutations of ten words. Their answers match their interpretation. This answer matches my interpretation although it should return all permutations of any number of words. I have fully tested my routine at creating all permutations of from three to nine words. For ten or more words my test routine takes too long to be viable. Since my routine works for up to and including nine words, I assume it works for larger numbers.

Both Pᴇʜ and Tragamor have used recursion. I consider recursion to be a very useful technique but for VBA, if not for other languages, it is a slow technique. I decided against recursion.

With my technique, the Permutation routine has two parameters: the array, Words, (containing the ten words) and the array Permutations (in which the 3,628,800 permutations are returned). The routine has an array, PermCrnt, containing the indices of the ten words. If the lower bound of Words is 0, the initial value of PermCrnt is:

0 1 2 3 4 5 6 7 8 9

The main loop of the Permutation routine uses PermCrnt’s indices to output the current permutation to array Permutations and then resets PermCrnt to the next sequence. This loop continues until array Permutations is full.

The code that resets PermCrnt looks from the right for two indices that are not in ascending sequence. Those indices and all to the right are removed from PermCrnt. The leftmost indice removed is replaced by the next in sequence. The remaining indices are placed in ascending sequence. This gives:

                      First pair not in ascending sequence. Remove that
PermCrnt              pair and all to their right and re-sequence them.
0 1 2 3 4 5 6 7 8 9   “8 9”
0 1 2 3 4 5 6 7 9 8   “7 9”
0 1 2 3 4 5 6 8 7 9   “7 9”
0 1 2 3 4 5 6 8 9 7   “8 9”
0 1 2 3 4 5 6 9 7 8   “7 8”
0 1 2 3 4 5 6 9 8 7   “6 9”
0 1 2 3 4 5 7 6 8 9   “8 9”
0 1 2 3 4 5 7 6 9 8

As can be seen, this simple algorithm cycles through all possible permutation until:

9 8 7 6 5 4 3 2 1 0

For ten words, my routine takes around 12 seconds to generate the 3,628,800 permutations.

My routine, and its test is below. Note: because of the way I have tested PermWords, it was convenient for Words to be a Variant. You may wish to change to an array of strings.

Option Explicit
Sub CallPermutations()

  Dim ColOutCrnt As Long
  Dim Duration As Single
  Dim InxPerm As Long
  Dim InxWord As Long
  Dim Match As Boolean
  Dim MultiWords As Variant
  Dim NumWords As Long
  Dim NumPerms As Long
  Dim Permutations() As String
  Dim RowOutCrnt1 As Long
  Dim RowOutCrnt2 As Long
  Dim RowOutMax As Long
  Dim TimeStart As Single
  Dim Words As Variant

  Application.ScreenUpdating = False

  MultiWords = VBA.Array(VBA.Array("apple", "bear", "cat"), _
                         VBA.Array("apple", "bear", "cat", "dog"), _
                         VBA.Array("apple", "bear", "cat", "dog", "egg"), _
                         VBA.Array("apple", "bear", "cat", "dog", "egg", "fast"), _
                         VBA.Array("apple", "bear", "cat", "dog", "egg", "fast", _
                                   "game"), _
                         VBA.Array("apple", "bear", "cat", "dog", "egg", "fast", _
                                   "game", "house"), _
                         VBA.Array("apple", "bear", "cat", "dog", "egg", "fast", _
                                   "game", "house", "island"), _
                         VBA.Array("apple", "bear", "cat", "dog", "egg", "fast", _
                                   "game", "house", "island", "joy"))

  For Each Words In MultiWords

    TimeStart = Timer
    Call PermWords(Words, Permutations)
    Duration = Timer - TimeStart

    NumWords = UBound(Words) - LBound(Words) + 1
    NumPerms = UBound(Permutations, 1) - LBound(Permutations, 1) + 1

    Debug.Print "Generating " & PadL(NumPerms, 7) & _
                " permutations of " & PadL(NumWords, 2) & _
                " words took " & PadL(Format(Duration, "#,##0.000"), 9) & " seconds"

    If NumWords < 9 Then

     TimeStart = Timer
      For RowOutCrnt1 = LBound(Permutations, 1) To UBound(Permutations, 1) - 1
        For RowOutCrnt2 = RowOutCrnt1 + 1 To UBound(Permutations, 1)
          Match = True
          For ColOutCrnt = 1 To NumWords
            If Permutations(RowOutCrnt1, ColOutCrnt) <> _
               Permutations(RowOutCrnt2, ColOutCrnt) Then
              Match = False
              Exit For
            End If
          Next
          If Match Then
            Debug.Print
            Debug.Print "Row " & RowOutCrnt1 & " = " & "Row " & RowOutCrnt2
            Debug.Assert False
          Else
          End If
        Next
      Next

      Duration = Timer - TimeStart

      Debug.Print "Testing    " & PadL(NumPerms, 7) & _
                  " permutations of " & PadL(NumWords, 2) & _
                  " words took " & PadL(Format(Duration, "#,##0.000"), 9) & " seconds"
    End If

    DoEvents
  Next

End Sub
Sub PermWords(ByRef Words As Variant, ByRef Permutations() As String)

  ' On entry Words is a list of words created by Array, VBA.Array or
  ' by code that emulated Array or VBA.Array.
  ' On exit, Permutations will contain one row permutation of the words.

  ' Note: Array creates an array with a lower bound of zero or one depending
  ' on the Option Base statement while VBA.Array creates an array with a
  ' lower bound that is always zero.

  ' Permutations will be redim'ed as a two-dimensional array.  The first
  ' dimension will have bounds of one to number-of-permutations.  The second
  ' dimension will have bounds to match those of Words.

  ' If Words contains "one", "two" and "three", Permutations will contain:
  '   "one"   "two"   "three"
  '   "one"   "three" "two"
  '   "two"   "one"   "three"
  '   "two"   "three" "one"
  '   "three" "one"   "two"
  '   "three" "two"   "one"

  Dim InxPermCrnt As Long
  Dim InxToPlaceCrnt As Long
  Dim InxToPlaceMax As Long
  Dim InxToPlaceNext As Long
  Dim InxWord As Long
  Dim ValueNext As Long
  Dim NumPerms As Long
  Dim NumWords As Long
  Dim PermCrnt() As Long
  Dim RowPerms As Long
  Dim ToPlace() As Long

  ' Calculate number of words and number of permutations
  NumWords = UBound(Words) - LBound(Words) + 1
  NumPerms = Factorial(NumWords)

  ' Redim arrays to required size
  ReDim PermCrnt(LBound(Words) To UBound(Words))
  ReDim Permutations(1 To NumPerms, LBound(Words) To UBound(Words))
  ReDim ToPlace(1 To NumWords)

  RowPerms = 1    ' First row in Permutations

  ' Create initial sequence of words
  For InxWord = LBound(Words) To UBound(Words)
    PermCrnt(InxWord) = InxWord
  Next

  ' Loop until Permutations() is full
  Do While True
    ' Output current permutation to Permutations
    For InxPermCrnt = LBound(PermCrnt) To UBound(PermCrnt)
      InxWord = PermCrnt(InxPermCrnt)
      Permutations(RowPerms, InxPermCrnt) = Words(InxWord)
    Next
    RowPerms = RowPerms + 1
    If RowPerms > UBound(Permutations, 1) Then
      ' All permutations generated
      Exit Sub
    End If
    ' Generate next sequence
    ' Find first pair from right not in ascending sequence
    ' Copy this pair, and all to its right, to ToPlace()
    InxToPlaceMax = 1
    ToPlace(InxToPlaceMax) = PermCrnt(UBound(PermCrnt))
    For InxPermCrnt = UBound(PermCrnt) - 1 To LBound(PermCrnt) Step -1
      InxToPlaceMax = InxToPlaceMax + 1
      ToPlace(InxToPlaceMax) = PermCrnt(InxPermCrnt)
      If PermCrnt(InxPermCrnt) < PermCrnt(InxPermCrnt + 1) Then
        Exit For
      End If
    Next
    ' Elements InxPermCrnt to UBound(PermCrnt) of PermCrnt are to be
    ' resequenced.  PermCrnt(InxPermCrnt) will reference the next to place word
    ' in sequence.  Remaining elements will be the values from ToPlace() in
    ' ascending sequence.
    ' Find next value above value in PermCrnt(InxPermCrnt)
    ValueNext = -1
    InxToPlaceNext = -1
    For InxToPlaceCrnt = 1 To InxToPlaceMax
      If PermCrnt(InxPermCrnt) < ToPlace(InxToPlaceCrnt) Then
        ' ToPlace(InxToPlaceCrnt) is greater than PermCrnt(InxPermCrnt). It will
        ' be the next in sequence unless there is PermCrnt(X) such that
        ' PermCrnt(InxPermCrnt) < PermCrnt(X) < ToPlace(InxToPlaceCrnt)
        If InxToPlaceNext = -1 Then
          ' This is the first ToPlace entry found that is greater than
          ' PermCrnt(InxPermCrnt)
          ValueNext = ToPlace(InxToPlaceCrnt)
          InxToPlaceNext = InxToPlaceCrnt
        Else
          ' This is not the first ToPlace value greater than PermCrnt(InxPermCrnt)
          If ValueNext > ToPlace(InxToPlaceCrnt) Then
            ValueNext = ToPlace(InxToPlaceCrnt)
            InxToPlaceNext = InxToPlaceCrnt
          End If
        End If
      End If
    Next
    ' If stop here, next value in sequence not found
    Debug.Assert ValueNext <> PermCrnt(InxPermCrnt)
    ' Place next value in PermCrnt() and remove from ToPlace()
    PermCrnt(InxPermCrnt) = ValueNext
    ToPlace(InxToPlaceNext) = ToPlace(InxToPlaceMax)
    InxToPlaceMax = InxToPlaceMax - 1
    ' Move remaining values in ToPlace() to PermCrnt() in ascending sequence
    Do While InxToPlaceMax > 0
      InxPermCrnt = InxPermCrnt + 1  ' Next position within PermCrnt
      ' Find next value to place
      ValueNext = ToPlace(1)
      InxToPlaceNext = 1
      For InxToPlaceCrnt = 2 To InxToPlaceMax
        If ValueNext > ToPlace(InxToPlaceCrnt) Then
          ValueNext = ToPlace(InxToPlaceCrnt)
          InxToPlaceNext = InxToPlaceCrnt
        End If
      Next
      ' Place next value in PermCrnt() and remove from ToPlace()
      PermCrnt(InxPermCrnt) = ValueNext
      ToPlace(InxToPlaceNext) = ToPlace(InxToPlaceMax)
      InxToPlaceMax = InxToPlaceMax - 1
    Loop  ' until all values in ToPlace() copied to PermCrnt()
  Loop  ' until Permutations() is full

End Sub
Function Factorial(ByVal Num As Long)

  ' Return Fsctorial Num

  '  6Jun19  Coded

  Dim Answer As Long
  Dim I As Long

  Answer = 1
  For I = 1 To Num
    Answer = Answer * I
  Next I
  Factorial = Answer

End Function
Public Function PadL(ByVal Str As String, ByVal PadLen As Long, _
                     Optional ByVal PadChr As String = " ") As String

  ' Pad Str with leading PadChr to give a total length of PadLen
  ' If the length of Str exceeds PadLen, Str will not be truncated

  '   Sep15 Coded
  ' 20Dec15 Added code so overlength strings are not truncated
  ' 10Jun16 Added PadChr so could pad with characters other than space

  If Len(Str) >= PadLen Then
    ' Do not truncate over length strings
    PadL = Str
  Else
    PadL = Right$(String(PadLen, PadChr) & Str, PadLen)
  End If

End Function
Public Function PadR(ByVal Str As String, ByVal PadLen As Long, _
                     Optional ByVal PadChr As String = " ") As String

  ' Pad Str with trailing PadChr to give a total length of PadLen
  ' If the length of Str exceeds PadLen, Str will not be truncated

  '   Nov15 Coded
  ' 15Sep16 Added PadChr so could pad with characters other than space

  If Len(Str) >= PadLen Then
    ' Do not truncate over length strings
    PadR = Str
  Else
    PadR = Left$(Str & String(PadLen, PadChr), PadLen)
  End If

End Function

How to get all permutations of a list taken k things at at a time using a user defined recursive function(Python)

Since the function returns a nested list, I've tried to convert the nested list to a set of tuples.

Yes, that is indeed what is needed. So Perm should yield tuples.

Here is a possible recursive implementation for Perm:

def Perm(lst, size):
    if size <= 0:
        yield ()   # empty tuple
    else:
        for i, val in enumerate(lst):
            for p in Perm(lst[:i] + lst[i+1:], size-1):
                yield (val, *p)

This passes the test given in the question.

Get all permutations of a list in python without duplicates?

You can use combinations and permutations together. This should be able to get you going

a = ["ab", "ls", "u"]
for i in range(1, len(a)+1):
    for comb in combinations(a, i):
        for perm in permutations(comb):
            print(perm)

Output:

('ab',)
('ls',)
('u',)
('ab', 'ls')
('ls', 'ab')
('ab', 'u')
('u', 'ab')
('ls', 'u')
('u', 'ls')
('ab', 'ls', 'u')
('ab', 'u', 'ls')
('ls', 'ab', 'u')
('ls', 'u', 'ab')
('u', 'ab', 'ls')
('u', 'ls', 'ab')

You can handle comb how ever you see fit

How do I generate permutations of length LEN given a list of N Items?

itertools.permutations(my_list, 3)

---

Related Topics