Liste de toutes les permutations d'une chaîne / d'un entier

Une tâche courante dans la programmation des interviews (pas de mon expérience des interviews cependant) est de prendre une chaîne ou un entier et de lister toutes les permutations possibles.

Y a-t-il un exemple de la façon dont cela est fait et de la logique derrière la résolution d'un tel problème?

J'ai vu quelques extraits de code mais ils n'étaient pas bien commentés / expliqués et donc difficiles à suivre.

Tout d'abord: ça sent la récursion bien sûr!

Puisque vous vouliez aussi connaître le principe, j'ai fait de mon mieux pour l'expliquer en langage humain. Je pense que la récursivité est très facile la plupart du temps. Vous n'avez qu'à saisir deux étapes:

1. Le premier pas
2. Toutes les autres étapes (toutes avec la même logique)

En langage humain :

En bref:
1. La permutation de 1 élément est un élément.
2. La permutation d'un ensemble d'éléments est une liste de chacun des éléments, concaténée avec chaque permutation des autres éléments.

Exemple:

Si l'ensemble n'a qu'un seul élément -> le
renvoyer.
perm (a) -> a

Si l'ensemble a deux caractères: pour chaque élément qu'il contient: renvoie l'élément, avec la permutation du reste des éléments ajoutée, comme ceci:

perm (ab) ->

a + perm (b) -> ab

b + perm (a) -> ba

De plus: pour chaque caractère de l'ensemble: retourne un caractère, concaténé avec une lecture> du reste de l'ensemble

perm (abc) ->

a + perm (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> cabine , cba

perm (abc ... z) ->

a + perm (...), b + perm (....)
....

J'ai trouvé le pseudocode sur http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ :

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

C #

OK, et quelque chose de plus élaboré (et puisqu'il est étiqueté c #), de http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Plutôt long, mais j'ai décidé de le copier de toute façon, le message ne dépend donc pas de l'original.

La fonction prend une chaîne de caractères et écrit toutes les permutations possibles de cette chaîne exacte, donc par exemple, si "ABC" a été fourni, doit se répandre:

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 <= 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 = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

Ce n'est que deux lignes de code si LINQ est autorisé à utiliser. Veuillez voir ma réponse ici .

ÉDITER

Voici ma fonction générique qui peut renvoyer toutes les permutations (pas les combinaisons) à partir d'une liste de T:

static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

Exemple:

IEnumerable<IEnumerable<int>> result =
    GetPermutations(Enumerable.Range(1, 3), 3);

Sortie - une liste de listes d'entiers:

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

Comme cette fonction utilise LINQ, elle nécessite .net 3.5 ou supérieur.

Ici, j'ai trouvé la solution. Il a été écrit en Java, mais je l'ai converti en C #. J'espère que cela vous aidera.

Voici le code en C #:

static void Main(string[] args)
{
    string str = "ABC";
    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 <=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;
}

La récursivité n'est pas nécessaire, voici de bonnes informations sur cette 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();

J'utilise cet algorithme depuis des années, il a une complexité temporelle et spatiale O (N) pour calculer chaque permutation .

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[]) array.Clone();

        for (int i = 0; i < clone.Length - 1; i++)
        {
            Swap(ref clone[i], ref clone[i + sequence[i]]);
        }

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(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 < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}

void permute (char *str, int ptr) {
  int i, len;
  len = strlen(str);
  if (ptr == len) {
    printf ("%s\n", str);
    return;
  }

  for (i = ptr ; i < len ; i++) {
    swap (&str[ptr], &str[i]);
    permute (str, ptr + 1);
    swap (&str[ptr], &str[i]);
  }
}

Vous pouvez écrire votre fonction d'échange pour permuter les caractères.
Ceci doit être appelé comme permute (string, 0);

Tout d'abord, les ensembles ont des permutations, pas des chaînes ou des entiers, donc je suppose simplement que vous voulez dire «l'ensemble des caractères d'une chaîne».

Notez qu'un ensemble de taille n a n! n-permutations.

Le pseudocode suivant (de Wikipedia), appelé avec k = 1 ... n! donnera toutes les 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;
}

Voici le code Python équivalent (pour les index de tableau basés sur 0):

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

Version légèrement modifiée en C # qui donne les permutations nécessaires dans un tableau de type ANY.

    // 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<T[]> Permutations<T>(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 < 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<T>(T[] values, int pos1, int pos2)
{
    if (pos1 != pos2)
    {
        T tmp = values[pos1];
        values[pos1] = values[pos2];
        values[pos2] = tmp;
    }
}

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 < rest.Length; i++)
        {                
            Permutation(rest.Remove(i, 1), prefix + rest[i]);
        }
    }
}

J'ai aimé l' approche FBryant87 car elle est simple. Malheureusement, comme beaucoup d'autres «solutions», elle n'offre pas toutes les permutations ou par exemple un entier s'il contient le même chiffre plus d'une fois. Prenons l'exemple de 656123. La ligne:

var tail = chars.Except(new List<char>(){c});

Sauf à l' aide entraînera toutes les occurrences à supprimer, à savoir quand c = 6, deux chiffres sont retirés et il nous reste par exemple 5123. Comme aucune des solutions que j'ai essayé résolu ce problème, j'ai décidé d'essayer de le résoudre par moi - même FBryant87 d » code comme base. Voici ce que j'ai proposé:

private static List<string> FindPermutations(string set)
    {
        var output = new List<string>();
        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;
    }

Je supprime simplement la première occurrence trouvée en utilisant .Remove et .IndexOf. Semble fonctionner comme prévu pour mon utilisation au moins. Je suis sûr que cela pourrait être rendu plus intelligent.

Une chose à noter cependant: la liste résultante peut contenir des doublons, alors assurez-vous que la méthode retourne par exemple un HashSet à la place ou supprimez les doublons après le retour en utilisant la méthode de votre choix.

Voici un bon article couvrant trois algorithmes pour trouver toutes les permutations, dont un pour trouver la prochaine permutation.

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

C ++ et Python ont respectivement des fonctions intégrées next_permutation et itertools.permutations .

Voici une implémentation F # purement fonctionnelle:

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 }

Les performances peuvent être grandement améliorées en modifiant le swap pour tirer parti de la nature mutable des tableaux CLR, mais cette implémentation est thread-safe en ce qui concerne le tableau source et cela peut être souhaitable dans certains contextes. De plus, pour les tableaux de plus de 16 éléments, int doit être remplacé par des types avec une précision supérieure / arbitraire car factorielle 17 entraîne un débordement int32.

Voici une solution simple en c # utilisant la récursivité,

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 < n; i++)
        {
            WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
        }
    }
}

Voici une fonction de permutation facile à comprendre pour les chaînes et les entiers en entrée. Avec cela, vous pouvez même définir votre longueur de sortie (qui, dans le cas normal, est égale à la longueur d'entrée)

Chaîne

    static ICollection<string> result;

    public static ICollection<string> GetAllPermutations(string str, int outputLength)
    {
        result = new List<string>();
        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 < outputLength)
         {
             for (int i = 0; i < possibleArray.Length; i++)
             {
                 var tempList = possibleArray.ToList<char>();
                 tempList.RemoveAt(i);
                 MakePermutations(tempList.ToArray(), 
                      string.Concat(permutation, possibleArray[i]), outputLength);
             }
         }
         else if (!result.Contains(permutation))
            result.Add(permutation);
    }

et pour Integer, changez simplement la méthode de l'appelant et MakePermutations () reste inchangé:

    public static ICollection<int> GetAllPermutations(int input, int outputLength)
    {
        result = new List<string>();
        MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
        return result.Select(m => int.Parse(m)).ToList<int>();
    }

exemple 1: GetAllPermutations ("abc", 3); "abc" "acb" "bac" "bca" "cab" "cba"

exemple 2: GetAllPermutations ("abcd", 2); "ab" "ac" "ad" "ba" "bc" "bd" "ca" "cb" "cd" "da" "db" "dc"

exemple 3: GetAllPermutations (486,2); 48 46 84 86 64 68

Voici la fonction qui affichera toutes les permutations. Cette fonction implémente la logique expliquée par 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 <= 1)
            Console.WriteLine(beginningString + endingString);
        else
            for (int i = 0; i < 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();

    }

Voici ma mise en œuvre de la permutation. Ne vous inquiétez pas des noms de variables, car je le faisais pour le plaisir :)

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<string> final = comb(abc);
                int count = 1;
                foreach (string s in final)
                {
                    Console.WriteLine("{0} --> {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<string> comb(string test)
    {
        List<string> sec = new List<string>();
        List<string> first = new List<string>();
        if (test.Length == 1) first.Add(test);
        else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
        else if (test.Length > 2)
        {
            sec = generateWords(test);
            foreach (string s in sec)
            {
                string init = s.Substring(0, 1);
                string restOfbody = s.Substring(1, s.Length - 1);

                List<string> 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 < arr.Length; i++)
        {
            wrd += arr[i];
        }

        wrd += temp;
        return wrd;
    }

    static List<string> generateWords(string test)
    {
        List<string> final = new List<string>();
        if (test.Length == 1)
            final.Add(test);
        else
        {
            final.Add(test);
            string holdString = test;
            while (final.Count < 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 < arr.Length; i++)
        {
            word += arr[i];

        }

        return word;

    }
}

Voici un exemple de haut niveau que j'ai écrit et qui illustre l' explication du langage humain que Peter a donnée:

    public List<string> FindPermutations(string input)
    {
        if (input.Length == 1)
            return new List<string> { input };
        var perms = new List<string>();
        foreach (var c in input)
        {
            var others = input.Remove(input.IndexOf(c), 1);
            perms.AddRange(FindPermutations(others).Select(perm => c + perm));
        }
        return perms;
    }

Si les performances et la mémoire sont un problème, je suggère cette implémentation très efficace. Selon l'algorithme de Heap sur Wikipedia , il devrait être le plus rapide. J'espère qu'il répondra à vos besoins :-)!

Juste comme comparaison de cela avec une implémentation Linq pour 10! (code inclus):

• Ceci: 36288000 articles en 235 millisecs

• Linq: 36288000 articles en 50051 millisecs

  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Linq;
  using System.Runtime.CompilerServices;
  using System.Text;
  
  namespace WpfPermutations
  {
      /// <summary>
      /// 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
      /// </summary>
      public static class Permutations
      {
          /// <summary>
          /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
          /// </summary>
          /// <param name="items">Items to permute in each possible ways</param>
          /// <param name="funcExecuteAndTellIfShouldStop"></param>
          /// <returns>Return true if cancelled</returns> 
          public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
          {
              int countOfItem = items.Length;
  
              if (countOfItem <= 1)
              {
                  return funcExecuteAndTellIfShouldStop(items);
              }
  
              var indexes = new int[countOfItem];
              for (int i = 0; i < countOfItem; i++)
              {
                  indexes[i] = 0;
              }
  
              if (funcExecuteAndTellIfShouldStop(items))
              {
                  return true;
              }
  
              for (int i = 1; i < countOfItem;)
              {
                  if (indexes[i] < i)
                  { // On the web there is an implementation with a multiplication which should be less efficient.
                      if ((i & 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;
          }
  
          /// <summary>
          /// This function is to show a linq way but is far less efficient
          /// </summary>
          /// <typeparam name="T"></typeparam>
          /// <param name="list"></param>
          /// <param name="length"></param>
          /// <returns></returns>
          static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
          {
              if (length == 1) return list.Select(t => new T[] { t });
  
              return GetPermutations(list, length - 1)
                  .SelectMany(t => list.Where(e => !t.Contains(e)),
                      (t1, t2) => t1.Concat(new T[] { t2 }));
          }
  
          /// <summary>
          /// Swap 2 elements of same type
          /// </summary>
          /// <typeparam name="T"></typeparam>
          /// <param name="a"></param>
          /// <param name="b"></param>
          [MethodImpl(MethodImplOptions.AggressiveInlining)]
          static void Swap<T>(ref T a, ref T b)
          {
              T temp = a;
              a = b;
              b = temp;
          }
  
          /// <summary>
          /// Func to show how to call. It does a little test for an array of 4 items.
          /// </summary>
          public static void Test()
          {
              ForAllPermutation("123".ToCharArray(), (vals) =>
              {
                  Debug.Print(String.Join("", vals));
                  return false;
              });
  
              int[] values = new int[] { 0, 1, 2, 4 };
  
              Debug.Print("Non Linq");
              ForAllPermutation(values, (vals) =>
              {
                  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 < values.Length; n++)
              {
                  values[n] = n;
              }
  
              Stopwatch stopWatch = new Stopwatch();
              stopWatch.Reset();
              stopWatch.Start();
  
              ForAllPermutation(values, (vals) =>
              {
                  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");
  
          }
      }
  }

Voici ma solution en JavaScript (NodeJS). L'idée principale est de prendre un élément à la fois, de le «supprimer» de la chaîne, de faire varier le reste des caractères et d'insérer l'élément au début.

function perms (string) {
  if (string.length == 0) {
    return [];
  }
  if (string.length == 1) {
    return [string];
  }
  var list = [];
  for(var i = 0; i < 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 < newPerms.length; j++) {
      list.push(invariant + newPerms[j]);
    }
  }
  return list;
}

module.exports = perms;

Et voici les 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);
    })
  })
})

Voici la solution la plus simple à laquelle je puisse penser:

let rec distribute e = function
  | [] -> [[e]]
  | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]

let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs

La distributefonction prend un nouvel élément eet une nliste d'éléments et renvoie une liste de n+1listes dont chacune a été einsérée à un endroit différent. Par exemple, insérer 10à chacun des quatre endroits possibles dans la liste [1;2;3]:

> 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]]

La permutefonction se replie sur chaque élément à son tour en répartissant les permutations accumulées jusqu'à présent, aboutissant à toutes les permutations. Par exemple, les 6 permutations de la liste [1;2;3]:

> 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]]

Modification de l' foldune scanafin de maintenir les accumulateurs intermédiaires éclaire sur la façon dont les permutations sont générés un élément à la fois:

> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
  seq
    [[[]]; [[1]]; [[2; 1]; [1; 2]];
     [[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]

Répertorie les permutations d'une chaîne. Évite la duplication lorsque les caractères sont répétés:

using System;
using System.Collections;

class Permutation{
  static IEnumerable Permutations(string word){
    if (word == null || word.Length <= 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 <= indexOfFirstChar; index++ )
        yield return subPermute.Insert (index, new string (firstChar, 1));
    }
  }

  static void Main(){
    foreach( var permutation in Permutations ("aab") )
      Console.WriteLine (permutation);
  }
}

En s'appuyant sur la solution de @ Peter, voici une version qui déclare une Permutations()méthode d'extension simple de style LINQ qui fonctionne sur tout IEnumerable<T>.

Utilisation (sur l'exemple de caractères de chaîne):

foreach (var permutation in "abc".Permutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Les sorties:

a, b, c
a, c, b
b, a, c
b, c, a
c, b, a
c, a, b

Ou sur tout autre type de collection:

foreach (var permutation in (new[] { "Apples", "Oranges", "Pears"}).Permutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Les sorties:

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<T[]> Permutations<T>(this IEnumerable<T> source)
    {
        var sourceArray = source.ToArray();
        var results = new List<T[]>();
        Permute(sourceArray, 0, sourceArray.Length - 1, results);
        return results;
    }

    private static void Swap<T>(ref T a, ref T b)
    {
        T tmp = a;
        a = b;
        b = tmp;
    }

    private static void Permute<T>(T[] elements, int recursionDepth, int maxDepth, ICollection<T[]> results)
    {
        if (recursionDepth == maxDepth)
        {
            results.Add(elements.ToArray());
            return;
        }

        for (var i = recursionDepth; i <= maxDepth; i++)
        {
            Swap(ref elements[recursionDepth], ref elements[i]);
            Permute(elements, recursionDepth + 1, maxDepth, results);
            Swap(ref elements[recursionDepth], ref elements[i]);
        }
    }
}

Voici la fonction qui imprimera toutes les permutations de manière récursive.

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 < 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 >= 0)
        {
            input.Remove(index, 1);
            return true;
        }
        return false;
    }

class Permutation
{
    public static List<string> Permutate(string seed, List<string> 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<string> PermuateRecursive(string seed)
    {
        List<string> lstStrs = new List<string>();

        if (seed.Length > 2)
        {
            for (int i = 0; i < seed.Length; i++)
            {
                str = Swap(seed, 0, i);

                PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
                    s =>
                    {
                        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<string> Permutate(string seed)
    {
        loopCounter = 0;
        List<string> strList = new List<string>();
        strList.Add(seed);
        for (int i = 0; i < seed.Length; i++)
        {
            int count = strList.Count;
            for (int j = i + 1; j < seed.Length; j++)
            {
                for (int k = 0; k < 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);
    }
}

Voici une réponse C # qui est un peu simplifiée.

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 <= 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;
}

Production:

1 2 3
1 3 2

2 1 3
2 3 1

3 2 1
3 1 2

C'est ma solution qu'il m'est facile de comprendre

class ClassicPermutationProblem
{
    ClassicPermutationProblem() { }

    private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
    {
         foreach (T element in list)
         {
             List<T> 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<List<int>> GetPermutations(List<int> list)
    {
        List<List<int>> results = new List<List<int>>();
        PopulatePosition(results, list, new List<int>(), 1);
        return results;
     }
}

static void Main(string[] args)
{
    List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}

Voici une autre implémentation de l'algo mentionné.

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<string>();

        foreach(var c in s)
        {

            string cStr = c.ToString();

            var sToProcess = s.Replace(cStr,"");
            if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
            {
                var conCatStr = GenerateFor(sToProcess);



                foreach(var a in conCatStr)
                {
                    comb.Add(c.ToString()+a);
                }


            }
        }
        return comb.ToArray();

    }
}

    //Generic C# Method
            private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
            {
                var perms = new List<T[]>();

                var l = input.Length - 1;

                if (l == startIndex)
                    perms.Add(input);
                else
                {

                    for (int i = startIndex; i <= 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);

    /// <summary>
    /// Print All the Permutations.
    /// </summary>
    /// <param name="inputStr">input string</param>
    /// <param name="strLength">length of the string</param>
    /// <param name="outputStr">output string</param>
    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< 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);
        }
    }