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

Voici un bon article qui présente trois algorithmes permettant de trouver toutes les permutations, dont un qui permet de trouver la permutation suivante.

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

C++ et Python ont intégré Permutation suivante et itertools.permutations respectivement.

Answer 2

Voici une mise en œuvre purement fonctionnelle en F# :

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 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 ayant une précision supérieure/arbitraire, car la factorielle 17 entraîne un dépassement de int32.

Answer 3

Voici une fonction de permutation facile à comprendre pour une chaîne de caractères et un nombre entier en entrée. Avec cette vous pouvez même définir votre longueur de sortie (qui dans le cas normal est égal à la longueur de l'entrée)

Chaîne de caractères

    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 Entier il suffit de changer la méthode de l'appelant et MakePermutations() reste intacte :

    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

Answer 4

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

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

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

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

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

Answer 5

Base/révision sur Pengyang réponse

Et inspiré de permutations-in-javascript

La version c# FunctionalPermutations devrait être ceci

static IEnumerable<IEnumerable<T>> FunctionalPermutations<T>(IEnumerable<T> elements, int length)
    {
        if (length < 2) return elements.Select(t => new T[] { t });
        /* Pengyang answser..
          return _recur_(list, length - 1).SelectMany(t => list.Where(e => !t.Contains(e)),(t1, t2) => t1.Concat(new T[] { t2 }));
        */
        return elements.SelectMany((element_i, i) => 
          FunctionalPermutations(elements.Take(i).Concat(elements.Skip(i + 1)), length - 1)
            .Select(sub_ei => new[] { element_i }.Concat(sub_ei)));
    }