Generating all permutations of a given string

Question

What is an elegant way to find all the permutations of a string  E g  permutation for ba  would be ba and ab  but what about longer string such as abcdefgh  Is there any Java implementation example

User · Answer

Here is a java implementation      All Permutations of a String     import java util    import java lang    import java io        Complexity O n n      class Ideone        public static ArrayList lt String gt  strPerm String str  ArrayList lt String gt  list                 int len   str length            if len  1               list add str               return list                     list   strPerm str substring 0 len-1  list           int ls   list size            char ap   str charAt len-1           for int i 0 i lt ls i                 String temp   list get i               int tl   temp length                for int j 0 j lt  tl j                     list add temp substring 0 j  ap temp substring j tl                                       while true               String temp   list get 0               if temp length   lt len                  list remove temp               else                 break                     return list             public static void main  String   args  throws java lang Exception               String str    abc           ArrayList lt String gt  list   new ArrayList lt  gt              list   strPerm str list           System out println  Total Permutations     list size             for int i 0 i lt list size   i                System out println list get i               http   ideone com nWPb3k

User · Answer

import java io    public class Anagram    public static void main String   args          java util Scanner sc new java util Scanner System in               PrintWriter p new PrintWriter System out true               p println  Enter Word                String a   s    st boolean flag true              int in   n nf 1 i j 0 k m 0              char l                st sc next                p println  Anagrams                p println  1     st               l st toCharArray                n st length                for i 1 i lt  n i                     nf  i                             i 1              a new String nf               in new int n               a 0  st              while i lt nf                   for m 0 m lt n m                         in m  n                   j 0                  while j lt n                       k  int  n Math random                          for m 0 m lt  j m                             if k  in m                                flag false                              break                                                                                if flag  true                           in j    k                       flag true                   s                     for j 0 j lt n j                         s  l in j                                         Removing same words                 for m 0 m lt  i m                             if s equalsIgnoreCase a m                                 flag false                              break                                                                                if flag  true                           a i    s                          p println i       a i-1                         flag true

User · Answer

String permutaions using Es6  Using reduce   method   x000D   x000D  const permutations   str   gt    x000D    if  str length  lt   2   x000D    return str length     2    str  str 1    str 0      str   x000D     x000D    return str x000D       split     x000D       reduce  x000D         acc  letter  index    gt  x000D          acc concat permutations str slice 0  index    str slice index   1   map val   gt  letter   val    x000D            x000D         x000D     x000D   x000D  console log permutations  STR     x000D   x000D   x000D

User · Answer

This is a C solution    include  lt stdio h gt   include  lt string h gt   include  lt math h gt   include  lt stdlib h gt    char  addLetter char  string  char  c        char  result   malloc sizeof string    2       strcpy result  string       strncat result  c  1       return result     char  removeLetter char  string  char  c        char  result   malloc sizeof string        int j   0      for  int i   0  i  lt  strlen string   i              if  string i      c                result j      string i                       result j      0        return result     void makeAnagram char  anagram  char  letters         if   letters      0             printf   s n   anagram           return             char  c   letters      while   c      0             makeAnagram addLetter anagram  c                       removeLetter letters  c            c              int main          makeAnagram      computer         return 0

User · Answer

I am defining two strings left and right  In the beginning  the left is input string and he right is         I recursively choose all possible chars from left and add it to the end of the right  Then  I call the recursive function on left-charAt i  and right charAt i   I am defining a class to keep track of the generated permutations   import java util HashSet  import java util Set   public class FindPermutations        static class Permutations           Set lt String gt  permutations   new HashSet lt  gt                           Building all the permutations by adding chars of left to right one by one                 param left         The left string         param right        The right string         param permutations The permutations             private void findPermutations String left  String right  Permutations permutations            int n   left length            if  n    0                permutations permutations add right                     for  int i   0  i  lt  n  i                  findPermutations left substring 0  i    left substring i   1  n   right   left charAt i   permutations                                   Gets all the permutations of a string s                 param s The input string         return all the permutations of a string s             public Permutations getPermutations String s            Permutations permutations   new Permutations            findPermutations s      permutations           return permutations             public static void main String   args            FindPermutations findPermutations   new FindPermutations            String s    ABC           Permutations permutations   findPermutations getPermutations s           printPermutations permutations              private static void printPermutations Permutations permutations            for  String p   permutations permutations                System out println p                        I hope it helps

User · Answer

Another simple way is to loop through the string  pick the character that is not used yet and put it to a buffer  continue the loop till the buffer size equals to the string length  I like this back tracking solution better because    Easy to understand Easy to avoid duplication The output is sorted   Here is the java code   List lt String gt  permute String str      if  str    null        return null         char   chars   str toCharArray      boolean   used   new boolean chars length      List lt String gt  res   new ArrayList lt String gt       StringBuilder sb   new StringBuilder       Arrays sort chars      helper chars  used  sb  res      return res     void helper char   chars  boolean   used  StringBuilder sb  List lt String gt  res      if  sb length      chars length        res add sb toString         return         for  int i   0  i  lt  chars length  i             avoid duplicates     if  i  gt  0  amp  amp  chars i     chars i - 1   amp  amp   used i - 1           continue                pick the character that has not used yet     if   used i           used i    true        sb append chars i           helper chars  used  sb  res             back tracking       sb deleteCharAt sb length   - 1         used i    false                Input str  1231  Output list   1123  1132  1213  1231  1312  1321  2113  2131  2311  3112  3121  3211   Noticed that the output is sorted  and there is no duplicate result

User · Answer

Here is my solution that is based on the idea of the book  Cracking the Coding Interview   P54           List permutations of a string          param s the input string     return  the list of permutations     public static ArrayList lt String gt  permutation String s           The result     ArrayList lt String gt  res   new ArrayList lt String gt            If input string s length is 1  return  s      if  s length      1            res add s         else if  s length    gt  1            int lastIndex   s length   - 1             Find out the last character         String last   s substring lastIndex              Rest of the string         String rest   s substring 0  lastIndex              Perform permutation on the rest string and            merge with the last character         res   merge permutation rest   last             return res             param list a result of permutation  e g    ab    ba       param c    the last character     return     a merged new list  e g    cab    acb            public static ArrayList lt String gt  merge ArrayList lt String gt  list  String c        ArrayList lt String gt  res   new ArrayList lt  gt            Loop through all the string in the list     for  String s   list               For each string  insert the last character to all possible positions            and add them to the new list         for  int i   0  i  lt   s length      i                String ps   new StringBuffer s  insert i  c  toString                res add ps                       return res        Running output of string  abcd     Step 1  Merge  a  and b   ba  ab  Step 2  Merge  ba  ab  and c   cba  bca  bac  cab  acb  abc  Step 3  Merge  cba  bca  bac  cab  acb  abc  and d   dcba  cdba  cbda  cbad  dbca  bdca  bcda  bcad  dbac  bdac  badc  bacd  dcab  cdab  cadb  cabd  dacb  adcb  acdb  acbd  dabc  adbc  abdc  abcd

User · Answer

python implementation  def getPermutation s  prefix              if len s     0                  print prefix         for i in range len s                    getPermutation s 0 i  s i 1 len s   prefix s i       getPermutation  abcd

User · Answer

A very basic solution in Java is to use recursion   Set   to avoid repetitions   if you want to store and return the solution strings    public static Set lt String gt  generatePerm String input        Set lt String gt  set   new HashSet lt String gt         if  input                return set       Character a   input charAt 0        if  input length    gt  1                input   input substring 1            Set lt String gt  permSet   generatePerm input            for  String x   permSet                        for  int i   0  i  lt   x length    i                                  set add x substring 0  i    a   x substring i                                      else               set add a                  return set

User · Answer

We can use factorial to find how many strings started with particular letter   Example  take the input abcd   3      6 strings will start with every letter of abcd   static public int facts int x       int sum   1      for  int i   1  i  lt  x  i              sum     i 1             return sum     public static void permutation String str        char   str2   str toCharArray        int n   str2 length      int permutation   0      if  n    1            System out println str2 0          else if  n    2            System out println str2 0         str2 1            System out println str2 1         str2 0          else           for  int i   0  i  lt  n  i                  if  true                    char   str3   str toCharArray                    char temp   str3 i                   str3 i    str3 0                   str3 0    temp                  str2   str3                             for  int j   1  count   0  count  lt  facts n-1   j    count                      if  j    n-1                        char temp1   str2 j 1                       str2 j 1    str2 j                       str2 j    temp1                    else                       char temp1   str2 n-1                       str2 n-1    str2 1                       str2 1    temp1                      j   1                       end of else block                 permutation                    System out print  permutation     permutation     is   - gt                      for  int k   0  k  lt  n  k                          System out print str2 k                         end of loop k                 System out println                     end of loop j              end of loop i

User · Answer

Based on Mark Byers  answer i came up with this solution  JAVA public class Main        public static void main String   args            myPerm  quot ABCD quot   0              private static void myPerm String str  int index                if  index    str length    System out println str            for  int i   index  i  lt  str length    i                          char prefix   str charAt i               String suffix   str substring 0 i    str substring i 1                myPerm prefix   suffix  index   1                       C  I also wrote the function in C  using the new C  8 0 range operator     class Program               static void Main string   args                        myPerm  quot ABCD quot   0                      private static void myPerm string str  int index                        if  index    str Length  Console WriteLine str                for  int i   index  i  lt  str Length  i                                  char prefix   str i                   string suffix   str 0  i    str  i   1                       myPerm prefix   suffix  index   1                                  We just put every letter at the beginning and then permute  The first iteration looks like this     myPerm  quot ABCD quot  0      prefix    quot A quot      suffix    quot BCD quot      myPerm  quot ABCD quot  1        prefix    quot B quot        suffix    quot ACD quot        myPerm  quot BACD quot  2          prefix    quot C quot          suffix    quot BAD quot          myPerm  quot CBAD quot  3            prefix    quot D quot            suffix    quot CBA quot            myPerm  quot DCBA quot  4              Console WriteLine  quot DCBA quot

User · Answer

Returns an array list containing all    permutations of the characters in s     public static ArrayList lt String gt  permute String s        ArrayList lt String gt  perms   new ArrayList lt  gt         int slen   s length        if  slen  gt  0               Add the first character from s to the perms array list          perms add Character toString s charAt 0                 Repeat for all additional characters in s          for  int i   1   i  lt  slen     i                    Get the next character from s              char c   s charAt i                   For each of the strings currently in perms do the following              int size   perms size                for  int j   0   j  lt  size     j                        1  remove the string                 String p   perms remove 0                   int plen   p length                        2  Add plen   1 new strings to perms   Each new string                       consists of the removed string with the character c                       inserted into it at a unique location                  for  int k   0   k  lt   plen     k                        perms add p substring 0  k    c   p substring k                                                        return perms

User · Answer

Let s use input abc as an example   Start off with just the last element  c  in a set    c     then add the second last element  b  to its front  end and every possible positions in the middle  making it   bc    cb   and then in the same manner it will add the next element from the back  a  to each string in the set making it    a     bc      abc    bac    bca    and   a     cb      acb    cab    cba      Thus entire permutation     abc    bac    bca   acb    cab    cba     Code   public class Test        static Set lt String gt  permutations      static Set lt String gt  result   new HashSet lt String gt          public static Set lt String gt  permutation String string            permutations   new HashSet lt String gt              int n   string length            for  int i   n - 1  i  gt   0  i--                         shuffle string charAt i                      return permutations             private static void shuffle char c            if  permutations size      0                permutations add String valueOf c              else               Iterator lt String gt  it   permutations iterator                for  int i   0  i  lt  permutations size    i                       String temp1                  for    it hasNext                           temp1   it next                        for  int k   0  k  lt  temp1 length     1  k    1                            StringBuilder sb   new StringBuilder temp1                            sb insert k  c                            result add sb toString                                                                       permutations   result                 result  has to be refreshed so that in next run it doesn t contain stale values              result   new HashSet lt String gt                          public static void main String   args            Set lt String gt  result   permutation  abc             System out println   nThere are total of     result size       permutations             Iterator lt String gt  it   result iterator            while  it hasNext                  System out println it next

User · Answer

This can be done iteratively by simply inserting each letter of the string in turn in all locations of the previous partial results   We start with  A   which with B becomes  BA  AB   and with C   CBA  BCA  BAC  CAB  etc    The running time would be O n    which  for the test case ABCD  is 1 x 2 x 3 x 4   In the above product  the 1 is for A  the 2 is for B  etc   Dart sample   void main        String insertAt String a  String b  int index          return a substring 0  index    b   a substring index          List lt String gt  Permute String word         var letters   word split           var p list     letters first         for  var c in letters sublist 1            var new list               for  var p in p list          for  int i   0  i  lt   p length  i              new list add insertAt p  c  i           p list   new list             return p list         print Permute  ABCD

User · Answer

Permutation of String   public static void main String args          permu 0  ABCD       static void permu int fixed String s        char   chr s toCharArray        if fixed  s length            System out println s       for int i fixed i lt s length   i              char c chr i           chr i  chr fixed           chr fixed  c          permu fixed 1 new String chr

User · Answer

Here are two c  versions  just for reference    1  Prints all permuations 2  returns all permutations  Basic gist of the algorithm is  probably below code is more intuitive - nevertheless  here is some explanation of what below code does   - from the current index to for the rest of the collection  swap the element at current index - get the permutations for the remaining elements from next index recursively - restore the order  by re-swapping   Note  the above recursive function will be invoked from the start index   private void PrintAllPermutations int   a  int index  ref int count                        if  index     a Length - 1                                 count                    var s   string Format   0    1    count  string Join      a                    Debug WriteLine s                             for  int i   index  i  lt  a Length  i                                  Utilities swap ref a i   ref a index                    this PrintAllPermutations a  index   1  ref count                   Utilities swap ref a i   ref a index                                    private int PrintAllPermutations int   a                        a ThrowIfNull  a                int count   0              this PrintAllPermutations a  index 0  count  ref count               return count              version 2  same as above - but returns the permutations in lieu of printing   private int     GetAllPermutations int   a  int index                        List lt int   gt  permutations   new List lt int   gt                 if  index     a Length - 1                                 permutations Add a ToArray                                for  int i   index  i  lt  a Length  i                                  Utilities swap ref a i   ref a index                    var r   this GetAllPermutations a  index   1                   permutations AddRange r                   Utilities swap ref a i   ref a index                              return permutations ToArray                      private int     GetAllPermutations int   p                        p ThrowIfNull  p                return this GetAllPermutations p  0               Unit Tests   TestMethod          public void PermutationsTests                         List lt int gt  input   new List lt int gt                 int   output     0  1  2  6  24  120                for  int i   0  i  lt   5  i                                  if  i    0                                        input Add i                                     Debug WriteLine                  PrintAllPermutations                                       int count   this PrintAllPermutations input ToArray                     Assert IsTrue count    output i                    Debug WriteLine                       GetAllPermutations                                     var r   this GetAllPermutations input ToArray                     Assert IsTrue count    r Length                   for  int j   1  j  lt   r Length j                                           string s   string Format   0    1    j                          string Join      r j - 1                         Debug WriteLine s                                     Debug WriteLine  No OfElements   0   TotalPerms   1    i  count

User · Answer

My implementation based on Mark Byers s description above       static Set lt String gt  permutations String str           if  str isEmpty                 return Collections singleton str            else              Set  lt String gt  set   new HashSet lt  gt                 for  int i 0  i lt str length    i                    for  String s   permutations str substring 0  i    str substring i 1                        set add str charAt i    s               return set

User · Answer

I have been learning to think recursively and the first natural solution that struck me is as follows  A problem one step simpler would be to find permutations of a string that is one letter shorter  I will assume  and believe with every fiber of my being  that my function can correctly find permutations of a string that is one letter shorter than the one I am currently trying to  Given a string say  abc   break it into a subproblem of finding permutations of a string one character less which is  bc   Once we have permutations of  bc  we need to know how to combine it with  a  to get the permutations for  abc   This is the core of recursion  Use the solution of a subproblem to solve the current problem  By observation  we can see that inserting  a  in all the positions of each of the permutations of  bc  which are  bc  and  cb  will give us all the permutations of  abc   We have to insert  a  between adjacent letters and at the front and end of each permutation  For example For  bc  we have  a   bc        abc   b   a   c     bac   bc   a        bca  For  cb  we have  a   cb        acb   c   a   b     cab   cb   a        cba  The following code snippet will clarify this  Here is the working link for the snippet  def main        result          for permutation in   bc    cb            for i in range len permutation    1               result append permutation  i     a    permutation i        return result   if   name         main         print main     The complete recursive solution will be  Here is the working link for the complete code  def permutations s       if len s     1 or len s     0          return s      permutations          for permutation in permutations s 1             for i in range len permutation    1                permutations append permutation  i    s 0    permutation i        return  permutations   def main s       print permutations s     if   name         main         main  abc

User · Answer

public class Permutation     public static void main String   args          String str    ABC        int n   str length         Permutation permutation   new Permutation         permutation permute str  0  n-1               permutation function     param str string to calculate permutation for     param l starting index     param r end index     private void permute String str  int l  int r          if  l    r           System out println str        else                for  int i   l  i  lt   r  i                            str   swap str l i                permute str  l 1  r                str   swap str l i                                 Swap Characters at position     param a string value     param i position 1     param j position 2     return swapped string     public String swap String a  int i  int j          char temp       char   charArray   a toCharArray         temp   charArray i         charArray i    charArray j        charArray j    temp       return String valueOf charArray

User · Answer

eg  abc   gt  a bc   b ac   c ab           gt  ca b   cb a           gt cba cab          gt  ba c   bc a           gt bca bac          gt  ab c   ac b           gt acb abc             public void nonRecpermute String prefix  String word                String   currentstr   prefix word           Stack lt String   gt  stack   new Stack lt String   gt             stack add currentstr           while  stack isEmpty                          currentstr   stack pop                String currentPrefix   currentstr 0               String currentWord   currentstr 1               if currentWord equals                                    System out println  Word    currentPrefix                             for int i 0 i lt currentWord length   i                                  String   newstr   new String 2                   newstr 0  currentPrefix   String valueOf currentWord charAt i                    newstr 1    currentWord substring 0  i                   if i lt currentWord length  -1                                        newstr 1    newstr 1  currentWord substring i 1                                     stack push newstr

User · Answer

Based on the answer of Mark Byers  my python implementation   def permutations string       if len string     1          return  string      permutations        for i in range len string            for perm in permutations string  i  string i 1                 permutations append string i    perm      return permutations

User · Answer

All the previous contributors have done a great job explaining and providing the code  I thought I should share this approach too because it might help someone too  The solution is based on  heaps  algorithm     Couple of things     Notice the last item which is depicted in the excel is just for helping you better visualize the logic  So  the actual values in the last column would be 2 1 0  if we were to run the code because we are dealing with arrays and arrays start with 0   The swapping algorithm happens based on even or odd values of current position  It s very self explanatory if you look at where the swap method is getting called You can see what s going on    Here is what happens    public static void main String   args             String ourword    abc           String   ourArray   ourword split              permute ourArray  ourArray length               private static void swap String   ourarray  int right  int left            String temp   ourarray right           ourarray right    ourarray left           ourarray left    temp             public static void permute String   ourArray  int currentPosition            if  currentPosition    1                System out println Arrays toString ourArray              else               for  int i   0  i  lt  currentPosition  i                         subtract one from the last position  here is where you are                    selecting the the next last item                  permute ourArray  currentPosition - 1                       if it s odd position                 if  currentPosition   2    1                        swap ourArray  0  currentPosition - 1                     else                       swap ourArray  i  currentPosition - 1

User · Answer

A simple recursive C   implementation would look like this    include  lt iostream gt   void generatePermutations std  string  amp sequence  int index       if index    sequence size             std  cout  lt  lt  sequence  lt  lt    n         else          generatePermutations sequence  index   1           for int i   index   1   i  lt  sequence size       i               std  swap sequence index   sequence i                generatePermutations sequence  index   1               std  swap sequence index   sequence i                                   int main int argc  char const  argv          std  string str    abc       generatePermutations str  0       return 0      Output   abc acb bac bca cba cab   UPDATE  If you want to store the results  you can pass a vector as the third argument to the function call  Furthermore  if you only want the unique permutations  you can use a set     include  lt iostream gt   include  lt vector gt   include  lt set gt   void generatePermutations std  string  amp sequence  int index  std  vector  lt std  string gt   amp v       if index    sequence size               std  cout  lt  lt  sequence  lt  lt    n           v push back sequence         else          generatePermutations sequence  index   1  v           for int i   index   1   i  lt  sequence size       i               std  swap sequence index   sequence i                generatePermutations sequence  index   1  v               std  swap sequence index   sequence i                                   int main int argc  char const  argv          std  string str    112       std  vector  lt std  string gt  permutations      generatePermutations str  0  permutations       std  cout  lt  lt   Number of permutations    lt  lt  permutations size    lt  lt    n       for const std  string  amp s   permutations           std  cout  lt  lt  s  lt  lt    n             std  set  lt std  string gt  uniquePermutations permutations begin    permutations end         std  cout  lt  lt   Number of unique permutations    lt  lt  uniquePermutations size    lt  lt    n       for const std  string  amp s   uniquePermutations           std  cout  lt  lt  s  lt  lt    n             return 0      Output   Number of permutations 6 112 121 112 121 211 211 Number of unique permutations 3 112 121 211

User · Answer

In python anyway  def perms in str  prefix      if not len in str        print prefix  else              for i in range 0  len in str            perms in str  i    in str i   1    prefix   in str i    perms  ASD

User · Answer

Recursion is not necessary  even you can calculate any permutation directly  this solution uses generics to permute any array   Here is a good information about this algorihtm   For C  developers here is more useful implementation   public static void main String   args        String word    12345        Character   array   ArrayUtils toObject word toCharArray         long   factorials   Permutation getFactorials array length   1        for  long i   0  i  lt  factorials array length   i              Character   permutation   Permutation  lt Character gt getPermutation i  array  factorials           printPermutation permutation            private static void printPermutation Character   permutation        for  int i   0  i  lt  permutation length  i              System out print permutation i              System out println        This algorithm has O N  time and space complexity to calculate each permutation   public class Permutation       public static  lt T gt  T   getPermutation long permutationNumber  T   array  long   factorials            int   sequence   generateSequence permutationNumber  array length - 1  factorials           T   permutation   generatePermutation array  sequence            return permutation             public static  lt T gt  T   generatePermutation T   array  int   sequence            T   clone   array clone             for  int i   0  i  lt  clone length - 1  i                  swap clone  i  i   sequence i                       return clone             private static int   generateSequence long permutationNumber  int size  long   factorials            int   sequence   new int size            for  int j   0  j  lt  sequence length  j                  long factorial   factorials sequence length - j               sequence j     int   permutationNumber   factorial               permutationNumber    int   permutationNumber   factorial                      return sequence             private static  lt T gt  void swap T   array  int i  int j            T t   array i           array i    array j           array j    t             public static long   getFactorials int length            long   factorials   new long length           long factor   1           for  int i   0  i  lt  length  i                  factor    i  lt   1   1   i              factorials i    factor                     return factorials

User · Answer

This one is without recursion   public static void permute String s        if null  s    s isEmpty              return                List containing words formed in each iteration      List lt String gt  strings   new LinkedList lt String gt         strings add String valueOf s charAt 0        add the first element to the list          Temp list that holds the set of strings for           appending the current character to all position in each word in the original list     List lt String gt  tempList   new LinkedList lt String gt           for int i 1  i lt  s length    i               for int j 0  j lt strings size    j                  tempList addAll merge s charAt i   strings get j                                       strings removeAll strings           strings addAll tempList            tempList removeAll tempList               for int i 0  i lt strings size    i              System out println strings get i                    helper method that appends the given character at each position in the given string     and returns a set of such modified strings     - set removes duplicates if any in case a character is repeated      private static Set lt String gt  merge Character c   String s        if s  null    s isEmpty              return null             int len   s length        StringBuilder sb   new StringBuilder        Set lt String gt  list   new HashSet lt String gt          for int i 0  i lt   len  i              sb   new StringBuilder            sb append s substring 0  i    c   s substring i  len            list add sb toString                return list

User · Answer

As a Python generator  with modern type hints  from typing import Iterator   def permutations string  str  prefix  str       - gt  Iterator str       if len string     0          yield prefix     for i  character in enumerate string           yield from permutations string  i    string i   1    prefix   character    for p in permutations  abcd        print p

User · Answer

This is a faster solution as it doesn t suffer for string concatenation computation complexity O n 2   On the other hand its loop free  fully recursive   public static void main String   args        permutation  ABCDEFGHIJKLMNOPQRSTUVWXYZ       private static void permutation String str        char   stringArray   str toCharArray        printPermutation stringArray  0  stringArray length  0  1      private static void printPermutation char   string  int loopCounter  int length  int indexFrom  int indexTo           Stop condition     if  loopCounter    length          return                When reaching the end of the array       1- Reset loop indices       2- Increase length counter               if  indexTo    length            indexFrom   0          indexTo   1            loopCounter                Print      System out println string           Swap from   to indices      char temp   string indexFrom       string indexFrom    string indexTo       string indexTo    temp          Go for next iteration      printPermutation string  loopCounter  length    indexFrom    indexTo

User · Answer

This is what I did through basic understanding of Permutations and Recursive function calling  Takes a bit of time but it s done independently   public class LexicographicPermutations    public static void main String   args           TODO Auto-generated method stub     String s  abc       List lt String gt combinations new ArrayList lt String gt         combinations permutations s       Collections sort combinations       System out println combinations      private static List lt String gt  permutations String s           TODO Auto-generated method stub     List lt String gt combinations new ArrayList lt String gt         if s length    1           combinations add s             else          for int i 0 i lt s length   i                 List lt String gt temp permutations s substring 0  i  s substring i 1                for  String string   temp                    combinations add s charAt i  string                                     return combinations       which generates Output as  abc  acb  bac  bca  cab  cba    Basic logic behind it is   For each character  consider it as 1st character  amp  find the combinations of remaining characters  e g   abc  Combination of abc - gt     a- gt  bc  a x Combination of  bc  - gt  abc acb  b- gt  ac  b x Combination of  ac  - gt  bac bca  c- gt  ab  c x Combination of  ab  - gt  cab cba    And then recursively calling each  bc   ac   amp   ab  independently

User · Answer

public static void permutation String str         permutation     str       private static void permutation String prefix  String str        int n   str length        if  n    0  System out println prefix       else           for  int i   0  i  lt  n  i                permutation prefix   str charAt i   str substring 0  i    str substring i 1  n               via Introduction to Programming in Java

User · Answer

Well here is an elegant  non-recursive  O n   solution   public static StringBuilder   permutations String s            if  s length      0              return null          int length   fact s length             StringBuilder   sb   new StringBuilder length           for  int i   0  i  lt  length  i                  sb i    new StringBuilder                      for  int i   0  i  lt  s length    i                  char ch   s charAt i               int times   length    i   1               for  int j   0  j  lt  times  j                      for  int k   0  k  lt  length   times  k                          sb j   length   times   k  insert k  ch                                                     return sb

User · Answer

Recursive Python solution  def permute input str        permute     input str   def  permute prefix  str to permute       if str to permute                print prefix       else          for i in range len str to permute                  permute prefix str to permute i   str to permute 0 i    str to permute i 1     if   name         main         permute  foobar

User · Answer

Loop thro  the entire character array and keep  i  as the basis of your permutation and keep finding the combination like you swap  ab  ba   public class Permutation         Act as a queue     private List lt Character gt  list        To remove the duplicates     private Set lt String gt  set   new HashSet lt String gt          public Permutation String s            list   new LinkedList lt Character gt             int len   s length            for int i   0  i  lt  len  i                  list add s charAt i                         public List lt String gt  getStack Character c  List lt Character gt  list            LinkedList lt String gt  stack   new LinkedList lt String gt             stack add    c           for Character ch  list                stack add    ch                      return stack             public String printCombination String s1  String s2              S1 will be a single character         StringBuilder sb   new StringBuilder            String   strArr   s2 split               for String s  strArr                sb append s  append s1               sb append                                for String s  strArr                sb append s1  append s               sb append                          return sb toString               public void printPerumtation             int cnt   list size             for int i   0  i  lt  cnt  i                  Character c   list get 0               list remove 0               List lt String gt  stack   getStack c  list                while stack size    gt  1                      Remove the top two elements                 String s2   stack remove stack size   - 1                   String s1   stack remove stack size   - 1                   String comS   printCombination s1  s2                   stack add comS                              String   perms    stack remove 0   split                   for String perm  perms                    set add perm                              list add c                      for String s  set                System out println s

User · Answer

In case anyone wants to generate the permutations to do something with them  instead of just printing them via a void method   static List lt int   gt  permutations int n         class Perm           private final List lt int   gt  permutations   new ArrayList lt  gt              private void perm int   array  int step                if  step    1  permutations add array clone                 else for  int i   0  i  lt  step  i                      perm array  step - 1                   int j    step   2    0    i   0                  swap array  step - 1  j                                    private void swap int   array  int i  int j                int buffer   array i               array i    array j               array j    buffer                        int   nVector    new int n       for  int i   0  i  lt  n  i    nVector  i    i       Perm perm   new Perm        perm perm nVector  n       return perm permutations

User · Answer

Of all the solutions given here and in other forums  I liked Mark Byers the most  That description actually made me think and code it myself  Too bad I cannot voteup his solution as I am newbie  Anyways here is my implementation of his description  public class PermTest        public static void main String   args  throws Exception           String str    abcdef           StringBuffer strBuf   new StringBuffer str           doPerm strBuf 0              private static void doPerm StringBuffer str  int index            if index    str length                System out println str                       else     recursively solve this by placing all other chars at current first pos             doPerm str  index 1               for  int i   index 1  i  lt  str length    i       start swapping all other chars with current first char                 swap str index  i                   doPerm str  index 1                   swap str i  index    restore back my string buffer                                    private  static void swap StringBuffer str  int pos1  int pos2           char t1   str charAt pos1           str setCharAt pos1  str charAt pos2            str setCharAt pos2  t1                I prefer this solution ahead of the first one in this thread because this solution uses StringBuffer  I wouldn t say my solution doesn t create any temporary string  it actually does in system out println where the toString   of StringBuffer is called   But I just feel this is better than the first solution where too many string literals are created  May be some performance guy out there can evalute this in terms of  memory   for  time  it already lags due to that extra  swap

User · Answer

Java implementation without recursion  public Set lt String gt  permutate String s       Queue lt String gt  permutations   new LinkedList lt String gt         Set lt String gt  v   new HashSet lt String gt         permutations add s        while permutations size    0           String str   permutations poll            if  v contains str                v add str               for int i   0 i lt str length   i                     String c   String valueOf str charAt i                    permutations add str substring i 1    c    str substring 0 i                                      return v

User · Answer

public class StringPermutation       Function to print all the permutations of str static void printPermutn String str  String ans            If string is empty     if  str length      0            System out print ans    quot   quot            return             for  int i   0  i  lt  str length    i                  ith character of str         char ch   str charAt i               Rest of the string after excluding            the ith character         String ros   str substring 0  i    str substring i   1               Recurvise call         printPermutn ros  ans   ch             public static void main String   args        String s    quot ABC quot       printPermutn s   quot  quot

User · Answer

simple solution utilizing feature of swift language that array is value type   func permutation chrs   String   arr   String   result  inout   String         if arr count    chrs count          result append arr         return          for chr in chrs          var arr   arr        if  arr contains chr               arr append chr             permutation chrs  chrs  arr  arr  result   amp result                   func test        var result     String        let chrs     a    b    c    d      permutation chrs  chrs  arr      result   amp result      complexity O n   n

User · Answer

Improved Code for the same      static String permutationStr        static int indexStr   0       static int factorial  int i            if  i    1              return 1          else             return i   factorial i-1              public static void permutation String str            char strArr     str toLowerCase   toCharArray            java util Arrays sort strArr            int count   1  dr   1          for  int i   0  i  lt  strArr length-1  i                 if   strArr i     strArr i 1                     count                  else                   dr    factorial count                   count   1                                         dr    factorial count            count   factorial strArr length    dr           permutationStr   new String count            permutation     str            for  String oneStr   permutationStr               System out println oneStr                        private static void permutation String prefix  String str            int n   str length            if  n    0                for  int i   0  i  lt  indexStr  i                     if permutationStr i  equals prefix                       return                                    permutationStr indexStr      prefix            else               for  int i   0  i  lt  n  i                      permutation prefix   str charAt i   str substring 0  i    str substring i   1  n

User · Answer

Let me try to tackle this problem with Kotlin   fun  lt T gt  List lt T gt  permutations    List lt List lt T gt  gt          escape case     if  this isEmpty    return emptyList        if  this size    1  return listOf this       if  this size    2  return listOf listOf this first    this last     listOf this last    this first            recursive case     return this flatMap   lastItem - gt          this minus lastItem  permutations   map   it plus lastItem              Core concept  Break down long list into smaller list   recursion  Long answer with example list  1  2  3  4    Even for a list of 4 it already kinda get s confusing trying to list all the possible permutations in your head  and what we need to do is exactly to avoid that  It is easy for us to understand how to make all permutations of list of size 0  1  and 2  so all we need to do is break them down to any of those sizes and combine them back up correctly  Imagine a jackpot machine  this algorithm will start spinning from the right to the left  and write down    return empty list of 1 when list size is 0 or 1 handle when list size is 2  e g   3  4    and generate the 2 permutations   3  4   amp   4  3   For each item  mark that as the last in the last  and find all the permutations for the rest of the item in the list   e g  put  4  on the table  and throw  1  2  3  into permutation again  Now with all permutation it s children  put itself back to the end of the list  e g    1  2  3   4    1  3  2   4    2  3  1    4

User · Answer

Rotate and create words beginning with all letter possible and push to stack 1    Read from stack1 and for each word create words with other letters at the next location by rotation and so on       eg   man      1  push1 - man  anm  nma     2  pop1 - nma    push2 - nam nma        pop1 - anm    push2 - amn anm        pop1 - man    push2 - mna man     public class StringPermute        static String str      static String word      static int top1   -1      static int top2   -1      static String   stringArray1      static String   stringArray2      static int strlength   0       public static void main String   args  throws IOException           System out println  Enter String               InputStreamReader isr   new InputStreamReader System in           BufferedReader bfr   new BufferedReader isr           str   bfr readLine            word   str          strlength   str length            int n   1          for  int i   1  i  lt   strlength  i                  n   n   i                    stringArray1   new String n           stringArray2   new String n           push word  1           doPermute            display               public static void push String word  int x            if  x    1              stringArray1   top1    word          else             stringArray2   top2    word             public static String pop int x            if  x    1              return stringArray1 top1--           else             return stringArray2 top2--              public static void doPermute              for  int j   strlength  j  gt   2  j--              popper j               public static void popper int length               pop from stack1   rotate each word n times and push to stack 2         if  top1  gt  -1                while  top1  gt  -1                    word   pop 1                   for  int j   0  j  lt  length  j                          rotate length                       push word  2                                                        pop from stack2   rotate each word n times w r t position and push to            stack 1         else               while  top2  gt  -1                    word   pop 2                   for  int j   0  j  lt  length  j                          rotate length                       push word  1                                                         public static void rotate int position            char   charstring   new char 100           for  int j   0  j  lt  word length    j                charstring j    word charAt j            int startpos   strlength - position          char temp   charstring startpos           for  int i   startpos  i  lt  strlength - 1  i                  charstring i    charstring i   1                     charstring strlength - 1    temp          word   new String charstring  trim               public static void display             int top          if  top1  gt  -1                while  top1  gt  -1                  System out println stringArray1 top1--              else               while  top2  gt  -1                  System out println stringArray2 top2--

User · Answer

A java implementation to print all the permutations of a given string considering  duplicate characters and prints only unique characters is as follow   import java util Set  import java util HashSet   public class PrintAllPermutations2       public static void main String   args                String str    AAC        PrintAllPermutations2 permutation   new PrintAllPermutations2         Set lt String gt  uniqueStrings   new HashSet lt  gt          permutation permute     str  uniqueStrings      void permute String prefixString  String s  Set lt String gt  set        int n   s length         if n    0                if  set contains prefixString                         System out println prefixString               set add prefixString                       else               for int i 0  i lt n  i                          permute prefixString   s charAt i   s substring 0 i    s substring i 1 n   set

User · Answer

Here is algorithm with O n   time complexity with pure recursion and intuitive    public class words   static String combinations  public static List lt String gt  arrlist new ArrayList lt  gt     public static void main String   args        words obj   new words         String str  premandl       obj getcombination str  str length  -1           System out println arrlist        public void getcombination String str  int charIndex  String output         if  str length      0            arrlist add output           return              if  charIndex    -1            return              String character   str toCharArray   charIndex            getcombination str  --charIndex  output        String remaining            output   output   character       remaining   str substring 0  charIndex   1    str substring charIndex   2        getcombination remaining  remaining length   - 1  output

User · Answer

import java io IOException  import java util ArrayList  import java util Scanner  public class hello       public static void main String   args  throws IOException           hello h   new hello            h printcomp                int fact 1      public void factrec int a int k           if a gt  k           fact fact k          k            factrec a k                     else          System out println  The string  will have   fact   permutations                            public void printcomp            String str          int k          Scanner in   new Scanner System in           System out println  enter the string whose permutations has to b found            str in next            k str length            factrec k 1           String   arr  new String fact           char   array   str toCharArray            while p lt fact          printcomprec k array arr                  if incase u need array containing all the permutation use this               for int d 0 d lt fact d                       System out println arr d              int y 1      int p   0      int g 1      int z   0      public void printcomprec int k char array   String arr             for  int l   0  l  lt  k  l                  for  int b 0 b lt k-1 b                 for  int i 1  i lt k-g  i                      char temp                  String stri                       temp   array i                   array i    array i   g                   array i   g    temp                  for  int j   0  j  lt  k  j                        stri    array j                   arr z    stri                  System out println arr z            p                     z                                            char temp              temp array 0               array 0  array y               array y  temp              if  y  gt   k-1                  y y- k-1               else                 y                      if  g  gt   k-1              g 1          else             g

User · Answer

This is can be easily done using bit manipulation   As we all know there are 2N possible subsets of any given set with N elements  What if we represent each element in a subset with a bit  A bit can be either 0 or 1  thus we can use this to denote whether the corresponding element belongs to this given subset or not  So each bit pattern will represent a subset    Copied text   private void getPermutation String str                        if str  null                  return              Set lt String gt  StrList   new HashSet lt String gt                 StringBuilder strB  new StringBuilder                for int i   0 i  lt   1  lt  lt  str length       i                                strB setLength 0     clear the StringBuilder                 for int j   0 j  lt  str length      j                       if  i  amp   1  lt  lt  j   gt 0       to check whether jth bit is set                         strB append str charAt j                                                            if  strB toString   isEmpty                        StrList add strB toString                               System out println Arrays toString StrList toArray

User · Answer

Adding a more detailed NcK NcR for both permutations and combinations  public static void combinationNcK List lt String gt  inputList  String prefix  int chooseCount  List lt String gt  resultList        if  chooseCount    0          resultList add prefix       else           for  int i   0  i  lt  inputList size    i                combinationNcK inputList subList i   1  inputList size     prefix         inputList get i   chooseCount - 1  resultList               Finally print once all combinations are done         if  prefix equalsIgnoreCase                    resultList stream   map str - gt  str substring 1   forEach System out  println                      public static void permNcK List lt String gt  inputList  int chooseCount  List lt String gt  resultList        for  int count   0  count  lt  inputList size    count              permNcK inputList      chooseCount  resultList           resultList   new ArrayList lt String gt             Collections rotate inputList  1           System out println  -------------------------              public static void permNcK List lt String gt  inputList  String prefix  int chooseCount  List lt String gt  resultList        if  chooseCount    0          resultList add prefix       else           for  int i   0  i  lt  inputList size    i                combinationNcK inputList subList i   1  inputList size     prefix         inputList get i   chooseCount - 1  resultList               Finally print once all combinations are done         if  prefix equalsIgnoreCase                    resultList stream   map str - gt  str substring 1   forEach System out  println                      public static void main String   args        List lt String gt  positions   Arrays asList new String      1    2    3    4    5    6    7    8          List lt String gt  resultList   new ArrayList lt String gt           combinationNcK positions      3  resultList        permNcK positions  3  resultList

User · Answer

Use recursion    Try each of the letters in turn as the first letter and then find all the permutations of the remaining letters using a recursive call  The base case is when the input is an empty string the only permutation is the empty string

User · Answer

Here is another simpler method of doing Permutation of a string   public class Solution4   public static void main String   args        String  a    Protijayi     per a  0       static void per String a    int start             bse case      if a length      start   System out println a        char   ca   a toCharArray          swap      for  int i   start  i  lt  ca length  i              char t   ca i           ca i    ca start           ca start    t          per new String ca  start 1             per

User · Answer

Simple python solution using recursion   def get permutations string          base case     if len string   lt   1          return set  string        all chars except last   string  -1      last char   string -1         recursive call  get all possible permutations for all chars except last     permutations of all chars except last   get permutations all chars except last         put the last char in all possible positions for each of the above permutations     permutations   set       for permutation of all chars except last in permutations of all chars except last          for position in range len all chars except last    1               permutation   permutation of all chars except last  position    last char   permutation of all chars except last position               permutations add permutation       return permutations

User · Answer

Use recursion   when the input is an empty string the only permutation is an empty string Try for each of the letters in the string by making it as the first letter and then find all the permutations of the remaining letters using a recursive call   import java util ArrayList  import java util List   class Permutation       private static List lt String gt  permutation String prefix  String str            List lt String gt  permutations   new ArrayList lt  gt             int n   str length            if  n    0                permutations add prefix             else               for  int i   0  i  lt  n  i                      permutations addAll permutation prefix   str charAt i   str substring i   1  n    str substring 0  i                                     return permutations             public static void main String   args            List lt String gt  perms   permutation      abcd             String   array   new String perms size             for  int i   0  i  lt  perms size    i                  array i    perms get i                      int x   array length           for  final String anArray   array                System out println anArray

User · Answer

One of the simple solution could be just keep swapping the characters recursively using two pointers   public static void main String   args        String str  abcdefgh       perm str     public static void perm String str     char   char arr str toCharArray        helper char arr 0     public static void helper char   char arr  int i        if i  char arr length-1                   print the shuffled string              String str                 for int j 0  j lt char arr length  j                                  str str char arr j                             System out println str             else           for int j i  j lt char arr length  j                  char tmp   char arr i           char arr i    char arr j           char arr j    tmp          helper char arr i 1           char tmp1   char arr i           char arr i    char arr j           char arr j    tmp1

User · Answer

A generic implementation of the Countdown Quickperm algorithm  representation  1  scalable  non-recursive           Generate permutations based on the    Countdown  lt a href  http   quickperm org   gt Quickperm algorithm lt   gt       public static  lt T gt  List lt List lt T gt  gt  generatePermutations List lt T gt  list        List lt T gt  in   new ArrayList lt  gt  list       List lt List lt T gt  gt  out   new ArrayList lt  gt  factorial list size           int n   list size        int   p   new int n  1       for  int i   0  i  lt  p length  i               p i    i            int i   0      while  i  lt  n            p i --          int j   0          if  i   2    0       odd              j   p i                        swap         T iTmp   in get i           in set i  in get j            in set j  iTmp            i   1          while  p i     0               p i    i              i                      out add new ArrayList lt  gt  in              return out     private static int factorial int num        int count   num      while  num    1            count    --num            return count      It needs Lists since generics don t play well with arrays

User · Answer

this worked for me      import java util Arrays   public class StringPermutations      public static void main String args              String inputString    ABC           permute inputString toCharArray    0  inputString length  -1              public static void permute char   ary  int startIndex  int endIndex            if startIndex    endIndex               System out println String valueOf ary             else              for int i startIndex i lt  endIndex i                       swap ary  startIndex  i                     permute ary  startIndex 1  endIndex                    swap ary  startIndex  i                                       public static void swap char   ary  int x  int y            char temp   ary x           ary x    ary y           ary y    temp

User · Answer

Here is a straightforward minimalist recursive solution in Java   public static ArrayList lt String gt  permutations String s        ArrayList lt String gt  out   new ArrayList lt String gt         if  s length      1            out add s           return out            char first   s charAt 0       String rest   s substring 1       for  String permutation   permutations rest             out addAll insertAtAllPositions first  permutation              return out    public static ArrayList lt String gt  insertAtAllPositions char ch  String s        ArrayList lt String gt  out   new ArrayList lt String gt         for  int i   0  i  lt   s length      i            String inserted   s substring 0  i    ch   s substring i           out add inserted             return out

User · Answer

Using Set operations to model  selections depending on other selections  is much easier to understand dependent permutations With dependent permutation  available selections reduce as positions are filled with selected characters from left to right   Terminal condition for recursive calls is to test if the set of available selections is empty  When terminal condition is met  a permutation is complete and it is stored to  results  List          public static List lt String gt  stringPermutation String s        List lt String gt  results   new ArrayList lt  gt         Set lt Character gt  charSet   s chars   mapToObj m - gt   char  m  collect Collectors toSet         stringPermutation charSet      results       return results     private static void stringPermutation Set lt Character gt  charSet           String prefix  List lt String gt  results        if  charSet isEmpty              results add prefix           return            for  Character c   charSet            Set lt Character gt  newSet   new HashSet lt  gt  charSet           newSet remove c           stringPermutation newSet  prefix   c  results              The code can be generalized to find permutations for a set of objects  In this case  I use a set of colors     public enum Color      ORANGE RED BULE GREEN YELLOW     public static List lt List lt Color gt  gt  colorPermutation Set lt Color gt  colors        List lt List lt Color gt  gt  results   new ArrayList lt  gt         List lt Color gt  prefix   new ArrayList lt  gt         permutation colors  prefix  results       return results     private static  lt T gt  void permutation Set lt T gt  set  List lt T gt  prefix  List lt List lt T gt  gt  results        if  set isEmpty              results add prefix           return            for  T t   set            Set lt T gt  newSet   new HashSet lt  gt  set           List lt T gt  newPrefix   new ArrayList lt  gt  prefix           newSet remove t           newPrefix add t           permutation newSet  newPrefix  results              Code for tests   public static void main String   args        List lt String gt  stringPerm   stringPermutation  abcde        System out println    of permutations     stringPerm size         stringPerm stream   forEach e - gt  System out println e         Set lt Color gt  colorSet   Arrays stream Color values    collect Collectors toSet         List lt List lt Color gt  gt  colorPerm   colorPermutation colorSet       System out println    of permutations     colorPerm size         colorPerm stream   forEach e - gt  System out println e

User · Answer

insert each character into an arraylist  static ArrayList al   new ArrayList     private static void findPermutation  String str       for  int k   0  k  lt  str length    k              addOneChar str charAt k               insert one char into ArrayList private static void addOneChar char ch       String lastPerStr      String tempStr      ArrayList locAl   new ArrayList        for  int i   0  i  lt  al size    i               lastPerStr   al get i  toString              System out println  lastPerStr      lastPerStr           for  int j   0  j  lt   lastPerStr length    j                  tempStr   lastPerStr substring 0 j    ch                        lastPerStr substring j  lastPerStr length                 locAl add tempStr                 System out println  tempStr      tempStr                       if al isEmpty             al add ch         else           al clear            al   locAl           private static void printArrayList ArrayList al       for  int i   0  i  lt  al size    i              System out print al get i

[java] Generating all permutations of a given string

Examples related to java

Examples related to algorithm