Generate list of all possible permutations of a string

Question

How would I go about generating a list of all possible permutations of a string between x and y characters in length  containing a variable list of characters   Any language would work  but it should be portable

User · Answer

I just whipped this up quick in Ruby   def perms x  y  possible characters    all          current array   all clone   1 upto y     iteration      next array          current array each    string        possible characters each    c          value   string   c         next array insert next array length  value         all insert all length  value                   current array   next array       all delete if    string  string length  lt  x   end   You might look into language API for built in permutation type functions  and you might be able to write more optimized code  but if the numbers are all that high  I m not sure there is much of a way around having a lot of results   Anyways  the idea behind the code is start with string of length 0  then keep track of all the strings of length Z where Z is the current size in the iteration   Then  go through each string and append each character onto each string   Finally at the end  remove any that were below the x threshold and return the result   I didn t test it with potentially meaningless input  null character list  weird values of x and y  etc

User · Answer

I needed this today  and although the answers already given pointed me in the right direction  they weren t quite what I wanted   Here s an implementation using Heap s method  The length of the array must be at least 3 and for practical considerations not be bigger than 10 or so  depending on what you want to do  patience and clock speed   Before you enter your loop  initialise Perm 1 To N  with the first permutation  Stack 3 To N  with zeroes   and Level with 2    At the end of the loop call NextPerm   which will return false when we re done     VB will do that for you      You can change NextPerm a little to make this unnecessary  but it s clearer like this   Option Explicit  Function NextPerm Perm   As Long  Stack   As Long  Level As Long  As Boolean Dim N As Long If Level   2 Then     Swap Perm 1   Perm 2      Level   3 Else     While Stack Level    Level - 1         Stack Level    0         If Level   UBound Stack  Then Exit Function         Level   Level   1     Wend     Stack Level    Stack Level    1     If Level And 1 Then N   1 Else N   Stack Level      Swap Perm N   Perm Level      Level   2 End If NextPerm   True End Function  Sub Swap A As Long  B As Long  A   A Xor B B   A Xor B A   A Xor B End Sub   This is just for testing  Private Sub Form Paint   Const Max   8 Dim A 1 To Max  As Long  I As Long Dim S 3 To Max  As Long  J As Long Dim Test As New Collection  T As String For I   1 To UBound A      A I    I Next Cls ScaleLeft   0 J   2 Do     If CurrentY   TextHeight  0    gt  ScaleHeight Then         ScaleLeft   ScaleLeft - TextWidth   0       UBound A    1          CurrentY   0         CurrentX   0     End If     T   vbNullString     For I   1 To UBound A          Print A I           T   T  amp  Hex A I       Next     Print     Test Add Null  T Loop While NextPerm A  S  J  J   1 For I   2 To UBound A      J   J   I Next If J  lt  gt  Test Count Then Stop End Sub   Other methods are described by various authors  Knuth describes two  one gives lexical order  but is complex and slow  the other is known as the method of plain changes  Jie Gao and Dianjun Wang also wrote an interesting paper

User · Answer

This is a translation of Mike s Ruby version  into Common Lisp    defun perms  x y original-string     loop with all    list             with current-array    list             for iteration from 1 to y         do  loop with next-array   nil                  for string in current-array                  do  loop for c across original-string                           for value    concatenate  string string  string c                             do  push value next-array                                push value all                        setf current-array  reverse next-array            finally  return  nreverse  delete-if    lambda  el    lt   length el  x   all        And another version  slightly shorter and using more loop facility features    defun perms  x y original-string     loop repeat y         collect  loop for string in  or  car  last sets    list                            append  loop for c across original-string                                    collect  concatenate  string string  string c     into sets         finally  return  loop for set in sets                               append  loop for el in set when   gt    length el  x  collect el

User · Answer

There are several ways to do this  Common methods use recursion  memoization  or dynamic programming  The basic idea is that you produce a list of all strings of length 1  then in each iteration  for all strings produced in the last iteration  add that string concatenated with each character in the string individually   the variable index in the code below keeps track of the start of the last and the next iteration   Some pseudocode   list   originalString split     index    0 0  list        for iteration n in 1 to y    index    index 1   len list     for string s in list subset index 0  to end       for character c in originalString        list add s   c    you d then need to remove all strings less than x in length  they ll be the first  x-1    len originalString  entries in the list

User · Answer

Recursive Solution with driver main   method   public class AllPermutationsOfString   public static void stringPermutations String newstring  String remaining        if remaining length    0          System out println newstring        for int i 0  i lt remaining length    i              String newRemaining   remaining replaceFirst remaining charAt i                   stringPermutations newstring remaining charAt i   newRemaining            public static void main String   args        String string    abc       AllPermutationsOfString stringPermutations     string

User · Answer

You are going to get a lot of strings  that s for sure      Where x and y is how you define them and r is the number of characters we are selecting from --if I am understanding you correctly  You should definitely generate these as needed and not get sloppy and say  generate a powerset and then filter the length of strings   The following definitely isn t the best way to generate these  but it s an interesting aside  none-the-less   Knuth  volume 4  fascicle 2  7 2 1 3  tells us that  s t -combination is equivalent to s 1 things taken t at a time with repetition -- an  s t -combination is notation used by Knuth that is equal to   We can figure this out by first generating each  s t -combination in binary form  so  of length  s t   and counting the number of 0 s to the left of each 1   10001000011101 --  becomes the permutation   0  3  4  4  4  1

User · Answer

Here is a simple word C  recursive solution   Method   public ArrayList CalculateWordPermutations string   letters  ArrayList words  int index                        bool finished   true              ArrayList newWords   new ArrayList                if  words Count    0                                foreach  string letter in letters                                        words Add letter                                                for int j index  j lt words Count  j                                  string word    string words j                   for int i  0  i lt letters Length  i                                          if  word Contains letters i                                                  finished   false                          string newWord    string word Clone                            newWord    letters i                           newWords Add newWord                                                                      foreach  string newWord in newWords                                   words Add newWord                              if finished     false                                CalculateWordPermutations letters  words  words Count - newWords Count                             return words              Calling   string   letters   new string    a   b   c    ArrayList words   CalculateWordPermutations letters  new ArrayList    0

User · Answer

The pythonic solution     from itertools import permutations s    ABCDEF  p       join x  for x in permutations s

User · Answer

The possible string permutations can be computed using recursive function  Below is one of the possible solution   public static String insertCharAt String s  int index  char c            StringBuffer sb   new StringBuffer s           StringBuffer sbb   sb insert index  c           return sbb toString       public static ArrayList lt String gt  getPerm String s  int index            ArrayList lt String gt  perm   new ArrayList lt String gt              if  index    s length  -1                perm add String valueOf s charAt index                 return perm                     ArrayList lt String gt  p   getPerm s  index 1           char c   s charAt index            for String pp   p                for  int idx 0  idx lt pp length   1  idx                      String ss   insertCharAt pp  idx  c                   perm add ss                                    return perm         public static void testGetPerm String s            ArrayList lt String gt  perm   getPerm s 0           System out println s   -- gt  total permutation are      perm size             System out println perm toString

User · Answer

c  iterative   public List lt string gt  Permutations char   chars                List lt string gt  words   new List lt string gt             words Add chars 0  ToString             for  int i   1  i  lt  chars Length    i                        int currLen   words Count              for  int j   0  j  lt  currLen    j                                var w   words j                   for  int k   0  k  lt   w Length    k                                        var nstr   w Insert k  chars i  ToString                         if  k    0                          words j    nstr                      else                         words Add nstr                                                     return words

User · Answer

In Perl  if you want to restrict yourself to the lowercase alphabet  you can do this   my  result     a      zzzz      This gives all possible strings between 1 and 4 characters using lowercase characters  For uppercase  change  a  to  A  and  zzzz  to  ZZZZ    For mixed-case it gets much harder  and probably not doable with one of Perl s builtin operators like that

User · Answer

It s better to use backtracking     include  lt stdio h gt   include  lt string h gt   void swap char  a  char  b        char temp      temp    a       a    b       b   temp     void print char  a  int i  int n        int j      if i    n            printf   s n   a         else           for j   i  j  lt   n  j                  swap a   i  a   j               print a  i   1  n               swap a   i  a   j                      int main void        char a 100       gets a       print a  0  strlen a  - 1       return 0

User · Answer

Though this doesn t answer your question exactly  here s one way to generate every permutation of the letters from a number of strings of the same length  eg  if your words were  coffee    joomla  and  moodle   you can expect output like  coodle    joodee    joffle   etc   Basically  the number of combinations is the  number of words  to the power of  number of letters per word   So  choose a random number between 0 and the number of combinations - 1  convert that number to base  number of words   then use each digit of that number as the indicator for which word to take the next letter from   eg  in the above example  3 words  6 letters   729 combinations  Choose a random number  465  Convert to base 3  122020  Take the first letter from word 1  2nd from word 2  3rd from word 2  4th from word 0    and you get     joofle    If you wanted all the permutations  just loop from 0 to 728  Of course  if you re just choosing one random value  a much simpler less-confusing way would be to loop over the letters  This method lets you avoid recursion  should you want all the permutations  plus it makes you look like you know Maths tm    If the number of combinations is excessive  you can break it up into a series of smaller words and concatenate them at the end

User · Answer

def permutation str    posibilities        str split     each do  char      if posibilities size    0       posibilities 0    char downcase       posibilities 1    char upcase     else       posibilities count   posibilities length       posibilities   posibilities   posibilities       posibilities count times do  i          posibilities i     char downcase         posibilities i posibilities count     char upcase       end     end   end   posibilities end   Here is my take on a non recursive version

User · Answer

Recursive solution in C        int main  int argc  char   const argv              string s    sarp           bool used  4           permute 0      used  s      void permute int level  string permuted  bool used     string  amp original        int length   original length         if level    length       permutation complete  display         cout  lt  lt  permuted  lt  lt  endl        else           for int i 0  i lt length  i         try to add an unused character             if  used i                     used i    true                  permute level 1  original i    permuted  used  original      find the permutations starting with this string                 used i    false

User · Answer

import java util     public class all subsets       public static void main String   args            String a    abcd           for String s  all perm a                 System out println s                        public static Set lt String gt  concat String c  Set lt String gt  lst            HashSet lt String gt  ret set   new HashSet lt String gt             for String s  lst                ret set add c s                     return ret set             public static HashSet lt String gt  all perm String a            HashSet lt String gt  set   new HashSet lt String gt             if a length      1                set add a             else               for int i 0  i lt a length    i                      set addAll concat a charAt i      all perm a substring 0  i  a substring i 1  a length                                        return set

User · Answer

The following Java recursion prints all permutations of a given string     call it as permut    str    public void permut String str1 String str2       if str2 length      0           char ch   str2 charAt 0           for int i   0  i  lt   str1 length   i                permut str1 substring 0 i    ch   str1 substring i str1 length                          str2 substring 1 str2 length           else      System out println str1             Following is the updated version of above  permut  method which makes n   n factorial  less recursive calls compared to the above method    call it as permut    str    public void permut String str1 String str2      if str2 length    gt  1          char ch   str2 charAt 0          for int i   0  i  lt   str1 length   i              permut str1 substring 0 i    ch   str1 substring i str1 length                      str2 substring 1 str2 length          else      char ch   str2 charAt 0       for int i   0  i  lt   str1 length   i            System out println str1 substring 0 i    ch      str1 substring i str1 length                      str2 substring 1 str2 length

User · Answer

There are a lot of good answers here  I also suggest a very simple recursive solution in C      include  lt string gt   include  lt iostream gt   template lt typename Consume gt  void permutations std  string s  Consume consume  std  size t start   0        if  start    s length    consume s       for  std  size t i   start  i  lt  s length    i              std  swap s start   s i            permutations s  consume  start   1            int main void        std  string s    abcd       permutations s     std  string s            std  cout  lt  lt  s  lt  lt  std  endl              Note  strings with repeated characters will not produce unique permutations

User · Answer

Non recursive solution according to Knuth  Python example     def nextPermutation perm       k0   None     for i in range len perm -1           if perm i  lt perm i 1               k0 i     if k0    None          return None      l0   k0 1     for i in range k0 1  len perm            if perm k0   lt  perm i               l0   i      perm k0   perm l0    perm l0   perm k0      perm k0 1     reversed perm k0 1        return perm  perm list  12345   while perm      print perm     perm   nextPermutation perm

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

This code in python  when called with allowed characters set to  0 1  and 4 character max  would generate 2 4 results     0000    0001    0010    0011    0100    0101    0110    0111    1000    1001    1010    1011    1100    1101    1110    1111    def generate permutations chars   4      modify if in need      allowed chars              0            1              status          for tmp in range chars            status append 0       last char   len allowed chars       rows          for x in xrange last char    chars            rows append             for y in range chars - 1   -1  -1                key   status y              rows x    allowed chars key    rows x           for pos in range chars - 1  -1  -1                if status pos     last char - 1                    status pos    0             else                   status pos     1                 break       return rows  import sys   print generate permutations     Hope this is of use to you  Works with any character  not only numbers

User · Answer

def gen  x y list    to generate all strings inserting y at different positions list      list append  y x   for i in range  len x         list append  func x 0 i    y   func x i 1 len x -1    return list   def func  x i j     returns x i  j  z       for i in range i j 1       z   z x i  return z   def perm  x   length   list     perm function if length    1     base case     list append  x len x -1        return list  else      lists   perm  x   length-1  list       lists temp   lists  temporarily storing the list      lists          for i in range  len lists temp              list temp   gen lists temp i  x length-2  lists          lists    list temp      return lists

User · Answer

code written for java language    package namo algorithms   import java util Scanner   public class Permuations      public static int totalPermutationsCount   0      public static void main String   args             Scanner sc   new Scanner System in           System out println  input string               String inputString   sc nextLine            System out println  given input String    gt    inputString       length is     inputString length             findPermuationsOfString -1  inputString           System out println                                                    System out println  total permutation strings    gt    totalPermutationsCount               public  static void findPermuationsOfString int fixedIndex  String inputString            int currentIndex   fixedIndex  1           for  int i   currentIndex  i  lt  inputString length    i                    swap elements and call the findPermuationsOfString                char   carr   inputString toCharArray                char tmp   carr currentIndex               carr currentIndex    carr i               carr i    tmp              inputString    new String carr                  System out println  chat At   current String    gt    inputString charAt currentIndex                if currentIndex    inputString length  -1                    totalPermutationsCount                    System out println  permuation string    gt    inputString                 else                     System out println  in else block gt  gt  gt  gt                     findPermuationsOfString currentIndex  inputString                    char   rarr   inputString toCharArray                        char rtmp   carr i                       carr i    carr currentIndex                       carr currentIndex    rtmp                      inputString    new String carr

User · Answer

and here is the C version   void permute const char  s  char  out  int  used  int len  int lev        if  len    lev            out lev      0           puts out           return             int i      for  i   0  i  lt  len    i            if    used i               continue           used i    1          out lev    s i           permute s  out  used  len  lev   1           used i    0            return

User · Answer

A recursive solution in python  The good thing about this code is that it exports a dictionary  with keys as strings and all possible permutations as values  All possible string lengths are included  so in effect  you are creating a superset   If you only require the final permutations  you can delete other keys from the dictionary   In this code  the dictionary of permutations is global   At the base case  I store the value as both possibilities in a list  perms  ab       ab   ba     For higher string lengths  the function refers to lower string lengths and incorporates the previously calculated permutations   The function does two things    calls itself with a smaller string returns a list of permutations of a particular string if already available  If returned to itself  these will be used to append to the character and create newer permutations    Expensive for memory    perms      def perm input string       global perms     if input string in perms          return perms input string    This will send a list of all permutations     elif len input string     2          perms input string     input string  input string -1    input string  -2           return perms input string      else          perms input string               for index in range 0  len input string                new string   input string 0 index    input string index  1               perm new string              for entries in perms new string                   perms input string  append input string index    entries      return perms input string

User · Answer

In ruby   str    a  100 000 000 times  puts str next     It is quite fast  but it is going to take some time     Of course  you can start at  aaaaaaaa  if the short strings aren t interesting to you   I might have misinterpreted the actual question though - in one of the posts it sounded as if you just needed a bruteforce library of strings  but in the main question it sounds like you need to permutate a particular string   Your problem is somewhat similar to this one  http   beust com weblog archives 000491 html  list all integers in which none of the digits repeat themselves  which resulted in a whole lot of languages solving it  with the ocaml guy using permutations  and some java guy using yet another solution

User · Answer

Here s a non-recursive version I came up with  in javascript  It s not based on Knuth s non-recursive one above  although it has some similarities in element swapping  I ve verified its correctness for input arrays of up to 8 elements   A quick optimization would be pre-flighting the out array and avoiding push     The basic idea is    Given a single source array  generate a first new set of arrays which swap the first element with each subsequent element in turn  each time leaving the other elements unperturbed  eg  given 1234  generate 1234  2134  3214  4231  Use each array from the previous pass as the seed for a new pass  but instead of swapping the first element  swap the second element with each subsequent element  Also  this time  don t include the original array in the output  Repeat step 2 until done    Here is the code sample   function oxe perm src  depth  index        var perm   src slice           duplicates src      perm   perm split          perm depth    src index       perm index    src depth       perm   perm join          return perm     function oxe permutations src        out   new Array         out push src        for  depth   0  depth  lt  src length  depth              var numInPreviousPass   out length          for  var m   0  m  lt  numInPreviousPass    m                for  var n   depth   1  n  lt  src length    n                    out push oxe perm out m   depth  n                                       return out

User · Answer

permute  ABC  -  A perm BC  -  A perm B perm C   -  A perm   BC    CB    -     ABC    BAC    BCA      ACB    CAB    CBA      To remove duplicates when inserting each alphabet check to see if previous string ends with the same alphabet  why  -exercise    public static void main String   args         for  String str   permStr  ABBB             System out println str            static Vector lt String gt  permStr String str        if  str length      1           Vector lt String gt  ret   new Vector lt String gt             ret add str           return ret             char start   str charAt 0       Vector lt String gt  endStrs   permStr str substring 1        Vector lt String gt  newEndStrs   new Vector lt String gt         for  String endStr   endStrs           for  int j   0  j  lt   endStr length    j                 if  endStr substring 0  j  endsWith String valueOf start                    break              newEndStrs add endStr substring 0  j    String valueOf start    endStr substring j                        return newEndStrs      Prints all permutations sans duplicates

User · Answer

Here is a simple solution in C    It generates only the distinct permutations of a given string       static public IEnumerable lt string gt  permute string word                if  word Length  gt  1                         char character   word 0               foreach  string subPermute in permute word Substring 1                                   for  int index   0  index  lt   subPermute Length  index                                          string pre   subPermute Substring 0  index                       string post   subPermute Substring index                        if  post Contains character                               continue                                              yield return pre   character   post                                                     else                       yield return word

User · Answer

You might look at  Efficiently Enumerating the Subsets of a Set   which describes an algorithm to do part of what you want - quickly generate all subsets of N characters from length x to y   It contains an implementation in C     For each subset  you d still have to generate all the permutations   For instance if you wanted 3 characters from  abcde   this algorithm would give you  abc   abd    abe     but you d have to permute each one to get  acb    bac    bca   etc

User · Answer

Many of the previous answers used backtracking  This is the asymptotically optimal way O n n   of generating permutations after initial sorting class Permutation           runtime -O n  for generating nextPermutaion        and O n n   for generating all n  permutations with increasing sorted array as start        return true  if there exists next lexicographical sequence        e g  a b c  3- gt  true  modifies array to  a c b         e g  c b a  3- gt  false  as it is largest lexicographic possible        public static boolean nextPermutation char   seq  int len               1         if  len  lt   1              return false    no more perm            2  Find last j such that seq j   lt   seq j 1   Terminate if no such j exists         int j   len - 2          while  j  gt   0  amp  amp  seq j   gt   seq j   1                 --j                    if  j    -1              return false    no more perm            3  Find last l such that seq j   lt   seq l   then exchange elements j and l         int l   len - 1          while  seq j   gt   seq l                 --l                    swap seq  j  l              4  Reverse elements j 1     count-1          reverseSubArray seq  j   1  len - 1              return seq  add store next perm          return true            private static void swap char   a  int i  int j            char temp   a i           a i    a j           a j    temp             private static void reverseSubArray char   a  int lo  int hi            while  lo  lt  hi                swap a  lo  hi                 lo              --hi                      public static void main String   args            String str    quot abcdefg quot           char   array   str toCharArray            Arrays sort array           int cnt 0          do               System out println new String array                cnt             while nextPermutation array  array length            System out println cnt    5040 7              if we use  quot bab quot - gt   quot abb quot    quot bab quot    quot bba quot   3  permutations

User · Answer

I m not sure why you would want to do this in the first place  The resulting set for any moderately large values of x and y will be huge  and will grow exponentially as x and or y get bigger    Lets say your set of possible characters is the 26 lowercase letters of the alphabet  and you ask your application to generate all permutations where length   5  Assuming you don t run out of memory you ll get 11 881 376  i e  26 to the power of 5  strings back  Bump that length up to 6  and you ll get 308 915 776 strings back  These numbers get painfully large  very quickly   Here s a solution I put together in Java  You ll need to provide two runtime arguments  corresponding to x and y   Have fun   public class GeneratePermutations       public static void main String   args            int lower   Integer parseInt args 0            int upper   Integer parseInt args 1             if  upper  lt  lower    upper    0    lower    0                System exit 0                      for  int length   lower  length  lt   upper  length                  generate length                            private static void generate int length  String partial            if  length  lt   0                System out println partial             else               for  char c    a   c  lt    z   c                      generate length - 1  partial   c

User · Answer

Some working Java code based on Sarp s answer   public class permute        static void permute int level  String permuted                      boolean used    String original            int length   original length            if  level    length                System out println permuted             else               for  int i   0  i  lt  length  i                      if   used i                         used i    true                      permute level   1  permuted   original charAt i                          used  original                       used i    false                                                       public static void main String   args            String s    hello           boolean used      false  false  false  false  false           permute 0      used  s

User · Answer

Recursive Approach func StringPermutations inputStr string   permutations   string        for i    0  i  lt  len inputStr   i             inputStr   inputStr 1     inputStr 0 1          if len inputStr   lt   2               permutations   append permutations  inputStr              continue                   leftPermutations    StringPermutations inputStr 0   len inputStr -1           for    leftPermutation    range leftPermutations               permutations   append permutations  leftPermutation inputStr len inputStr -1                        return

User · Answer

Here is a link that describes how to print permutations of a string   http   nipun-linuxtips blogspot in 2012 11 print-all-permutations-of-characters-in html

User · Answer

Ruby answer that works   class String   def each char with index     0 upto size - 1  do  index        yield self index  index   index      end   end   def remove char at index      return self 1  -1  if index    0     self 0   index-1     self  index 1   -1    end end  def permute str  prefix         if str size    0     puts prefix     return   end   str each char with index do  char  index      permute str remove char at index   prefix   char    end end    example   permute  abc

[string] Generate list of all possible permutations of a string

Examples related to string

Examples related to language-agnostic

Examples related to cross-platform