How to generate all permutations of a list

Question

How do you generate all the permutations of a list in Python  independently of the type of elements in that list   For example   permutations         permutations  1    1   permutations  1  2    1  2   2  1   permutations  1  2  3    1  2  3   1  3  2   2  1  3   2  3  1   3  1  2   3  2  1

User · Answer

ANOTHER APPROACH  without libs   def permutation input       if len input     1          return input if isinstance input  list  else  input       result          for i in range len input            first   input i          rest   input  i    input i   1           rest permutation   permutation rest          for p in rest permutation              result append first   p      return result   Input can be a string or a list  print permutation  abcd    print permutation   a    b    c    d

User · Answer

usr bin env python  def perm a  k 0      if k    len a         print a    else        for i in xrange k  len a             a k   a i    a i   a k           perm a  k 1           a k   a i    a i   a k   perm  1 2 3     Output    1  2  3   1  3  2   2  1  3   2  3  1   3  2  1   3  1  2    As I m swapping the content of the list it s required a mutable sequence type as input  E g  perm list  ball    will work and perm  ball   won t because you can t change a string    This Python implementation is inspired by the algorithm presented in the book Computer Algorithms by Horowitz  Sahni and Rajasekeran

User · Answer

And in Python 2 6 onwards   import itertools itertools permutations  1 2 3      returned as a generator   Use list permutations l   to return as a list

User · Answer

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

User · Answer

Disclaimer  shapeless plug by package author      The trotter package is different from most implementations in that it generates pseudo lists that don t actually contain permutations but rather describe mappings between permutations and respective positions in an ordering  making it possible to work with very large  lists  of permutations  as shown in this demo which performs pretty instantaneous operations and look-ups in a pseudo-list  containing  all the permutations of the letters in the alphabet  without using more memory or processing than a typical web page    In any case  to generate a list of permutations  we can do the following   import trotter  my permutations   trotter Permutations 3   1  2  3    print my permutations   for p in my permutations      print p    Output    A pseudo-list containing 6 3-permutations of  1  2  3    1  2  3   1  3  2   3  1  2   3  2  1   2  3  1   2  1  3

User · Answer

My Python Solution   def permutes input offset       if  len input     offset            return     join input        result                for i in range  offset  len input              input offset   input i    input i   input offset           result   result   permutes input offset 1           input offset   input i    input i   input offset      return result    input is a  string    return value is a list of strings def permutations input       return permutes  list input   0      Main Program print  permutations  wxyz

User · Answer

This algorithm is the most effective one  it avoids of array passing and manipulation in recursive calls  works in Python 2  3   def permute items       length   len items      def inner ix              do yield   len ix     length - 1         for i in range 0  length               if i in ix   avoid duplicates                 continue             if do yield                  yield tuple  items y  for y in ix    i                else                  for p in inner ix    i                        yield p     return inner     Usage   for p in permute  1 2 3        print p    1  2  3   1  3  2   2  1  3   2  3  1   3  1  2   3  2  1

User · Answer

Using Counter  from collections import Counter  def permutations nums       ans            cache   Counter nums       for idx  x in enumerate nums           result              for items in ans              cache1   Counter items              for id  n in enumerate nums                   if cache n     cache1 n  and items    n  not in result                      result append items    n            ans   result     return ans permutations  1  2  2    gt    1  2  2    2  1  2    2  2  1

User · Answer

list2Perm    1  2 0   three   listPerm     a  b  c              for a in list2Perm             for b in list2Perm             for c in list2Perm             if   a    b and b    c and a    c                 print listPerm   Output          1  2 0   three          1   three   2 0         2 0  1   three          2 0   three   1          three   1  2 0          three   2 0  1

User · Answer

def permuteArray  arr        arraySize   len arr       permutedList           if arraySize    1          return  arr       i   0      for item in arr           for elem in permuteArray arr  i    arr i   1                 permutedList append  item    elem           i   i   1          return permutedList   I intended to not exhaust every possibility in a new line to make it somewhat unique

User · Answer

Note that this algorithm has an n factorial time complexity  where n is the length of the input list  Print the results on the run   global result result        def permutation li   if li       or li    None      return  if len li     1      result append li 0       print result     result pop       return  for i in range 0 len li        result append li i       permutation li  i    li i 1        result pop         Example    permutation  1 2 3     Output    1  2  3   1  3  2   2  1  3   2  3  1   3  1  2   3  2  1

User · Answer

I used an algorithm based on the factorial number system- For a list of length n  you can assemble each permutation item by item  selecting from the items left at each stage  You have n choices for the first item  n-1 for the second  and only one for the last  so you can use the digits of a number in the factorial number system as the indices  This way the numbers 0 through n -1 correspond to all possible permutations in lexicographic order   from math import factorial def permutations l       permutations        length len l      for x in xrange factorial length            available list l          newPermutation            for radix in xrange length  0  -1               placeValue factorial radix-1              index x placeValue             newPermutation append available pop index               x- index placeValue         permutations append newPermutation      return permutations  permutations range 3     output     0  1  2    0  2  1    1  0  2    1  2  0    2  0  1    2  1  0     This method is non-recursive  but it is slightly slower on my computer and xrange raises an error when n  is too large to be converted to a C long integer  n 13 for me   It was enough when I needed it  but it s no itertools permutations by a long shot

User · Answer

from typing import List import time  random  def measure time func       def wrapper time  args    kwargs           start time   time perf counter           res   func  args    kwargs          end time   time perf counter           return res  end time - start time      return wrapper time   class Solution      def permute self  nums  List int   method  int   1  - gt  List List int            perms              perm              if method    1                 time perm   self  permute recur nums  0  len nums  - 1  perms          elif method    2                 time perm   self  permute recur agian nums  perm  perms              print perm          return perms  time perm       measure time     def  permute recur self  nums  List int   l  int  r  int  perms  List List int               base case         if l    r              perms append nums copy             for i in range l  r   1               nums l   nums i    nums i   nums l              self  permute recur nums  l   1  r   perms              nums l   nums i    nums i   nums l        measure time     def  permute recur agian self  nums  List int   perm  List int   perms list  List List int              quot  quot  quot          The idea is similar to nestedForLoops visualized as a recursion tree           quot  quot  quot          if nums              for i in range len nums                      perm append nums i    mistake  perm will be filled with all nums s elements                    Method1 perm copy   copy deepcopy perm                    Method2 add in the parameter list using    not in place                    caveat  list append is in-place   which is useful for operating on global element perms list                   Note that                    perms list pass by reference  shallow copy                   perm    nums i   pass by value instead of reference                  self  permute recur agian nums  i    nums i 1    perm    nums i    perms list          else                Arrive at the last loop  i e  leaf of the recursion tree              perms list append perm     if   name       quot   main   quot       array    random randint -10  10  for   in range 3       sol   Solution         perms  time perm   sol permute array  1      perms2  time perm2   sol permute array  2      print perms2        print perms  perms2        print time perm  time perm2

User · Answer

Another solution   def permutation flag  k  1        N   len flag      for i in xrange 0  N           if flag i     0              continue         flag i    k          if k    N              print flag         permutation flag  k 1          flag i    0  permutation  0  0  0

User · Answer

Generate all possible permutations  I m using python3 4   def calcperm arr  size       result   set           for dummy idx in range size           temp   set           for dummy lst in result              for dummy outcome in arr                  if dummy outcome not in dummy lst                      new seq   list dummy lst                      new seq append dummy outcome                      temp add tuple new seq           result   temp     return result   Test Cases   lst    1  2  3  4   lst     yellow    magenta    white    blue   seq   2 final   calcperm lst  seq  print len final   print final

User · Answer

This solution implements a generator  to avoid holding all the permutations on memory   def permutations  orig list       if not isinstance orig list  list           orig list   list orig list       yield orig list      if len orig list     1          return      for n in sorted orig list           new list   orig list            pos   new list index n          del new list pos           new list insert 0  n          for resto in permutations new list 1                 if new list  1    resto  lt  gt  orig list                  yield new list  1    resto

User · Answer

The beauty of recursion    gt  gt  gt  import copy  gt  gt  gt  def perm prefix rest            for e in rest                   new rest copy copy rest                   new prefix copy copy prefix                   new prefix append e                   new rest remove e                   if len new rest     0                           print new prefix   new rest                          continue                  perm new prefix new rest        gt  gt  gt  perm      a   b   c   d      a    b    c    d     a    b    d    c     a    c    b    d     a    c    d    b     a    d    b    c     a    d    c    b     b    a    c    d     b    a    d    c     b    c    a    d     b    c    d    a     b    d    a    c     b    d    c    a     c    a    b    d     c    a    d    b     c    b    a    d     c    b    d    a     c    d    a    b     c    d    b    a     d    a    b    c     d    a    c    b     d    b    a    c     d    b    c    a     d    c    a    b     d    c    b    a

User · Answer

for Python we can use itertools and import both permutations and combinations to solve your problem  from itertools import product  permutations A     1 2 3   print  list permutations sorted A  2

User · Answer

This is inspired by the Haskell implementation using list comprehension    def permutation list       if len list     0          return          else          return   x    ys for x in list for ys in permutation delete list  x     def delete list  item       lc   list        lc remove item      return lc

User · Answer

import java util Arrays   public class Permutation           runtime -O n  for generating nextPermutaion        and O n n   for generating all n  permutations with increasing sorted array as start        return true  if there exists next lexicographical sequence        e g  1 2 3  3- gt  true  modifies array to  1 3 2         e g  3 2 1  3- gt  false  as it is largest lexicographic possible        public static boolean nextPermutation int   seq  int len               1         if  len  lt   1              return false    no more perm            2  Find last j such that seq j   lt   seq j 1   Terminate if no such j exists         int j   len - 2          while  j  gt   0  amp  amp  seq j   gt   seq j   1                 --j                    if  j    -1              return false    no more perm            3  Find last l such that seq j   lt   seq l   then exchange elements j and l         int l   len - 1          while  seq j   gt   seq l                 --l                    swap seq  j  l              4  Reverse elements j 1     count-1          reverseSubArray seq  j   1  len - 1              return seq  add store next perm          return true            private static void swap int   a  int i  int j            int temp   a i           a i    a j           a j    temp             private static void reverseSubArray int   a  int lo  int hi            while  lo  lt  hi                swap a  lo  hi                 lo              --hi                      public static void main String   args            int   array    1 2 3 4 5 6 7           int cnt 0          do               System out println Arrays toString array                cnt             while nextPermutation array  array length            System out println cnt    5040 7            Algorithm for generating all permutations Java   It generates the next lexicographic sequence  modifies the array in place

User · Answer

For performance  a numpy solution inspired by Knuth   p22     from numpy import empty  uint8 from math import factorial  def perms n       f   1     p   empty  2 n-1  factorial n    uint8      for i in range n           p i   f    i         p i 1 2 i 1   f    p  i   f     constitution de blocs         for j in range i               p  i 1  f  j 1  f  j 2     p j 1 j i 2   f     copie de blocs         f   f  i 1      return p  n       Copying large blocs of memory saves time -  it s  20x faster than list itertools permutations range n      In  1    timeit -n10 list permutations range 10    10 loops  best of 3  815 ms per loop  In  2    timeit -n100 perms 10   100 loops  best of 3  40 ms per loop

User · Answer

Regular implementation  no yield - will do everything in memory    def getPermutations array       if len array     1          return  array      permutations          for i in range len array               get all perm s of subarray w o current item         perms   getPermutations array  i    array i 1              for p in perms              permutations append  array i    p       return permutations   Yield implementation   def getPermutations array       if len array     1          yield array     else          for i in range len array                perms   getPermutations array  i    array i 1                for p in perms                  yield  array i    p    The basic idea is to go over all the elements in the array for the 1st position  and then in 2nd position go over all the rest of the elements without the chosen element for the 1st  etc  You can do this with recursion  where the stop criteria is getting to an array of 1 element - in which case you return that array

User · Answer

To save you folks possible hours of searching and experimenting  here s the non-recursive permutaions solution in Python which also works with Numba  as of v  0 41     numba njit   def permutations A  k       r     i for i in range 0        for i in range k           r     a    b for a in A for b in r if  a in b   False      return r permutations  1 2 3  3    1  2  3    1  3  2    2  1  3    2  3  1    3  1  2    3  2  1     To give an impression about performance    timeit permutations np arange 5  5   243   s    11 1   s per loop  mean    std  dev  of 7 runs  1 loop each  time  406 ms   timeit list itertools permutations np arange 5  5   15 9   s    8 61 ns per loop  mean    std  dev  of 7 runs  100000 loops each  time  12 9 s   So use this version only if you have to call it from njitted function  otherwise prefer itertools implementation

User · Answer

in case anyone fancies this ugly one-liner  works only for strings though   def p a       return a if len a     1 else   a i    j  for i in range len a   for j in p a  i    a i   1

User · Answer

Anyway we could use sympy library   also support for multiset permutations import sympy from sympy utilities iterables import multiset permutations t    1 2 3  p   list multiset permutations t   print p       1  2  3    1  3  2    2  1  3    2  3  1    3  1  2    3  2  1    Answer is highly inspired by Get all permutations of a numpy array

User · Answer

There s a function in the standard-library for this  itertools permutations  import itertools list 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   lt  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  -- gt  AB AC AD BA BC BD CA CB CD DA DB DC       permutations range 3   -- gt  012 021 102 120 201 210     pool   tuple iterable      n   len pool      r   n if r is None else r     if r  gt  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

User · Answer

In a functional style  def addperm x l       return   l 0 i     x    l i    for i in range len l  1     def perm l       if len l     0          return          return  x for y in perm l 1    for x in addperm l 0  y     print perm   i for i in range 3      The result     0  1  2    1  0  2    1  2  0    0  2  1    2  0  1    2  1  0

User · Answer

One can indeed iterate over the first element of each permutation  as in tzwenn s answer  It is however more efficient to write this solution this way   def all perms elements       if len elements   lt   1          yield elements    Only permutation possible   no permutation     else            Iteration over the first element in the result permutation          for  index  first elmt  in enumerate elements               other elmts   elements  index  elements index 1               for permutation in all perms other elmts                    yield  first elmt    permutation   This solution is about 30    faster  apparently thanks to the recursion ending at len elements   lt   1 instead of 0  It is also much more memory-efficient  as it uses a generator function  through yield   like in Riccardo Reyes s solution

User · Answer

A quite obvious way in my opinion might be also   def permutList l       if not l              return          res          for e in l              temp   l                temp remove e              res extend   e    r for r in permutList temp         return res

User · Answer

Here is an algorithm that works on a list without creating new intermediate lists similar to Ber s solution at https   stackoverflow com a 108651 184528    def permute xs  low 0       if low   1  gt   len xs           yield xs     else          for p in permute xs  low   1               yield p                 for i in range low   1  len xs                        xs low   xs i    xs i   xs low              for p in permute xs  low   1                   yield p                     xs low   xs i    xs i   xs low   for p in permute  1  2  3  4        print p   You can try the code out for yourself here  http   repl it J9v

User · Answer

from   future   import print function  def perm n       p          for i in range 0 n 1           p append i      while True          for i in range 1 n 1               print p i   end              print             i   n - 1         found   0         while  not found and i gt 0               if p i  lt p i 1                   found   1             else                  i   i - 1         k   n         while p i  gt p k               k   k - 1         aux   p i          p i    p k          p k    aux         for j in range 1  n-i  2 1               aux   p i j              p i j    p n-j 1              p n-j 1    aux         if not found              break  perm 5

User · Answer

def permutations head  tail          if len head     0          print tail      else          for i in range len head                permutations head  i    head i 1    tail   head i    called as  permutations  abc

User · Answer

The following code is an in-place permutation of a given list  implemented as a generator  Since it only returns references to the list  the list should not be modified outside the generator  The solution is non-recursive  so uses low memory  Work well also with multiple copies of elements in the input list   def permute in place a       a sort       yield list a       if len a   lt   1          return      first   0     last   len a      while 1          i   last - 1          while 1              i   i - 1             if a i   lt  a i 1                   j   last - 1                 while not  a i   lt  a j                        j   j - 1                 a i   a j    a j   a i    swap the values                 r   a i 1 last                  r reverse                   a i 1 last    r                 yield list a                  break             if i    first                  a reverse                   return  if   name         main         for n in range 5           for a in permute in place range 1  n 1                print a         print      for a in permute in place  0  0  1  1  1            print a     print

User · Answer

def permutation word  first char None       if word    None or len word     0  return        if len word     1  return  word       result          first char   word 0      for sub word in permutation word 1    first char           result    insert first char  sub word      return sorted result   def insert ch  sub word       arr    ch   sub word      for i in range len sub word            arr append sub word i     ch   sub word  i       return arr   assert permutation None        assert permutation           assert permutation  1         1   assert permutation  12        12    21    print permutation  abc     Output    abc    acb    bac    bca    cab    cba

User · Answer

I see a lot of iteration going on inside these recursive functions  not exactly pure recursion     so for those of you who cannot abide by even a single loop  here s a gross  totally unnecessary fully recursive solution  def all insert x  e  i 0       return  x 0 i   e  x i      all insert x e i 1  if i lt len x  1 else     def for each X  e       return all insert X 0   e    for each X 1   e  if X else     def permute x       return  x  if len x   lt  2 else for each  permute x 1      x 0     perms   permute  1 2 3

User · Answer

def pzip c  seq       result          for item in seq          for i in range len item  1               result append item i   c item  i       return result   def perm line       seq    c for c in line      if len seq   lt  1           return seq     else          return pzip seq 0   perm seq 1

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

Examples related to python

Examples related to algorithm

Examples related to permutation

Examples related to combinatorics

Examples related to python-2.5