Permutation of array

Question

For example I have this array   int a     new int   3 4 6 2 1     I need list of all permutations such that  if one is like this   3 2 1 4 6   others must not be the same  I know that if the length of the array is n then there are n  possible combinations  How can this algorithm be written   Update  thanks  but I need a pseudo code algorithm like   for int i 0 i lt a length i            code here     Just algorithm  Yes  API functions are good  but it does not help me too much

User · Answer

Do like this     import java util ArrayList  import java util Arrays   public class rohit        public static void main String   args            ArrayList lt Integer gt  a new ArrayList lt Integer gt             ArrayList lt Integer gt  b new ArrayList lt Integer gt             b add 1           b add 2           b add 3           permu a b              public static void permu ArrayList lt Integer gt  prefix ArrayList lt Integer gt  value            if value size    0                System out println prefix             else               for int i 0 i lt value size   i                      ArrayList lt Integer gt  a new ArrayList lt Integer gt                     a addAll prefix                   a add value get i                     ArrayList lt Integer gt  b new ArrayList lt Integer gt                      b addAll value subList 0  i                    b addAll value subList i 1  value size                       permu a b

User · Answer

Visual representation of the 3-item recursive solution   http   www docdroid net ea0s generatepermutations pdf html  Breakdown     For a two-item array  there are two permutations   The original array  and The two elements swapped  For a three-item array  there are six permutations   The permutations of the bottom two elements  then Swap 1st and 2nd items  and the permutations of the bottom two element  Swap 1st and 3rd items  and the permutations of the bottom two elements  Essentially  each of the items gets its chance at the first slot

User · Answer

Here is an implementation of the Permutation in Java   Permutation - Java  You should have a check on it   Edit  code pasted below to protect against link-death      Permute java -- A class generating all permutations  import java util Iterator  import java util NoSuchElementException  import java lang reflect Array   public class Permute implements Iterator       private final int size     private final Object    elements      copy of original 0    size-1    private final Object ar               array for output   0    size-1    private final int    permutation      perm of nums 1  size  perm 0  0     private boolean next   true         int    double   array won t work  -     public Permute  Object    e          size   e length        elements   new Object  size         not suitable for primitives       System arraycopy  e  0  elements  0  size         ar   Array newInstance  e getClass   getComponentType    size         System arraycopy  e  0  ar  0  size         permutation   new int  size 1         for  int i 0  i lt size 1  i               permutation  i  i                   private void formNextPermutation            for  int i 0  i lt size  i                  i 1 because perm 0  always   0             perm  -1 because the numbers 1  size are being permuted          Array set  ar  i  elements permutation i 1 -1                     public boolean hasNext           return next           public void remove   throws UnsupportedOperationException         throw new UnsupportedOperationException             private void swap  final int i  final int j          final int x   permutation i         permutation i    permutation  j         permutation j    x              does not throw NoSuchElement  it wraps around     public Object next   throws NoSuchElementException          formNextPermutation         copy original elements        int i   size-1        while  permutation i  gt permutation i 1   i--         if  i  0             next   false           for  int j 0  j lt size 1  j                  permutation  j  j                      return ar                 int j   size         while  permutation i  gt permutation j   j--        swap  i j         int r   size        int s   i 1        while  r gt s    swap r s   r--  s             return ar           public String toString            final int n   Array getLength ar         final StringBuffer sb   new StringBuffer              for  int j 0  j lt n  j               sb append  Array get ar j  toString              if  j lt n-1  sb append                      sb append             return new String  sb            public static void main  String    args          for  Iterator i   new Permute args   i hasNext                 final String    a    String     i next             System out println  i

User · Answer

Example with primitive array   public static void permute int   intArray  int start        for int i   start  i  lt  intArray length  i             int temp   intArray start           intArray start    intArray i           intArray i    temp          permute intArray  start   1           intArray i    intArray start           intArray start    temp            if  start    intArray length - 1            System out println java util Arrays toString intArray             public static void main String   args       int intArr      1  2  3       permute intArr  0

User · Answer

This a 2-permutation for a list wrapped in an iterator  import java util Iterator  import java util LinkedList  import java util List      all permutations of two objects         for ABC  AB AC BA BC CA CB           public class ListPermutation lt T gt  implements Iterator        int index   0      int current   0      List lt T gt  list       public ListPermutation List lt T gt  e            list   e             public boolean hasNext             return   index    list size   - 1  amp  amp  current    list size   - 1              public List lt T gt  next             if current    index                current                      if  current    list size                  current   0              index                      List lt T gt  output   new LinkedList lt T gt             output add list get index            output add list get current            current            return output             public void remove

User · Answer

Implementation via recursion  dynamic programming   in Java  with test case  TestNG      Code  PrintPermutation java  import java util Arrays          Print permutation of n elements          author eric     date Oct 13  2018 12 28 10 PM     public class PrintPermutation                  Print permutation of array elements                  param arr         return count of permutation              public static int permutation int arr              return permutation arr  0                         Print permutation of part of array elements                  param arr         param n                   start index in array          return count of permutation              private static int permutation int arr    int n            int counter   0          for  int i   n  i  lt  arr length  i                  swapArrEle arr  i  n               counter    permutation arr  n   1               swapArrEle arr  n  i                     if  n    arr length - 1                counter                System out println Arrays toString arr                       return counter                        swap 2 elements in array                  param arr         param i         param k             private static void swapArrEle int arr    int i  int k            int tmp   arr i           arr i    arr k           arr k    tmp            PrintPermutationTest java  test case via TestNG   import org testng Assert  import org testng annotations Test          PrintPermutation test          author eric     date Oct 14  2018 3 02 23 AM     public class PrintPermutationTest        Test     public void test             int arr     new int     0  1  2  3            Assert assertEquals PrintPermutation permutation arr   24            int arrSingle     new int     0            Assert assertEquals PrintPermutation permutation arrSingle   1            int arrEmpty     new int               Assert assertEquals PrintPermutation permutation arrEmpty   0

User · Answer

A simple java implementation  refer to c   std  next permutation   public static void main String   args       int   list    1 2 3 4 5       List lt List lt Integer gt  gt  output   new Main   permute list       for List result  output           System out println result             public List lt List lt Integer gt  gt  permute int   nums        List lt List lt Integer gt  gt  list   new ArrayList lt List lt Integer gt  gt         int size   factorial nums length           add the original one to the list     List lt Integer gt  seq   new ArrayList lt Integer gt         for int a nums           seq add a             list add seq           generate the next and next permutation and add them to list     for int i   0 i  lt  size - 1 i             seq   new ArrayList lt Integer gt             nextPermutation nums           for int a nums               seq add a                     list add seq             return list      int factorial int n       return  n  1  1 n factorial n-1      void nextPermutation int   nums       int i   nums length -1     start from the end      while i  gt  0  amp  amp  nums i-1   gt   nums i            i--             if i  0           reverse nums 0 nums length -1         else              found the first one not in order          int j   i              found just bigger one         while j  lt  nums length  amp  amp  nums j   gt  nums i-1                j                        swap nums i-1  nums j-1            int tmp   nums i-1           nums i-1    nums j-1           nums j-1    tmp          reverse nums i nums length-1                 reverse the sequence void reverse int   arr int start  int end       int tmp      for int i   0  i  lt    end - start  2  i              tmp   arr start   i           arr start   i    arr end - i           arr end - i     tmp

User · Answer

If you re using C    you can use std  next permutation from the  lt algorithm gt  header file   int a      3 4 6 2 1   int size   sizeof a  sizeof a 0    std  sort a  a size   do        print a s elements   while std  next permutation a  a size

User · Answer

There are n  total permutations for the given array size n  Here is code written in Java using DFS   public List lt List lt Integer gt  gt  permute int   nums        List lt List lt Integer gt  gt  results   new ArrayList lt List lt Integer gt  gt         if  nums    null    nums length    0            return results            List lt Integer gt  result   new ArrayList lt  gt         dfs nums  results  result       return results     public void dfs int   nums  List lt List lt Integer gt  gt  results  List lt Integer gt  result        if  nums length    result size              List lt Integer gt  temp   new ArrayList lt  gt  result           results add temp                     for  int i 0  i lt nums length  i              if   result contains nums i                  result add nums i                dfs nums  results  result               result remove result size   - 1                       For input array  3 2 1 4 6   there are totally 5    120 possible permutations which are     3 4 6 2 1   3 4 6 1 2   3 4 2 6 1   3 4 2 1 6   3 4 1 6 2   3 4 1 2 6   3 6 4 2 1   3 6 4 1 2   3 6 2 4 1   3 6 2 1 4   3 6 1 4 2   3 6 1 2 4   3 2 4 6 1   3 2 4 1 6   3 2 6 4 1   3 2 6 1 4   3 2 1 4 6   3 2 1 6 4   3 1 4 6 2   3 1 4 2 6   3 1 6 4 2   3 1 6 2 4   3 1 2 4 6   3 1 2 6 4   4 3 6 2 1   4 3 6 1 2   4 3 2 6 1   4 3 2 1 6   4 3 1 6 2   4 3 1 2 6   4 6 3 2 1   4 6 3 1 2   4 6 2 3 1   4 6 2 1 3   4 6 1 3 2   4 6 1 2 3   4 2 3 6 1   4 2 3 1 6   4 2 6 3 1   4 2 6 1 3   4 2 1 3 6   4 2 1 6 3   4 1 3 6 2   4 1 3 2 6   4 1 6 3 2   4 1 6 2 3   4 1 2 3 6   4 1 2 6 3   6 3 4 2 1   6 3 4 1 2   6 3 2 4 1   6 3 2 1 4   6 3 1 4 2   6 3 1 2 4   6 4 3 2 1   6 4 3 1 2   6 4 2 3 1   6 4 2 1 3   6 4 1 3 2   6 4 1 2 3   6 2 3 4 1   6 2 3 1 4   6 2 4 3 1   6 2 4 1 3   6 2 1 3 4   6 2 1 4 3   6 1 3 4 2   6 1 3 2 4   6 1 4 3 2   6 1 4 2 3   6 1 2 3 4   6 1 2 4 3   2 3 4 6 1   2 3 4 1 6   2 3 6 4 1   2 3 6 1 4   2 3 1 4 6   2 3 1 6 4   2 4 3 6 1   2 4 3 1 6   2 4 6 3 1   2 4 6 1 3   2 4 1 3 6   2 4 1 6 3   2 6 3 4 1   2 6 3 1 4   2 6 4 3 1   2 6 4 1 3   2 6 1 3 4   2 6 1 4 3   2 1 3 4 6   2 1 3 6 4   2 1 4 3 6   2 1 4 6 3   2 1 6 3 4   2 1 6 4 3   1 3 4 6 2   1 3 4 2 6   1 3 6 4 2   1 3 6 2 4   1 3 2 4 6   1 3 2 6 4   1 4 3 6 2   1 4 3 2 6   1 4 6 3 2   1 4 6 2 3   1 4 2 3 6   1 4 2 6 3   1 6 3 4 2   1 6 3 2 4   1 6 4 3 2   1 6 4 2 3   1 6 2 3 4   1 6 2 4 3   1 2 3 4 6   1 2 3 6 4   1 2 4 3 6   1 2 4 6 3   1 2 6 3 4   1 2 6 4 3     Hope this helps

User · Answer

According to wiki https   en wikipedia org wiki Heap 27s algorithm  Heap s algorithm generates all possible permutations of n objects  It was first proposed by B  R  Heap in 1963  The algorithm minimizes movement  it generates each permutation from the previous one by interchanging a single pair of elements  the other n-2 elements are not disturbed  In a 1977 review of permutation-generating algorithms  Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer   So if we want to do it in recursive manner  Sudo code is bellow   procedure generate n   integer  A   array of any       if n   1 then           output A      else         for i    0  i  lt  n - 1  i    1 do             generate n - 1  A              if n is even then                 swap A i   A n-1               else                 swap A 0   A n-1               end if         end for         generate n - 1  A      end if   java code   public static void printAllPermutations          int n  int   elements  char delimiter        if  n    1            printArray elements  delimiter         else           for  int i   0  i  lt  n - 1  i                  printAllPermutations n - 1  elements  delimiter               if  n   2    0                    swap elements  i  n - 1                 else                   swap elements  0  n - 1                                   printAllPermutations n - 1  elements  delimiter            private static void printArray int   input  char delimiter        int i   0      for    i  lt  input length  i              System out print input i              System out print delimiter      private static void swap int   input  int a  int b        int tmp   input a       input a    input b       input b    tmp     public static void main String   args        int   input   new int   0 1 2 3       printAllPermutations input length  input

User · Answer

Here is one using arrays and Java 8  import java util Arrays  import java util stream IntStream   public class HelloWorld        public static void main String   args            int   arr    1  2  3  5           permutation arr  new int                  static void permutation int   arr  int   prefix            if  arr length    0                System out println Arrays toString prefix                      for  int i   0  i  lt  arr length  i                  int i2   i              int   pre   IntStream concat Arrays stream prefix   IntStream of arr i    toArray                int   post   IntStream range 0  arr length  filter i1 - gt  i1    i2  map v - gt  arr v   toArray                permutation post  pre

User · Answer

Here is how you can print all permutations in 10 lines of code   public class Permute      static void permute java util List lt Integer gt  arr  int k           for int i   k  i  lt  arr size    i                 java util Collections swap arr  i  k               permute arr  k 1               java util Collections swap arr  k  i                     if  k    arr size   -1               System out println java util Arrays toString arr toArray                          public static void main String   args           Permute permute java util Arrays asList 3 4 6 2 1   0             You take first element of an array  k 0  and exchange it with any element  i  of the array  Then you recursively apply permutation on array starting with second element  This way you get all permutations starting with i-th element  The tricky part is that after recursive call you must swap i-th element with first element back  otherwise you could get repeated values at the first spot  By swapping it back we restore order of elements  basically you do backtracking     Iterators and Extension to the case of repeated values  The drawback of previous algorithm is that it is recursive  and does not play nicely with iterators  Another issue is that if you allow repeated elements in your input  then it won t work as is   For example  given input  3 3 4 4  all possible permutations  without repetitions  are    3  3  4  4   3  4  3  4   3  4  4  3   4  3  3  4   4  3  4  3   4  4  3  3     if you simply apply permute function from above you will get  3 3 4 4  four times  and this is not what you naturally want to see in this case  and the number of such permutations is 4   2  2   6   It is possible to modify the above algorithm to handle this case  but it won t look nice  Luckily  there is a better algorithm  I found it here  which handles repeated values and is not recursive    First note  that permutation of array of any objects can be reduced to permutations of integers by enumerating them in any order    To get permutations of an integer array  you start with an array sorted in ascending order  You  goal  is to make it descending  To generate next permutation you are trying to find the first index from the bottom where sequence fails to be descending  and improves value in that index while switching order of the rest of the tail from descending to ascending in this case   Here is the core of the algorithm     ind is an array of integers for int tail   ind length - 1 tail  gt  0 tail--       if  ind tail - 1   lt  ind tail     still increasing            find last element which does not exceed ind tail-1          int s   ind length - 1          while ind tail-1   gt   ind s               s--           swap ind  tail-1  s              reverse order of elements in the tail         for int i   tail  j   ind length - 1  i  lt  j  i    j--               swap ind  i  j                     break            Here is the full code of iterator  Constructor accepts an array of objects  and maps them into an array of integers using HashMap    import java lang reflect Array  import java util    class Permutations lt E gt  implements  Iterator lt E   gt        private E   arr      private int   ind      private boolean has next       public E   output   next   returns this array  make it public      Permutations E   arr           this arr   arr clone            ind   new int arr length             convert an array of any elements into array of integers - first occurrence is used to enumerate         Map lt E  Integer gt  hm   new HashMap lt E  Integer gt             for int i   0  i  lt  arr length  i                 Integer n   hm get arr i                if  n    null                   hm put arr i   i                   n   i                            ind i    n intValue                      Arrays sort ind    start with ascending sequence of integers             output   new E arr length    lt -- cannot do in Java with generics  so use reflection         output    E    Array newInstance arr getClass   getComponentType    arr length           has next   true             public boolean hasNext             return has next                        Computes next permutations  Same array instance is returned every time          return             public E   next             if   has next              throw new NoSuchElementException             for int i   0  i  lt  ind length  i                 output i    arr ind i                          get next permutation         has next   false          for int tail   ind length - 1 tail  gt  0 tail--               if  ind tail - 1   lt  ind tail     still increasing                    find last element which does not exceed ind tail-1                  int s   ind length - 1                  while ind tail-1   gt   ind s                       s--                   swap ind  tail-1  s                      reverse order of elements in the tail                 for int i   tail  j   ind length - 1  i  lt  j  i    j--                       swap ind  i  j                                     has next   true                  break                                   return output             private void swap int   arr  int i  int j           int t   arr i           arr i    arr j           arr j    t             public void remove                Usage test       TCMath Permutations lt Integer gt  perm   new TCMath Permutations lt Integer gt  new Integer   3 3 4 4 4 5 5        int count   0      while perm hasNext             System out println Arrays toString perm next              count              System out println  total      count     Prints out all 7   2  3  2   210 permutations

[java] Permutation of array

Examples related to java

Examples related to c++

Examples related to algorithm