Listing all permutations of a string integer

Question

A common task in programming interviews  not from my experience of interviews though  is to take a string or an integer and list every possible permutation   Is there an example of how this is done and the logic behind solving such a problem   I ve seen a few code snippets but they weren t well commented explained and thus hard to follow

User · Answer

Generic C  Method             private static List lt T   gt  GetPerms lt T gt  T   input  int startIndex   0                                var perms   new List lt T   gt                      var l   input Length - 1                   if  l    startIndex                      perms Add input                   else                                        for  int i   startIndex  i  lt   l  i                                                  var copy   input ToArray      make copy                          var temp   copy startIndex                            copy startIndex    copy i                           copy i    temp                           perms AddRange GetPerms copy  startIndex   1                                                              return perms                               usages             char   charArray   new char      A    B    C                 var charPerms   GetPerms charArray                 string   stringArray   new string      Orange    Mango    Apple                 var stringPerms   GetPerms stringArray                 int   intArray   new int     1  2  3                var intPerms   GetPerms intArray

User · Answer

This is my solution which it is easy for me to understand  class ClassicPermutationProblem       ClassicPermutationProblem            private static void PopulatePosition lt T gt  List lt List lt T gt  gt  finalList  List lt T gt  list  List lt T gt  temp  int position                 foreach  T element in list                          List lt T gt  currentTemp   temp ToList                 if   currentTemp Contains element                   currentTemp Add element                else                 continue                if  position    list Count                  finalList Add currentTemp                else                 PopulatePosition finalList  list  currentTemp  position   1                        public static List lt List lt int gt  gt  GetPermutations List lt int gt  list                List lt List lt int gt  gt  results   new List lt List lt int gt  gt             PopulatePosition results  list  new List lt int gt     1           return results            static void Main string   args        List lt List lt int gt  gt  results   ClassicPermutationProblem GetPermutations new List lt int gt      1  2  3

User · Answer

Here is the function which will print all permutations recursively    public void Permutations string input  StringBuilder sb                if  sb Length    input Length                        Console WriteLine sb ToString                 return                     char   inChar   input ToCharArray             for  int i   0  i  lt  input Length  i                          if   sb ToString   Contains inChar i                                  sb Append inChar i                    Permutations input  sb                       RemoveChar sb  inChar i                                   private bool RemoveChar StringBuilder input  char toRemove                int index   input ToString   IndexOf toRemove           if  index  gt   0                        input Remove index  1               return true                    return false

User · Answer

Here is the function which will print all permutaion  This function implements logic Explained by peter   public class Permutation         http   www java2s com Tutorial Java 0100  Class-Definition RecursivemethodtofindallpermutationsofaString htm      public static void permuteString String beginningString  String endingString                            if  endingString Length  lt   1              Console WriteLine beginningString   endingString           else             for  int i   0  i  lt  endingString Length  i                                   String newString   endingString Substring 0  i    endingString Substring i   1                    permuteString beginningString   endingString ElementAt i   newString                               static void Main string   args                 Permutation permuteString String Empty   abc            Console ReadLine

User · Answer

Building on  Peter s solution  here s a version that declares a simple LINQ-style Permutations   extension method that works on any IEnumerable lt T gt    Usage  on string characters example    foreach  var permutation in  abc  Permutations          Console WriteLine string Join       permutation        Outputs   a  b  c a  c  b b  a  c b  c  a c  b  a c  a  b   Or on any other collection type   foreach  var permutation in  new      Apples    Oranges    Pears    Permutations          Console WriteLine string Join       permutation        Outputs   Apples  Oranges  Pears Apples  Pears  Oranges Oranges  Apples  Pears Oranges  Pears  Apples Pears  Oranges  Apples Pears  Apples  Oranges   using System  using System Collections Generic  using System Linq   public static class PermutationExtension       public static IEnumerable lt T   gt  Permutations lt T gt  this IEnumerable lt T gt  source                var sourceArray   source ToArray            var results   new List lt T   gt             Permute sourceArray  0  sourceArray Length - 1  results           return results             private static void Swap lt T gt  ref T a  ref T b                T tmp   a          a   b          b   tmp             private static void Permute lt T gt  T   elements  int recursionDepth  int maxDepth  ICollection lt T   gt  results                if  recursionDepth    maxDepth                        results Add elements ToArray                 return                     for  var i   recursionDepth  i  lt   maxDepth  i                          Swap ref elements recursionDepth   ref elements i                Permute elements  recursionDepth   1  maxDepth  results               Swap ref elements recursionDepth   ref elements i

User · Answer

Here is a C  answer which is a little simplified   public static void StringPermutationsDemo         strBldr   new StringBuilder         string result   Permute  ABCD  ToCharArray    0       MessageBox Show result           static string Permute char   elementsList  int startIndex        if  startIndex    elementsList Length                foreach  char element in elementsList                        strBldr Append       element                     strBldr AppendLine                else               for  int tempIndex   startIndex  tempIndex  lt   elementsList Length - 1  tempIndex                          Swap ref elementsList startIndex   ref elementsList tempIndex                 Permute elementsList   startIndex   1                 Swap ref elementsList startIndex   ref elementsList tempIndex                         return strBldr ToString       static void Swap ref char Char1  ref char Char2        char tempElement   Char1      Char1   Char2      Char2   tempElement      Output   1 2 3 1 3 2  2 1 3 2 3 1  3 2 1 3 1 2

User · Answer

Slightly modified version in C  that yields needed permutations in an array of ANY type          USAGE  create an array of any type  and call Permutations       var vals   new     a    bb    ccc        foreach  var v in Permutations vals           Console WriteLine string Join      v       Print values separated by comma   public static IEnumerable lt T   gt  Permutations lt T gt  T   values  int fromInd   0        if  fromInd   1    values Length          yield return values      else               foreach  var v in Permutations values  fromInd   1               yield return v           for  var i   fromInd   1  i  lt  values Length  i                          SwapValues values  fromInd  i               foreach  var v in Permutations values  fromInd   1                   yield return v              SwapValues values  fromInd  i                      private static void SwapValues lt T gt  T   values  int pos1  int pos2        if  pos1    pos2                T tmp   values pos1           values pos1    values pos2           values pos2    tmp

User · Answer

Here s a good article covering three algorithms for finding all permutations  including one to find the next permutation   http   www cut-the-knot org do you know AllPerm shtml  C   and Python have built-in next permutation and itertools permutations functions respectively

User · Answer

Here is a simple solution in c  using recursion   void Main         string word    abc       WordPermuatation    word      void WordPermuatation string prefix  string word        int n   word Length      if  n    0    Console WriteLine prefix         else               for  int i   0  i  lt  n  i                          WordPermuatation prefix   word i  word Substring 0  i    word Substring i   1  n -  i 1

User · Answer

Recursion is not necessary  here is good information about this solution   var values1   new     1  2  3  4  5     foreach  var permutation in values1 GetPermutations          Console WriteLine string Join       permutation       var values2   new      a    b    c    d    e      foreach  var permutation in values2 GetPermutations          Console WriteLine string Join       permutation       Console ReadLine      I have been used this algorithm for years  it has O N  time and space complexity to calculate each permutation    public static class SomeExtensions       public static IEnumerable lt IEnumerable lt T gt  gt  GetPermutations lt T gt  this IEnumerable lt T gt  enumerable                var array   enumerable as T      enumerable ToArray             var factorials   Enumerable Range 0  array Length   1               Select Factorial               ToArray             for  var i   0L  i  lt  factorials array Length   i                          var sequence   GenerateSequence i  array Length - 1  factorials                yield return GeneratePermutation array  sequence                        private static IEnumerable lt T gt  GeneratePermutation lt T gt  T   array  IReadOnlyList lt int gt  sequence                var clone    T    array Clone             for  int i   0  i  lt  clone Length - 1  i                          Swap ref clone i   ref clone i   sequence i                        return clone             private static int   GenerateSequence long number  int size  IReadOnlyList lt long gt  factorials                var sequence   new int size            for  var j   0  j  lt  sequence Length  j                          var facto   factorials sequence Length - j                sequence j     int  number   facto               number    int  number   facto                      return sequence             static void Swap lt T gt  ref T a  ref T b                T temp   a          a   b          b   temp             private static long Factorial int n                long result   n           for  int i   1  i  lt  n  i                          result   result   i                     return result

User · Answer

Here is the simplest solution I can think of   let rec distribute e   function        - gt    e       x  xs  as xs - gt   e  xs    for xs in distribute e xs  - gt  x  xs   let permute xs   Seq fold  fun ps x - gt  List collect  distribute x  ps       xs   The distribute function takes a new element e and an n-element list and returns a list of n 1 lists each of which has e inserted at a different place  For example  inserting 10 at each of the four possible places in the list  1 2 3     gt  distribute 10  1  3    val it   int list list       10  1  2  3    1  10  2  3    1  2  10  3    1  2  3  10     The permute function folds over each element in turn distributing over the permutations accumulated so far  culminating in all permutations  For example  the 6 permutations of the list  1 2 3     gt  permute  1 2 3    val it   int list list       3  2  1    2  3  1    2  1  3    3  1  2    1  3  2    1  2  3     Changing the fold to a scan in order to keep the intermediate accumulators sheds some light on how the permutations are generated an element at a time    gt  Seq scan  fun ps x - gt  List collect  distribute x  ps        1  3    val it   seq lt int list list gt      seq              1      2  1    1  2           3  2  1    2  3  1    2  1  3    3  1  2    1  3  2    1  2  3

User · Answer

First of all  it smells like recursion of course  Since you also wanted to know the principle  I did my best to explain it human language  I think recursion is very easy most of the times  You only have to grasp two steps   The first step All the other steps  all with the same logic   In human language   In short   The permutation of 1 element is one element  The permutation of a set of elements is a list each of the elements  concatenated with every permutation of the other elements   Example  If the set just has one element -- gt  return it  perm a  - gt  a If the set has two characters  for each element in it  return the element  with the permutation of the rest of the elements added  like so  perm ab     - gt   a   perm b  - gt  ab  b   perm a  - gt  ba  Further  for each character in the set  return a character  concatenated with a permutation of  gt  the rest of the set perm abc  - gt  a   perm bc  -- gt   abc  acb b   perm ac  -- gt   bac  bca c   perm ab  -- gt   cab  cba perm abc   z  -- gt  a   perm       b   perm              I found the pseudocode on http   www programmersheaven com mb Algorithms 369713 369713 permutation-algorithm-help   makePermutations permutation      if  length permutation  lt  required length        for  i   min digit to max digit          if  i not in permutation            makePermutations permutation i                      else       add permutation to list        C  OK  and something more elaborate  and since it is tagged c     from http   radio weblogs com 0111551 stories 2002 10 14 permutations html   Rather lengthy  but I decided to copy it anyway  so the post is not dependent on the original   The function takes a string of characters  and writes down every possible permutation of that exact string  so for example  if  quot ABC quot  has been supplied  should spill out   ABC  ACB  BAC  BCA  CAB  CBA  Code  class Program       private static void Swap ref char a  ref char b                if  a    b  return           var temp   a          a   b          b   temp             public static void GetPer char   list                int x   list Length - 1          GetPer list  0  x              private static void GetPer char   list  int k  int m                if  k    m                        Console Write list                     else             for  int i   k  i  lt   m  i                                     Swap ref list k   ref list i                       GetPer list  k   1  m                      Swap ref list k   ref list i                             static void Main                 string str    quot sagiv quot           char   arr   str ToCharArray            GetPer arr

User · Answer

If performance and memory is an issue  I suggest this very efficient implementation  According to Heap s algorithm in Wikipedia  it should be the fastest  Hope it will fits your need  -     Just as comparison of this with a Linq implementation for 10   code included     This  36288000 items in 235 millisecs Linq  36288000 items in 50051 millisecs  using System  using System Collections Generic  using System Diagnostics  using System Linq  using System Runtime CompilerServices  using System Text   namespace WpfPermutations            lt summary gt          EO  2016-04-14         Generator of all permutations of an array of anything          Base on Heap s Algorithm  See  https   en wikipedia org wiki Heap 27s algorithm cite note-3          lt  summary gt      public static class Permutations                    lt summary gt              Heap s algorithm to find all pmermutations  Non recursive  more efficient               lt  summary gt               lt param name  items  gt Items to permute in each possible ways lt  param gt               lt param name  funcExecuteAndTellIfShouldStop  gt  lt  param gt               lt returns gt Return true if cancelled lt  returns gt           public static bool ForAllPermutation lt T gt  T   items  Func lt T    bool gt  funcExecuteAndTellIfShouldStop                        int countOfItem   items Length               if  countOfItem  lt   1                                return funcExecuteAndTellIfShouldStop items                              var indexes   new int countOfItem               for  int i   0  i  lt  countOfItem  i                                  indexes i    0                             if  funcExecuteAndTellIfShouldStop items                                 return true                             for  int i   1  i  lt  countOfItem                                 if  indexes i   lt  i                       On the web there is an implementation with a multiplication which should be less efficient                      if   i  amp  1     1     if  i   2    1       more efficient     At least the same                                                Swap ref items i   ref items indexes i                                               else                                               Swap ref items i   ref items 0                                               if  funcExecuteAndTellIfShouldStop items                                                 return true                                             indexes i                         i   1                                    else                                       indexes i      0                                               return false                          lt summary gt              This function is to show a linq way but is far less efficient              lt  summary gt               lt typeparam name  T  gt  lt  typeparam gt               lt param name  list  gt  lt  param gt               lt param name  length  gt  lt  param gt               lt returns gt  lt  returns gt          static IEnumerable lt IEnumerable lt T gt  gt  GetPermutations lt T gt  IEnumerable lt T gt  list  int length                        if  length    1  return list Select t   gt  new T     t                  return GetPermutations list  length - 1                   SelectMany t   gt  list Where e   gt   t Contains e                         t1  t2    gt  t1 Concat new T     t2                              lt summary gt              Swap 2 elements of same type              lt  summary gt               lt typeparam name  T  gt  lt  typeparam gt               lt param name  a  gt  lt  param gt               lt param name  b  gt  lt  param gt           MethodImpl MethodImplOptions AggressiveInlining           static void Swap lt T gt  ref T a  ref T b                        T temp   a              a   b              b   temp                          lt summary gt              Func to show how to call  It does a little test for an array of 4 items               lt  summary gt          public static void Test                         ForAllPermutation  123  ToCharArray     vals    gt                                Debug Print String Join     vals                    return false                               int   values   new int     0  1  2  4                 Debug Print  Non Linq                ForAllPermutation values   vals    gt                                Debug Print String Join     vals                    return false                               Debug Print  Linq                foreach var v in GetPermutations values  values Length                                 Debug Print String Join     v                                  Performance             int count   0               values   new int 10               for int n   0  n  lt  values Length  n                                  values n    n                             Stopwatch stopWatch   new Stopwatch                stopWatch Reset                stopWatch Start                 ForAllPermutation values   vals    gt                                foreach var v in vals                                        count                                      return false                               stopWatch Stop                Debug Print   Non Linq  count  items in  stopWatch ElapsedMilliseconds  millisecs                 count   0              stopWatch Reset                stopWatch Start                 foreach  var vals in GetPermutations values  values Length                                 foreach  var v in vals                                        count                                                 stopWatch Stop                Debug Print   Linq  count  items in  stopWatch ElapsedMilliseconds  millisecs

User · Answer

I hope this will suffice  using System                   public class Program       public static void Main                   Example using word cat         permute  quot cat quot                static void permute string word       for int i 0  i  lt  word Length  i             char start   word 0           for int j 1  j  lt  word Length  j                 string left   word Substring 1 j-1               string right   word Substring j               Console WriteLine start right left                     if i 1  lt  word Length               word   wordChange word  i   1                                   static string wordChange string word  int index       string newWord    quot  quot       for int i 0  i lt word Length  i             if i   0              newWord    word index           else if i   index              newWord    word 0           else             newWord    word i             return newWord     output  cat cta act atc tca tac

User · Answer

Base Revise on Pengyang answer And inspired from permutations-in-javascript  The c  version FunctionalPermutations should be this  static IEnumerable lt IEnumerable lt T gt  gt  FunctionalPermutations lt T gt  IEnumerable lt T gt  elements  int length                if  length  lt  2  return elements Select t   gt  new T     t                Pengyang answser             return  recur  list  length - 1  SelectMany t   gt  list Where e   gt   t Contains e    t1  t2    gt  t1 Concat new T     t2                         return elements SelectMany  element i  i    gt             FunctionalPermutations elements Take i  Concat elements Skip i   1    length - 1               Select sub ei   gt  new     element i   Concat sub ei

User · Answer

Lists permutations of a string  Avoids duplication when characters are repeated   using System  using System Collections   class Permutation    static IEnumerable Permutations string word       if  word    null    word Length  lt   1          yield return word        yield break             char firstChar   word 0       foreach  string subPermute in Permutations  word Substring  1             int indexOfFirstChar   subPermute IndexOf  firstChar         if  indexOfFirstChar    -1  indexOfFirstChar   subPermute Length         for  int index   0  index  lt   indexOfFirstChar  index             yield return subPermute Insert  index  new string  firstChar  1                 static void Main        foreach  var permutation in Permutations   aab           Console WriteLine  permutation

User · Answer

void permute  char  str  int ptr      int i  len    len   strlen str     if  ptr    len        printf    s n   str       return         for  i   ptr   i  lt  len   i          swap   amp str ptr    amp str i        permute  str  ptr   1       swap   amp str ptr    amp str i            You can write your swap function to swap characters  This is to be called as permute string  0

User · Answer

First of all  sets have permutations  not strings or integers  so I ll just assume you mean  the set of characters in a string    Note that a set of size n has n  n-permutations   The following pseudocode  from Wikipedia   called with k   1   n  will give all the permutations   function permutation k  s        for j   2 to length s            swap s  k mod j    1  with s j      note that our array is indexed starting at 1         k    k   j     integer division cuts off the remainder           return s      Here s the equivalent Python code  for 0-based array indexes    def permutation k  s       r   s        for j in range 2  len s  1           r j-1   r k j    r k j   r j-1          k   k j 1     return r

User · Answer

Here is one more implementation of the algo mentioned    public class Program       public static void Main string   args                string str    abcefgh           var astr   new Permutation   GenerateFor str           Console WriteLine astr Length           foreach var a in astr                        Console WriteLine a                       a ForEach Console WriteLine            class Permutation       public string   GenerateFor string s                   if s Length    1                         return new    s                       else if s Length    2                         return new    s 1  ToString   s 0  ToString   s 0  ToString   s 1  ToString                         var comb   new List lt string gt              foreach var c in s                         string cStr   c ToString                 var sToProcess   s Replace cStr                  if   string IsNullOrEmpty sToProcess   amp  amp  sToProcess Length gt 0                                var conCatStr   GenerateFor sToProcess                      foreach var a in conCatStr                                        comb Add c ToString   a                                                       return comb ToArray

User · Answer

Here I have found the solution  It was written in Java  but I have converted it to C   I hope it will help you   Here s the code in C   static void Main string   args        string str    quot ABC quot       char   charArry   str ToCharArray        Permute charArry  0  2       Console ReadKey       static void Permute char   arry  int i  int n        int j      if  i  n          Console WriteLine arry       else               for j   i  j  lt  n  j                          Swap ref arry i  ref arry j                Permute arry i 1 n               Swap ref arry i   ref arry j      backtrack                    static void Swap ref char a  ref char b        char tmp      tmp   a      a b      b   tmp

User · Answer

lt summary gt          Print All the Permutations           lt  summary gt           lt param name  inputStr  gt input string lt  param gt           lt param name  strLength  gt length of the string lt  param gt           lt param name  outputStr  gt output string lt  param gt      private void PrintAllPermutations string inputStr  int strLength string outputStr  int NumberOfChars                  Means you have completed a permutation          if  outputStr Length    NumberOfChars                        Console WriteLine outputStr                               return                       For loop is used to print permutations starting with every character  first print all the permutations starting with a then b  etc          for int i 0   i lt  strLength  i                             Recursive call   for a string abc   a   perm bc   b  perm ac  etc              PrintAllPermutations inputStr Remove i  1   strLength - 1  outputStr   inputStr Substring i  1   4

User · Answer

It s just two lines of code if LINQ is allowed to use  Please see my answer here   EDIT  Here is my generic function which can return all the permutations  not combinations  from a list of T   static IEnumerable lt IEnumerable lt T gt  gt      GetPermutations lt T gt  IEnumerable lt T gt  list  int length        if  length    1  return list Select t   gt  new T     t          return GetPermutations list  length - 1           SelectMany t   gt  list Where e   gt   t Contains e                 t1  t2    gt  t1 Concat new T     t2          Example   IEnumerable lt IEnumerable lt int gt  gt  result       GetPermutations Enumerable Range 1  3   3     Output - a list of integer-lists    1 2 3   1 3 2   2 1 3   2 3 1   3 1 2   3 2 1    As this function uses LINQ so it requires  net 3 5 or higher

User · Answer

class Program       public static void Main string   args                Permutation  abc               static void Permutation string rest  string prefix                     if  string IsNullOrEmpty rest   Console WriteLine prefix               Each letter has a chance to be permutated         for  int i   0  i  lt  rest Length  i                                          Permutation rest Remove i  1   prefix   rest i

User · Answer

The below is my implementation of permutation   Don t mind the variable names  as i was doing it for fun      class combinations       static void Main                  string choice    y           do                       try                               Console WriteLine  Enter word                      string abc   Console ReadLine   ToString                    Console WriteLine  Combinatins for word                      List lt string gt  final   comb abc                   int count   1                  foreach  string s in final                                        Console WriteLine   0  -- gt   1    count    s                                     Console WriteLine  Do you wish to continue y n                      choice   Console ReadLine   ToString                              catch  Exception exc                                Console WriteLine exc                           while  choice     y     choice     Y               static string swap string test                return swap 0  1  test              static List lt string gt  comb string test                List lt string gt  sec   new List lt string gt             List lt string gt  first   new List lt string gt             if  test Length    1  first Add test           else if  test Length    2    first Add test   first Add swap test              else if  test Length  gt  2                        sec   generateWords test               foreach  string s in sec                                string init   s Substring 0  1                   string restOfbody   s Substring 1  s Length - 1                    List lt string gt  third   comb restOfbody                   foreach  string s1 in third                                        if   first Contains init   s1   first Add init   s1                                                        return first             static string ShiftBack string abc                char   arr   abc ToCharArray            char temp   arr 0           string wrd   string Empty          for  int i   1  i  lt  arr Length  i                          wrd    arr i                      wrd    temp          return wrd             static List lt string gt  generateWords string test                List lt string gt  final   new List lt string gt             if  test Length    1              final Add test           else                       final Add test               string holdString   test              while  final Count  lt  test Length                                holdString   ShiftBack holdString                   final Add holdString                                    return final             static string swap int currentPosition  int targetPosition  string temp                char   arr   temp ToCharArray            char t   arr currentPosition           arr currentPosition    arr targetPosition           arr targetPosition    t          string word   string Empty          for  int i   0  i  lt  arr Length  i                          word    arr i                       return word

User · Answer

Here s my solution in JavaScript  NodeJS   The main idea is that we take one element at a time   remove it  from the string  vary the rest of the characters  and insert the element at the front   function perms  string      if  string length    0        return           if  string length    1        return  string         var list         for var i   0  i  lt  string length  i          var invariant   string i       var rest   string substr 0  i    string substr i   1       var newPerms   perms rest       for  var j   0  j  lt  newPerms length  j            list push invariant   newPerms j                return list     module exports   perms    And here are the tests   require  should    var permutations   require     src perms     describe  permutations   function        it  should permute      function          permutations     should eql              it  should permute  1    function          permutations  1   should eql   1             it  should permute  12    function          permutations  12   should eql   12    21             it  should permute  123    function          var expected     123    132    321    213    231    312        var actual   permutations  123        expected forEach function  e          actual should containEql e                  it  should permute  1234    function             Wolfram Alpha FTW      var expected     1234    1243    1324    1342    1423    1432    2134    2143    2314    2341    2413    2431    3124    3142    3214    3241    3412    3421    4123    4132        var actual   permutations  1234        expected forEach function  e          actual should containEql e

User · Answer

Here s a high level example I wrote which illustrates the human language explanation Peter gave       public List lt string gt  FindPermutations string input                if  input Length    1              return new List lt string gt    input            var perms   new List lt string gt             foreach  var c in input                        var others   input Remove input IndexOf c   1               perms AddRange FindPermutations others  Select perm   gt  c   perm                      return perms

User · Answer

class Permutation       public static List lt string gt  Permutate string seed  List lt string gt  lstsList                loopCounter   0             string s   w 0 2            var lstStrs   PermuateRecursive seed            Trace WriteLine  Loop counter      loopCounter           return lstStrs                Recursive function to find permutation     private static List lt string gt  PermuateRecursive string seed                List lt string gt  lstStrs   new List lt string gt              if  seed Length  gt  2                        for  int i   0  i  lt  seed Length  i                                  str   Swap seed  0  i                    PermuateRecursive str Substring 1  str Length - 1   ForEach                      s   gt                                                lstStrs Add str 0    s                           loopCounter                                                                              else                       lstStrs Add seed               lstStrs Add Swap seed  0  1                      return lstStrs              Loop counter variable to count total number of loop execution in various functions     private static int loopCounter   0         Non recursive  version of permuation function     public static List lt string gt  Permutate string seed                loopCounter   0          List lt string gt  strList   new List lt string gt             strList Add seed           for  int i   0  i  lt  seed Length  i                          int count   strList Count              for  int j   i   1  j  lt  seed Length  j                                  for  int k   0  k  lt  count  k                                          strList Add Swap strList k   i  j                        loopCounter                                                      Trace WriteLine  Loop counter      loopCounter           return strList             private static string Swap string seed  int p  int p2                Char   chars   seed ToCharArray            char temp   chars p2           chars p2    chars p           chars p    temp          return new string chars

User · Answer

Here is an easy to understand permutaion function for both string and integer as input  With this you can even set your output length which in normal case it is equal to input length   String      static ICollection lt string gt  result       public static ICollection lt string gt  GetAllPermutations string str  int outputLength                result   new List lt string gt             MakePermutations str ToCharArray    string Empty  outputLength           return result             private static void MakePermutations         char   possibleArray   all chars extracted from input        string permutation         int outputLength  the length of output                 if  permutation Length  lt  outputLength                          for  int i   0  i  lt  possibleArray Length  i                                    var tempList   possibleArray ToList lt char gt                      tempList RemoveAt i                    MakePermutations tempList ToArray                           string Concat permutation  possibleArray i    outputLength                                      else if   result Contains permutation               result Add permutation           and for Integer just change the caller method and MakePermutations   remains untouched       public static ICollection lt int gt  GetAllPermutations int input  int outputLength                result   new List lt string gt             MakePermutations input ToString   ToCharArray    string Empty  outputLength           return result Select m   gt  int Parse m   ToList lt int gt             example 1  GetAllPermutations  abc  3    abc   acb   bac   bca   cab   cba    example 2  GetAllPermutations  abcd  2    ab   ac   ad   ba   bc   bd   ca   cb   cd   da   db   dc   example 3  GetAllPermutations 486 2   48 46 84 86 64 68

User · Answer

I liked FBryant87 approach since it s simple  Unfortunately  it does like many other  solutions  not offer all permutations or of e g  an integer if it contains the same digit more than once  Take 656123 as an example  The line   var tail   chars Except new List lt char gt    c      using Except will cause all occurrences to be removed  i e  when c   6  two digits are removed and we are left with e g  5123  Since none of the solutions I tried solved this  I decided to try and solve it myself by FBryant87 s code as base  This is what I came up with   private static List lt string gt  FindPermutations string set                var output   new List lt string gt             if  set Length    1                        output Add set                     else                       foreach  var c in set                                   Remove one occurrence of the char  not all                  var tail   set Remove set IndexOf c   1                   foreach  var tailPerms in FindPermutations tail                                         output Add c   tailPerms                                                     return output          I simply just remove the first found occurrence using  Remove and  IndexOf  Seems to work as intended for my usage at least  I m sure it could be made cleverer   One thing to note though  The resulting list may contain duplicates  so make sure you either make the method return e g  a HashSet instead or remove the duplicates after the return using any method you like

User · Answer

Here s a purely functional F  implementation     let factorial i       let rec fact n x           match n with           0 -  1           1 -  x             -  fact  n-1   x n      fact i 1  let swap  arr  a array  i j      for k in 0   arr Length-1  -  if k   i then arr  j  elif k   j then arr  i  else arr  k      let rec permutation  k int j int   r  a array        if j    r Length   1  then r     else permutation  k j 1  j 1   swap r  j-1   k j    let permutations  source  a array    seq   for k   0 to  source    Array length    factorial  - 1 do yield permutation  k 2  source     Performance can be greatly improved by changing swap to take advantage of the mutable nature of CLR arrays  but this implementation is thread safe with regards to the source array and that may be desirable in some contexts  Also  for arrays with more than 16 elements int must be replaced with types with greater arbitrary precision as factorial 17 results in an int32 overflow

[c#] Listing all permutations of a string/integer

Examples related to c#

Examples related to algorithm

Examples related to permutation