How to generate all permutations of a list? How to generate all permutations of a list? python python

How to generate all permutations of a list?


There's a function in the standard-library for this: itertools.permutations.

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

If for some reason you want to implement it yourself or are just curious to know how it works, here's one nice approach, taken from http://code.activestate.com/recipes/252178/:

def all_perms(elements):    if len(elements) <=1:        yield elements    else:        for perm in all_perms(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)


And in Python 2.6 onwards:

import itertoolsitertools.permutations([1,2,3])

(returned as a generator. Use list(permutations(l)) to return as a list.)


The following code with Python 2.6 and above ONLY

First, import itertools:

import itertools

Permutation (order matters):

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

Combination (order does NOT matter):

print list(itertools.combinations('123', 2))[('1', '2'), ('1', '3'), ('2', '3')]

Cartesian product (with several iterables):

print list(itertools.product([1,2,3], [4,5,6]))[(1, 4), (1, 5), (1, 6),(2, 4), (2, 5), (2, 6),(3, 4), (3, 5), (3, 6)]

Cartesian product (with one iterable and itself):

print list(itertools.product([1,2], repeat=3))[(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2),(2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)]


matomo