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

Version légèrement modifiée en C# qui permet d'obtenir les permutations nécessaires dans un tableau de n'importe quel 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<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;
    }
}

Answer 2

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 de permutation pour permuter les caractères.
Ceci doit être appelé permute(string, 0) ;

Answer 3

J'ai aimé FBryant87 approche car elle est simple. Malheureusement, comme beaucoup d'autres "solutions", elle n'offre pas toutes les permutations ou, par exemple, d'un nombre 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});

L'utilisation de Except entraîne la suppression de toutes les occurrences, c'est-à-dire que lorsque c = 6, deux chiffres sont supprimés et il nous reste par exemple 5123. Comme aucune des solutions que j'ai essayées n'a résolu ce problème, j'ai décidé d'essayer de le résoudre moi-même en FBryant87 comme base. Voici ce que j'ai trouvé :

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. Cela semble fonctionner comme prévu, du moins pour mon utilisation. Je suis sûr que cela pourrait être plus intelligent.

Une chose à noter cependant : La liste résultante peut contenir des doublons. Veillez donc à ce que la méthode renvoie un HashSet, par exemple, ou supprimez les doublons après le retour en utilisant la méthode de votre choix.

Answer 4

Tout d'abord, les ensembles ont des permutations, pas les chaînes ou les entiers, donc je vais supposer que vous voulez dire "l'ensemble des caractères dans une chaîne".

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

Le pseudocode suivant (tiré 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 tableaux 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

Answer 5

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

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