Generating All Possible Permutations of a List Recursively

Generating all possible permutations of a list recursively

If allPossibleItems contains two different elements, x and y, then you successively write x and y to the list until it reaches DESIRED_SIZE. Is that what you really want? If you pick DESIRED_SIZE sufficiently large, you will have too many recursive calls on the stack, hence the SO exception.

What I'd do (if original has no douplets / duplicates) is:

public <E> List<List<E>> generatePerm(List<E> original) {
  if (original.isEmpty()) {
    List<List<E>> result = new ArrayList<>();
    result.add(new ArrayList<>());
    return result;
  }
  E firstElement = original.remove(0);
  List<List<E>> returnValue = new ArrayList<>();
  List<List<E>> permutations = generatePerm(original);
  for (List<E> smallerPermutated : permutations) {
    for (int index = 0; index <= smallerPermutated.size(); index++) {
      List<E> temp = new ArrayList<>(smallerPermutated);
      temp.add(index, firstElement);
      returnValue.add(temp);
    }
  }
  return returnValue;
}

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)

Recursive function to generate permutations correctly prints each permutation but can not add it to a list

You append perm to permutations then remove the elements in perm using pop(). This will remove those in permutations as it is not a copy of perm that is present in permutations but it is a reference to perm itself.

The concept of references, is similar to pointers in C.

object_1 = object_2

saves a reference of object_2 to object_1 not a copy so any change in object_2 will reflect in object_1

use copy.deepcopy() to copy the list perm

Working code:

import copy
permutations = []

def generate_permutations(n, perm=[]):
    """
    Recursive function to print all possible permutations of integers in range n.
    :param perm: list representing a single permutation of integers in range(n)
    :param n: end of range(n) and length of each permutation
    """
    # base case: when a permutation reaches its full length, print it and move on:
    if len(perm) == n:
        print(perm)
        permutations.append(copy.deepcopy(perm))  
        return
    # recursive case:
    for k in range(n):
        # if number k not already in the permutation, add it, generate permutations, and
        # then remove k so a new set of permutations can be generated.
        if k not in perm:
            perm.append(k)
            generate_permutations(n, perm)
            perm.pop()

generate_permutations(3)
print(permutations)

Output:

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

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)

How to recursively create a list of permutations in python?

After some coding I have come up with a recursive solution. You can either use itertools.product or the functions below.

def rec_permutations(possibilities):
    counter = 0
    permutations_list=[]
    lst=[]
    return rec_permutations_helper(possibilities, permutations_list, counter, lst)

def rec_permutations_helper(possibilities, permutations_list, counter, lst):
    # Base case
    if counter == len(possibilities):
        permutations_list.append(lst)
        return
    # Recursive case
    else:
        locations = possibilities[counter]
        for location in locations:
            new_lst = lst + [location]      
            rec_permutations_helper(possibilities, permutations_list, counter+1, new_lst)

    return permutations_list

how to permute n elements from list recursively in python?

This isn't sort of like cartesian product; it's exactly like cartesian product.

>>> from itertools import product
>>> list(product([0,1,5], repeat=2))
[(0, 0), (0, 1), (0, 5), (1, 0), (1, 1), (1, 5), (5, 0), (5, 1), (5, 5)]
>>> list(product([2,3], repeat=3))
[(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3, 3, 2), (3, 3, 3)]

The polyfill for itertools.product is the following:

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

But since you can't use itertools, you might as well take the liberty of writing a slightly more efficient solution to your problem. Since we are just computing the product of n identical iterables, let's just call it a cartesian exponent:

def cartesian_exponent(li, e=1):
    pools = [li] * e
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    return result

Or recursively using yet another incomprehensible list comprehension:

def cartesian_exponent(li, e=1):
    if e == 1:
        return [[x] for x in li]
    else:
        return [[x]+y for x in li for y in cartesian_exponent(li, e=e-1)]

Which can be compressed to one line:

def cartesian_exponent(li, e=1):
    return [[x] for x in li] if e == 1 else [[x] + y for x in li for y in cartesian_exponent(li, e=e-1)]

But then you would be sacrificing readability for terseness and that's no bueno. The incomprehensible list comprehension is already opaque enough.

Some tests:

>>> cartesian_exponent([0,1,5], e=2)
[[0, 0], [0, 1], [0, 5], [1, 0], [1, 1], [1, 5], [5, 0], [5, 1], [5, 5]]
>>> cartesian_exponent([2,3], e=3)
[[2, 2, 2], [2, 2, 3], [2, 3, 2], [2, 3, 3], [3, 2, 2], [3, 2, 3], [3, 3, 2], [3, 3, 3]]

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.

---

Related Topics