Liste de toutes les permutations d'une chaîne de caractères/un nombre entier

Question

Une tâche courante dans les entretiens de programmation (ce n'est pas mon expérience des entretiens) consiste à prendre une chaîne de caractères ou un nombre entier et à énumérer toutes les permutations possibles.

Existe-t-il un exemple de la manière de procéder et de la logique qui sous-tend 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.

Answer 1

Tout d'abord, ça sent comme récursion bien sûr !

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

1. La première étape
2. Toutes les autres étapes (toutes avec la même logique)

Sur le langage humain :

En bref :

1. La permutation d'un é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 rendre.
perm(a) -> a

Si l'ensemble a deux caractères : pour chaque élément de l'ensemble : retourner l'élément avec la permutation des éléments le reste des éléments, comme ceci :

perm(ab) ->

a + perm(b) -> ab

b + perm(a) -> ba

En outre : pour chaque caractère de l'ensemble : retour d'un caractère, concaténé avec une permutation 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 pseudo-code 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 puisque c'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 quand même, pour que le post ne soit pas dépendant 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, devrait se déverser :

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

Answer 2

Il ne s'agit que de deux lignes de code si l'utilisation de LINQ est autorisée. Veuillez voir ma réponse ici .

EDIT

Voici ma fonction générique qui peut retourner toutes les permutations (pas les combinaisons) 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 plus.

Answer 3

J'ai trouvé la solution ici. Elle était écrite en Java, mais je l'ai convertie en C#. J'espère qu'elle 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;
}

Answer 4

Récursion n'est pas nécessaire, ici est une bonne information 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 O(N) temps et espace complexité 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;
    }
}

Answer 5

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]);
        }
    }
}