Algorithm to generate all possible permutations of a list

Question

Say I have a list of n elements  I know there are n  possible ways to order these elements  What is an algorithm to generate all possible orderings of this list  Example  I have list  a  b  c   The algorithm would return   a  b  c    a  c  b     b  a  c    b  c  a    c  a  b    c  b  a     I m reading this here http   en wikipedia org wiki Permutation Algorithms to generate permutations  But Wikipedia has never been good at explaining  I don t understand much of it

User · Answer

Bourne shell solution - in a total of four lines  without test for no param case    test    -eq 1  amp  amp  echo   1   amp  amp  exit for i in     do    0  echo        sed -e  s  i       sed -e  s    i    done

User · Answer

Here is a non-recursive solution in C   that provides the next permutation in ascending order  similarly to the functionality provided by std  next permutation   void permute next vector lt int gt  amp  v      if  v size    lt  2      return     if  v size      2           int tmp   v 0       v 0    v 1       v 1    tmp      return            Step 1  find first ascending-ordered pair from right to left   int i   v size  -2    while i gt  0           if  v i   lt  v i 1         break      i--        if  i lt 0     vector fully sorted in descending order  last permutation            resort in ascending order and return     sort v begin    v end         return            Step 2  swap v i  with next higher element of remaining elements   int pos   i 1    int val   v pos     for int k i 2  k lt v size    k        if v k   lt  val  amp  amp  v k   gt  v i               pos   k        val   v k           v pos    v i     v i    val        Step 3  sort remaining elements from i 1     end   sort v begin   i 1  v end

User · Answer

This produces them one-at-time without making a list - the same end result as Marios Choudary s answer  or simply calling C   s nextPermute  as Anders answer notes   But this is Heap s algorithm  the non-recursive version  re-arranged and a class to save context  Used as   P5 new genPermutes t 5      P5 P is now  0 1 2 3 4  while  P5 isDone           use P5 P here   P5 next        Code is in C  without being an endorsement  Variables are as-is from Heap s pseudocode  to which the comments also refer   public class genPermutes t     public int   P     the current permuation    private int n  i     vars from the original algorithm   private int   c     ditto    public genPermutes t int count           init algorithm      n count      i 0      c new int n       for int j 0 j lt n j    c j  0          start current permutation as 0 1     n-1      P new int n       for int j 0 j lt n j    P j  j         public bool isDone         return i gt  n     condition on the original while loop        public void next            the part of the loop that spins until done or ready for next permute      while i lt n  amp  amp  c i  gt  i          c i  0        i                 pulled from inside loop -- the part that makes next permute      if i lt n       if not done       if i 2  0  swap 0 i         else swap c i   i             print P  removed  User will simply examine it       c i   1        i 0               private void swap int i1  int i2   int tmp P i1   P i1  P i2   P i2  tmp

User · Answer

If anyone wonders how to be done in permutation in javascript   Idea pseudocode   pick one element at a time permute rest of the element and then add the picked element to the all of the permutation   for example   a   permute bc   permute of bc would be bc  amp  cb  Now add these two will give abc  acb  similarly  pick b   permute  ac  will provice bac  bca   and keep going   now look at the code  function permutations arr       var len   arr length          perms              rest         picked         restPerms         next         for one or less item there is only one permutation      if  len  lt   1          return  arr        for  var i 0  i lt len  i                    copy original array to avoid changing it while picking elements         rest   Object create arr              splice removed element change array original array copied array             1 2 3 4  splice 2 1  will return  3  and remaining array    1 2 4          picked   rest splice i  1              get the permutation of the rest of the elements         restPerms   permutations rest              Now concat like a permute bc  for each        for  var j 0  j lt restPerms length  j                        next   picked concat restPerms j               perms push next                      return perms      Take your time to understand this  I got this code from  pertumation in JavaScript

User · Answer

I have written this recursive solution in ANSI C  Each execution of the Permutate function provides one different permutation until all are completed  Global variables can also be used for variables fact and count    include  lt stdio h gt   define SIZE 4  void Rotate int vec    int size        int i  j  first       first   vec 0       for j   0  i   1  i  lt  size  i    j                  vec j    vec i             vec j    first     int Permutate int  start  int size  int  count        static int fact       if size  gt  1                if Permutate start   1  size - 1  count                         Rotate start  size                     fact    size            else                 count             fact   1             return    count   fact      void Show int vec    int size        int i       printf   d   vec 0        for i   1  i  lt  size  i                  printf    d   vec i              putchar   n       int main         int vec       1  2  3  4  5  6       Only the first SIZE items will be permutated        int count   0       do               Show vec  SIZE         while  Permutate vec  SIZE   amp count         putchar   n        Show vec  SIZE       printf   nCount   d n n   count        return 0

User · Answer

this is a java version for permutation  public class Permutation        static void permute String str            permute str toCharArray    0  str length                static void permute char    str  int low  int high            if  low    high                System out println str               return                     for  int i low  i lt high  i                  swap str  i  low               permute str  low 1  high               swap str  low  i                         static void swap char    array  int i  int j            char t   array i           array i    array j           array j    t

User · Answer

Java version          param uniqueList     param permutationSize     param permutation     param only            Only show the permutation of permutationSize                            else show all permutation of less than or equal to permutationSize      public static void my permutationOf List lt Integer gt  uniqueList  int permutationSize  List lt Integer gt  permutation  boolean only        if  permutation    null            assert 0  lt  permutationSize  amp  amp  permutationSize  lt   uniqueList size            permutation   new ArrayList lt  gt  permutationSize           if   only                System out println Arrays toString permutation toArray                          for  int i   uniqueList            if  permutation contains i                 continue                    permutation add i           if   only                System out println Arrays toString permutation toArray                else if  permutation size      permutationSize                System out println Arrays toString permutation toArray                        if  permutation size    lt  permutationSize                my permutationOf uniqueList  permutationSize  permutation  only                     permutation remove permutation size   - 1             E g    public static void main String   args  throws Exception        my permutationOf new ArrayList lt Integer gt                            add 1               add 2               add 3                     3  null  true       output       1  2  3     1  3  2     2  1  3     2  3  1     3  1  2     3  2  1

User · Answer

As WhirlWind said  you start at the beginning    You swap cursor with each remaining value  including cursor itself  these are all new instances  I used an int   and array clone   in the example    Then perform permutations on all these different lists  making sure the cursor is one to the right   When there are no more remaining values  cursor is at the end   print the list  This is the stop condition     public void permutate int   list  int pointer        if  pointer    list length              stop-condition  print or process number         return            for  int i   pointer  i  lt  list length  i              int   permutation    int   list clone             permutation pointer    list i           permutation i    list pointer           permutate permutation  pointer   1

User · Answer

Recursive always takes some mental effort to maintain  And for big numbers  factorial is easily huge and stack overflow will easily be a problem   For small numbers  3 or 4  which is mostly encountered   multiple loops are quite simple and straight forward  It is unfortunate answers with loops didn t get voted up   Let s start with enumeration  rather than permutation   Simply read the code as pseudo perl code    foreach  i1 in  list      foreach  i2 in  list           foreach  i3 in  list             print   i1   i2   i3 n    Enumeration is more often encountered than permutation  but if permutation is needed  just add the conditions    foreach  i1 in  list      foreach  i2 in  list           if  i2   i1             next          foreach  i3 in  list              if  i3   i1 or  i3   i2                 next             print   i1   i2   i3 n    Now if you really need general method potentially for big lists  we can use radix method  First  consider the enumeration problem    n  list my  radix  for  i 0  n      radix  i  0  while 1     my  temp      for  i 0  n         push  temp   list  radix  i       print join        temp     n       call radix increment  subcode  radix increment      i 0      while 1          radix  i             if  radix  i    n              radix  i  0              i            else             last      if  i gt   n         last   Radix increment is essentially number counting  in the base of number of list elements    Now if you need permutaion  just add the checks inside the loop   subcode  check permutation     my  check     my  flag dup 0      for  i 0  n          check  radix  i              if  check  radix  i   gt 1              flag dup 1             last      if  flag dup         next   Edit  The above code should work  but for permutation  radix increment could be wasteful  So if time is a practical concern  we have to change radix increment into permute inc   subcode  permute init      for  i 0  n          radix  i   i  subcode  permute inc                                             max -1                                                      for  i  n 0                                                     if  max lt  radix  i                                               max  radix  i                                           else                                                            for  j  n 0                                                     if  radix  j  gt  radix  i                                         call swap   radix  i    radix  j                           break                                                j  i 1                                                      k  n-1                                                      while  j lt  k                                                     call swap   radix  j    radix  k                            j                                                           k--                                                    break                                                if  i lt 0                                                        break                                                 Of course now this code is logically more complex  I ll leave for reader s exercise

User · Answer

It s my solution on Java   public class CombinatorialUtils        public static void main String   args            List lt String gt  alphabet   new ArrayList lt  gt             alphabet add  1            alphabet add  2            alphabet add  3            alphabet add  4             for  List lt String gt  strings   permutations alphabet                 System out println strings                     System out println  -----------            for  List lt String gt  strings   combinations alphabet                 System out println strings                        public static List lt List lt String gt  gt  combinations List lt String gt  alphabet            List lt List lt String gt  gt  permutations   permutations alphabet           List lt List lt String gt  gt  combinations   new ArrayList lt  gt  permutations            for  int i   alphabet size    i  gt  0  i--                final int n   i              combinations addAll permutations stream   map strings - gt  strings subList 0  n   distinct   collect Collectors toList                        return combinations             public static  lt T gt  List lt List lt T gt  gt  permutations List lt T gt  alphabet            ArrayList lt List lt T gt  gt  permutations   new ArrayList lt  gt             if  alphabet size      1                permutations add alphabet               return permutations            else               List lt List lt T gt  gt  subPerm   permutations alphabet subList 1  alphabet size                  T addedElem   alphabet get 0               for  int i   0  i  lt  alphabet size    i                      for  List lt T gt  permutation   subPerm                        int index   i                      permutations add new ArrayList lt T gt  permutation                             add index  addedElem                                                                              return permutations

User · Answer

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

User · Answer

Just to be complete  C     include  lt iostream gt   include  lt algorithm gt   include  lt string gt   std  string theSeq    abc   do     std  cout  lt  lt  theSeq  lt  lt  endl     while  std  next permutation theSeq begin    theSeq end             abc acb bac bca cab cba

User · Answer

Here is a recursive solution in PHP  WhirlWind s post accurately describes the logic  It s worth mentioning that generating all permutations runs in factorial time  so it might be a good idea to use an iterative approach instead    public function permute  sofar   input     for  i 0   i  lt  strlen  input    i          diff   strDiff  input  input  i         next    sofar  input  i     next contains a permutation  save it      this- gt permute  next   diff           The strDiff function takes two strings  s1 and s2  and returns a new string with everything in s1 without elements in s2  duplicates matter   So  strDiff  finish   i       fnish   the second  i  is not removed

User · Answer

Here is an algorithm in R  in case anyone needs to avoid loading additional libraries like I had to   permutations  lt - function n       if n  1           return matrix 1         else           sp  lt - permutations n-1          p  lt - nrow sp          A  lt - matrix nrow n p ncol n          for i in 1 n               A  i-1  p 1 p    lt - cbind i sp  sp gt  i                     return A            Example usage    gt  matrix letters permutations 3   ncol 3         1    2    3   1    a    b    c    2    a    c    b    3    b    a    c    4    b    c    a    5    c    a    b    6    c    b    a

User · Answer

in PHP   set array  A   B   C   D     function permutate  set         b array        foreach  set as  key  gt  value            if count  set   1                 b    set  key                     else                subset  set              unset  subset  key                 x permutate  subset               foreach  x as  key1  gt  value1                     b    value      value1                                    return  b      x permutate  set   var export  x

User · Answer

Wikipedia s answer for  lexicographic order  seems perfectly explicit in cookbook style to me  It cites a 14th century origin for the algorithm   I ve just written a quick implementation in Java of Wikipedia s algorithm as a check and it was no trouble  But what you have in your Q as an example is NOT  list all permutations   but  a LIST of all permutations   so wikipedia won t be a lot of help to you  You need a language in which lists of permutations are feasibly constructed  And believe me  lists a few billion long are not usually handled in imperative languages  You really want a non-strict functional programming language  in which lists are a first-class object  to get out stuff while not bringing the machine close to heat death of the Universe   That s easy  In standard Haskell or any modern FP language     -- perms of a list perms     a  - gt     a    perms  a as     bs    a cs   perm  lt - perms as   bs cs   lt - splits perm  perms                   and  -- ways of splitting a list into two parts splits     a  - gt      a   a     splits                      splits  a as        a as      a bs cs     bs cs   lt - splits as

User · Answer

Here is an algorithm in Python that works by in place on an array   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

There is already plenty of good solutions here  but I would like to share how I solved this problem on my own and hope that this might be helpful for somebody who would also like to derive his own solution   After some pondering about the problem I have come up with two following conclusions    For the list L of size n there will be equal number of solutions starting with L1  L2     Ln elements of the list  Since in total there are n  permutations of the list of size n  we get n    n    n-1   permutations in each group  The list of 2 elements has only 2 permutations     a b  and  b a      Using these two simple ideas I have derived the following algorithm   permute array     if array is of size 2        return first and second element as new array        return second and first element as new array     else         for each element in array             new subarray   array with excluded element             return element   permute subarray   Here is how I implemented this in C    public IEnumerable lt List lt T gt  gt  Permutate lt T gt  List lt T gt  input        if  input Count    2     this are permutations of array of size 2               yield return new List lt T gt  input           yield return new List lt T gt   input 1   input 0               else               foreach T elem in input     going through array                       var rlist   new List lt T gt  input      creating subarray   array             rlist Remove elem      removing element             foreach List lt T gt  retlist in Permutate rlist                                 retlist Insert 0 elem      inserting the element at pos 0                 yield return retlist

User · Answer

In C  create a single matrix  unsigned char  to quickly and easily access all permutations from 1 to 6  Based on code from https   www geeksforgeeks org heaps-algorithm-for-generating-permutations   void swap unsigned char  a  unsigned char  b        unsigned char t       t    b       b    a       a   t     void print permutations unsigned char a    unsigned char n           can t rely on sizeof a 6      6  such as with MSVC 2019     for  int i   0  i  lt  n  i                  assert a i   lt  n           printf  quot  d  quot   a i              printf  quot  n quot          Generating permutation using Heap Algorithm  void generate permutations unsigned char    permutations  6   unsigned char a    int size  int n           can t rely on sizeof a 6      6  such as with MSVC 2019        if size becomes 1 then prints the obtained permutation      if  size    1                memcpy  permutations  a  n            permutations    1            else               for  int i   0  i  lt  size  i                          generate permutations permutations  a  size - 1  n                   if size is odd  swap first and last element             if  size  amp  1                  swap a  a   size - 1                   If size is even  swap ith and last element             else                 swap a   i  a   size - 1                      int main         unsigned char permutations 720  6      easily access all permutations from 1 to 6     unsigned char suit length indexes       0  1  2  3  4  5        assert sizeof suit length indexes     sizeof permutations 0         unsigned char  p  sizeof suit length indexes     permutations      generate permutations  amp p  suit length indexes  sizeof suit length indexes   sizeof suit length indexes        for  int i   0  i  lt  sizeof permutations    sizeof permutations 0    i            print permutations permutations i   sizeof suit length indexes        return 0

User · Answer

Here s an implementation for ColdFusion  requires CF10 because of the merge argument to ArrayAppend       public array function permutateArray arr        if  not isArray arguments arr              return   The ARR argument passed to the permutateArray function is not of type array                    var len   arrayLen arguments arr       var perms           var rest           var restPerms           var rpLen   0      var next              for one or less item there is only one permutation      if  len  lt   1            return arguments arr             for  var i 1  i  lt   len  i                 copy the original array so as not to change it and then remove the picked  current  element         rest   arraySlice arguments arr  1           arrayDeleteAt rest  i                recursively get the permutation of the rest of the elements          restPerms   permutateArray rest            rpLen   arrayLen restPerms               Now concat each permutation to the current  picked  array  and append the concatenated array to the end result         for  var j 1  j  lt   rpLen  j                     for each array returned  we need to make a fresh copy of the picked current  element array so as to not change the original array             next   arraySlice arguments arr  i  1               arrayAppend next  restPerms j   true               arrayAppend perms  next                         return perms      Based on KhanSharp s js solution above

User · Answer

void permutate char   x  int i  int n       x x clone        if  i  n           System out print x           System out print               counter         else               for  int j i  j lt  n j               System out print temp   System out print            Debugger         swap  x i j             System out print temp   System out print      i   i   j   j   n      Debugger         permutate x i 1 n             swap  temp i j                  void swap  char   x  int a  int b   char temp   x a   x a  x b   x b  temp      I created this one  based on research too permutate qwe  0  qwe length-1   Just so you know  you can do it with or without backtrack

User · Answer

Here s a toy Ruby method that works like  permutation to a that might be more legible to crazy people  It s hella slow  but also 5 lines   def permute ary    return  ary  if ary size  lt   1   ary collect concat with index do  e  i      rest   ary dup tap   a  a delete at i        permute rest  collect   a  a unshift e      end end

User · Answer

In Scala      def permutazione n  List Int    List List Int     permutationeAcc n  Nil     def permutationeAcc n  List Int   acc  List Int    List List Int            var result  List List Int     Nil     for  i   n if    acc contains  i             if  acc size    n size-1              result    i    acc     result         else             result   result     permutationeAcc n  i    acc      result

User · Answer

Here is the code in Python to print all possible permutations of a list   def next perm arr         Find non-increasing suffix     i   len arr  - 1     while i  gt  0 and arr i - 1   gt   arr i           i -  1     if i  lt   0          return False        Find successor to pivot     j   len arr  - 1     while arr j   lt   arr i - 1           j -  1     arr i - 1   arr j    arr j   arr i - 1         Reverse suffix     arr i       arr len arr  - 1   i - 1   -1      print arr     return True  def all perm arr       a   next perm arr      while a          a   next perm arr      arr   raw input       arr split          arr   map int  arr      arr sort       print arr     all perm arr    I have used a lexicographic order algorithm to get all possible permutations  but a recursive algorithm is more efficient  You can find the code for recursive algorithm here  Python recursion permutations

User · Answer

the simplest way I can think to explain this is by using some pseudo code  so   list of 1  2  3 for each item in list     templist Add item      for each item2 in list         if item2 is Not item             templist add item                 for each item3 in list                    if item2 is Not item                       templist add item                      end if                Next             end if      Next     permanentListofPermutaitons add templist      tempList Clear   Next   Now obviously this is not the most flexible way to do this  and doing it recursively would be a lot more functional by my tired sunday night brain doesn t want to think about that at this moment  If no ones put up a recursive version by the morning I ll do one

User · Answer

You can t really talk about solving a permultation problem in recursion without posting an implementation in a  dialect of  language that pioneered the idea  So  for the sake of completeness  here is one of the ways that can be done in Scheme    define  permof wd     cond   null  wd                 null   cdr wd    list wd            else           let splice   l       m  car wd    r  cdr wd                append              map  lambda  x   cons m x    permof  append l r                 if  null  r                                       splice  cons m l   car r   cdr r           calling  permof  list  foo   bar   baz    we ll get       foo   bar   baz       foo   baz   bar       bar   foo   baz       bar   baz   foo       baz   bar   foo       baz   foo   bar      I won t go into the algorithm details because it s been explained enough in other posts  The idea is the same   However  recursive problems tend to be much harder to model and think about in destructive medium like Python  C  and Java  while in Lisp or ML it can be concisely expressed

User · Answer

usr bin env python import time  def permutations sequence       print sequence   unit    1  2  1  2  1     if len sequence   gt   4      for i in range 4   len sequence    1          unit     unit    i - 1     i   -1          print unit     for j in unit        temp   sequence j        sequence j    sequence 0        sequence 0    temp       yield sequence   else      print  You can use PEN and PAPER      s    1 2 3 4 5 6 7 8 9 10  s    x for x in  PYTHON    print s  z   permutations s  try    while True        time sleep 0 0001      print next z  except StopIteration      print  Done        P    Y    T    H    O    N     Y    P    T    H    O    N     T    P    Y    H    O    N     P    T    Y    H    O    N     Y    T    P    H    O    N     T    Y    P    H    O    N     H    Y    P    T    O    N     Y    H    P    T    O    N     P    H    Y    T    O    N     H    P    Y    T    O    N     Y    P    H    T    O    N     P    Y    H    T    O    N     T    Y    H    P    O    N     Y    T    H    P    O    N     H    T    Y    P    O    N     T    H    Y    P    O    N     Y    H    T    P    O    N     H    Y    T    P    O    N     P    Y    T    H    O    N           Y    T    N    H    O    P     N    T    Y    H    O    P     T    N    Y    H    O    P     Y    N    T    H    O    P     N    Y    T    H    O    P

User · Answer

I was thinking of writing a code for getting the permutations of any given integer of any size  i e   providing a number 4567 we get all possible permutations till 7654   So i worked on it and found an algorithm and finally implemented it  Here is the code written in  c   You can simply copy it and run on any open source compilers  But some flaws are waiting to be debugged  Please appreciate   Code     include  lt stdio h gt   include  lt conio h gt   include  lt malloc h gt                     PROTOTYPES  int fact int                      For finding the factorial void swap int  int                Swapping 2 given numbers void sort int  int                Sorting the list from the specified path int imax int  int int             Finding the value of imax int jsmall int  int               Gives position of element greater than ith but smaller than rest  ahead of imax  void perm                         All the important tasks are done in this function   int n                            Global variable for input OR number of digits  void main     int c 0   printf  Enter the number       scanf   d   amp c   perm c   getch       void perm int c   int  p                        Pointer for allocating separate memory to every single entered digit like arrays int i  d                 int sum 0  int j  k  long f   n   0   while c    0                  this one is for calculating the number of digits in the entered number       sum    sum   10     c   10       n                                 as i told at the start of loop     c   c   10     f   fact n                            It gives the factorial value of any number  p    int   malloc n sizeof int                     Dynamically allocation of array of n elements  for i 0  sum    0   i            p i    sum   10                                  Giving values in dynamic array like 1234    n separately     sum   sum   10     sort p -1                                             For sorting the dynamic array  p   for c 0   c lt f 2   c                               Most important loop which prints 2 numbers per loop  so it goes upto 1 2 of fact n       for k 0   k lt n   k            printf   d  p k                            Loop for printing one of permutations     printf   n         i   d   0      i   imax p i d                                provides the max i as per algo  i am restricted to this only      j   i      j   jsmall p j                                provides smallest i val as per algo     swap  amp p i   amp p j         for k 0   k lt n   k            printf   d  p k        printf   n         i   d   0      i   imax p i d       j   i      j   jsmall p j       swap  amp p i   amp p j         sort p i     free p                                            Deallocating memory    int fact  int a    long f 1  while a  0        f   f a      a--    return f      void swap int  p1 int  p2    int temp  temp    p1   p1    p2   p2   temp  return      void sort int p int t    int i temp j  for i t 1   i lt n-1   i          for j i 1   j lt n   j                  if   p i   gt    p j                         temp     p i                 p i      p j                 p j    temp                        int imax int  p  int i   int d        while i lt n-1  amp  amp  d lt n-1        if   p d   lt    p d 1                    i   d          d              else         d      return i      int jsmall int  p  int j    int i small   32767 k   j  for  i j 1   i lt n   i          if  p i  lt small  amp  amp  p i  gt p k                     small   p i          j   i          return j

User · Answer

I know this a very very old and even off-topic in today s stackoverflow but I still wanted to contribute a friendly javascript answer for the simple reason that it runs in your browser   I ve also added the debugger directive breakpoint so you can step through the code  chrome required  to see how this algorithm works  Open up your dev console in chrome  F12 in windows or CMD   OPTION   I on mac  and then click  Run code snippet   This implements the same exact algorithm that  WhirlWind presented in his answer   Your browser should pause execution at the debugger directive  Use F8 to continue code execution   Step through the code and see how it works    x000D   x000D  function permute rest  prefix         x000D    if  rest length     0    x000D      return  prefix   x000D      x000D    return  rest x000D       map  x  index    gt    x000D        const oldRest   rest  x000D        const oldPrefix   prefix  x000D           the       destructures the array into single values flattening it x000D        const newRest       rest slice 0  index      rest slice index   1    x000D        const newPrefix       prefix  x   x000D        debugger  x000D   x000D        const result   permute newRest  newPrefix   x000D        return result  x000D         x000D         this step flattens the array of arrays returned by calling permute x000D       reduce  flattened  arr    gt      flattened     arr       x000D       x000D    x000D  console log permute  1  2  3     x000D   x000D   x000D

User · Answer

In the following Java solution we take advantage over the fact that Strings are immutable in order to avoid cloning the result-set upon every iteration   The input will be a String  say  abc   and the output will be all the possible permutations   abc acb bac bca cba cab   Code   public static void permute String s        permute s  0      private static void permute String str  int left       if left    str length  -1            System out println str         else           for int i   left  i  lt  str length    i                  String s   swap str  left  i               permute s  left 1                      private static String swap String s  int left  int right        if  left    right          return s       String result   s substring 0  left       result    s substring right  right 1       result    s substring left 1  right       result    s substring left  left 1       result    s substring right 1       return result      Same approach can be applied to arrays  instead of a string    public static void main String   args        int   abc    1 2 3       permute abc  0     public static void permute int   arr  int index        if  index    arr length            System out println Arrays toString arr          else           for  int i   index  i  lt  arr length  i                  int   permutation   arr clone                permutation index    arr i               permutation i    arr index               permute permutation  index   1

User · Answer

public class PermutationGenerator       private LinkedList lt List lt int gt  gt   permutationsList      public void FindPermutations List lt int gt  list  int permutationLength                 permutationsList   new LinkedList lt List lt int gt  gt             foreach var value in list                        CreatePermutations value  permutationLength                        private void CreatePermutations int value  int permutationLength                var node    permutationsList First          var last    permutationsList Last          while  node    null                        if  node Value Count  lt  permutationLength                                GeneratePermutations node Value  value  permutationLength                             if  node    last                                break                            node   node Next                     List lt int gt  permutation   new List lt int gt             permutation Add value            permutationsList AddLast permutation              private void GeneratePermutations List lt int gt  permutation  int value  int permutationLength               if  permutation Count  lt  permutationLength                        List lt int gt  copyOfInitialPermutation   new List lt int gt  permutation               copyOfInitialPermutation Add value                permutationsList AddLast copyOfInitialPermutation               List lt int gt  copyOfPermutation   new List lt int gt                 copyOfPermutation AddRange copyOfInitialPermutation               int lastIndex   copyOfInitialPermutation Count - 1              for  int i   lastIndex i  gt  0 i--                                int temp   copyOfPermutation i - 1                   copyOfPermutation i - 1    copyOfPermutation i                   copyOfPermutation i    temp                   List lt int gt  perm   new List lt int gt                     perm AddRange copyOfPermutation                    permutationsList AddLast perm                                      public void PrintPermutations int permutationLength                int count    permutationsList Where perm   gt  perm Count      permutationLength  Count            Console WriteLine  The number of permutations is     count

User · Answer

Another one in Python  it s not in place as  cdiggins s  but I think it s easier to understand  def permute num       if len num     2            get the permutations of the last 2 numbers by swapping them         yield num         num 0   num 1    num 1   num 0          yield num     else          for i in range 0  len num                  fix the first number and get the permutations of the rest of numbers             for perm in permute num 0 i    num i 1 len num                     yield  num i     perm  for p in permute  1  2  3  4        print p

[algorithm] Algorithm to generate all possible permutations of a list?

Examples related to algorithm

Examples related to list

Examples related to permutation