Auflistung aller Permutationen einer Zeichenfolge / Ganzzahl

159

Eine häufige Aufgabe beim Programmieren von Interviews (allerdings nicht aus meiner Erfahrung mit Interviews) besteht darin, eine Zeichenfolge oder eine Ganzzahl zu nehmen und jede mögliche Permutation aufzulisten.

Gibt es ein Beispiel dafür und die Logik zur Lösung eines solchen Problems?

Ich habe ein paar Code-Schnipsel gesehen, aber sie waren nicht gut kommentiert / erklärt und daher schwer zu folgen.

GurdeepS
quelle
1
Hier ist eine Frage zu Permutationen mit einigen gut erklärenden Antworten, einschließlich eines Diagramms , jedoch nicht in C #.
Benutzer unbekannt

Antworten:

152

Zuallererst: Es riecht natürlich nach Rekursion !

Da Sie auch das Prinzip kennenlernen wollten, habe ich mein Bestes getan, um es in der menschlichen Sprache zu erklären. Ich denke, Rekursion ist meistens sehr einfach. Sie müssen nur zwei Schritte erfassen:

  1. Der erste Schritt
  2. Alle anderen Schritte (alle mit der gleichen Logik)

In der menschlichen Sprache :

Kurz gesagt:
1. Die Permutation von 1 Element ist ein Element.
2. Die Permutation eines Satzes von Elementen ist eine Liste aller Elemente, die mit jeder Permutation der anderen Elemente verknüpft ist.

Beispiel:

Wenn die Menge nur ein Element hat ->
geben Sie es zurück.
Dauerwelle (a) -> a

Wenn die Menge zwei Zeichen enthält: für jedes Element: Geben Sie das Element zurück, wobei die Permutation der übrigen Elemente wie folgt hinzugefügt wird:

perm (ab) ->

a + perm (b) -> ab

b + perm (a) -> ba

Weiter: Für jedes Zeichen im Satz: Geben Sie ein Zeichen zurück, das mit einer Perumation des Restes des Satzes verknüpft ist

perm (abc) ->

a + perm (bc) -> abc , acb

b + perm (ac) -> bac , bca

c + perm (ab) -> cab , cba

perm (abc ... z) ->

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

Ich habe den Pseudocode unter http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/ gefunden :

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, und etwas ausführlicheres (und da es mit c # gekennzeichnet ist) von http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html : Ziemlich lang, aber ich habe beschlossen, es zu kopieren sowieso ist der Beitrag also nicht vom Original abhängig.

Die Funktion verwendet eine Zeichenfolge und schreibt jede mögliche Permutation dieser exakten Zeichenfolge auf. Wenn beispielsweise "ABC" angegeben wurde, sollte Folgendes ausgegeben werden:

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);
    }
}
Peter
quelle
21
Für ein bisschen mehr Klarheit würde ich k "recursionDepth" und m "maxDepth" nennen.
Nerf Herder
3
Der 2. Swap ( Swap(ref list[k], ref list[i]);) ist nicht erforderlich.
Dance2die
1
Vielen Dank für diese Lösung. Ich habe diese Geige ( dotnetfiddle.net/oTzihw ) daraus erstellt (mit der richtigen Benennung anstelle von k und m). Soweit ich das Algo verstehe, ist der zweite Swap erforderlich (zum Zurückverfolgen), da Sie das ursprüngliche Array direkt bearbeiten.
Andrew
3
Ein kleiner Punkt: Es sieht so aus, als ob die Swap-Methode besser mit einer temporären Puffervariablen implementiert werden kann und keine XORs verwendet ( dotnetperls.com/swap )
Sergioet
7
Mit C # 7 Tupeln können Sie den Tausch viel eleganter gestalten:(a[x], a[y]) = (a[y], a[x]);
Darren
81

Es sind nur zwei Codezeilen, wenn LINQ verwendet werden darf. Bitte sehen Sie meine Antwort hier .

BEARBEITEN

Hier ist meine generische Funktion, die alle Permutationen (keine Kombinationen) aus einer Liste von T zurückgeben kann:

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

Beispiel:

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

Ausgabe - eine Liste von Ganzzahllisten:

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

Da diese Funktion LINQ verwendet, ist .net 3.5 oder höher erforderlich.

Pengyang
quelle
3
Kombinationen und Permutationen sind verschiedene Dinge. Es ist ähnlich, aber Ihre Antwort dort scheint ein anderes Problem zu beantworten als alle Permutationen einer Reihe von Elementen.
Shawn Kovac
@ShawnKovac, danke für den Hinweis! Ich habe meinen Code von Kombination auf Permutation aktualisiert.
Pengyang
1
@Pengyang Ich habe mir Ihre andere Antwort angesehen und ich werde sagen, dass mir das sehr geholfen hat, aber ich habe eine andere Situation, die ich nicht kenne, wenn Sie auf die richtige Art der Lösung hingewiesen haben. Ich wollte alle Permutationen eines Wortes wie 'HALLOWEEN' finden, aber ich wollte auch sowohl 'L' als auch beide 'E' in die Ergebnismenge aufnehmen. In meinen Iterationen durchlaufe ich Ihre Methode und gebe mit jeder Iteration eine längere Länge (Länge ++). Ich würde erwarten, dass ich bei voller Länge des Wortes HALLOWEEN (9 Zeichen) Ergebnisse mit einer Länge von 9 Zeichen erhalte ... aber das ist nicht der Fall: Ich bekomme nur 7 (1 L und 1 E sind weggelassen)
MegaMark
Ich möchte auch darauf hinweisen, dass ich KEINE Situation möchte, in der ich 9 'H' sehe, da 'H' nur einmal im Wort vorkommt.
MegaMark
4
@MegaMark Für diese Funktion müssen die Elemente eindeutig sein. Versuchen Sie dies:const string s = "HALLOWEEN"; var result = GetPermutations(Enumerable.Range(0, s.Length), s.Length).Select(t => t.Select(i => s[i]));
Pengyang
36

Hier habe ich die Lösung gefunden. Es wurde in Java geschrieben, aber ich habe es in C # konvertiert. Ich hoffe es hilft dir.

Geben Sie hier die Bildbeschreibung ein

Hier ist der Code in 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;
}
user3277651
quelle
Wird es aus einer anderen Sprache portiert? Auf jeden Fall +1 für das Bild, weil es wirklich einen Mehrwert bietet. Der Code selbst scheint jedoch ein gewisses Verbesserungspotential zu haben. Einige kleinere Teile werden nicht benötigt, aber am wichtigsten ist, dass ich dieses C ++ - Gefühl bekomme, wenn wir etwas einsenden und Dinge daran tun, anstatt In-Parameter bereitzustellen und einen zurückgegebenen Wert abzurufen. Tatsächlich habe ich Ihr Bild verwendet, um einen C # -Stil-C # -Code zu implementieren (Stil ist natürlich meine persönliche Wahrnehmung), und es hat mir sehr geholfen. Wenn ich ihn poste, werde ich ihn Ihnen definitiv stehlen (und gutschreiben) du dafür).
Konrad Viltersten
21

Eine Rekursion ist nicht erforderlich. Hier finden Sie gute Informationen zu dieser Lösung.

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

Ich habe diesen Algorithmus seit Jahren verwendet, hat es O (N) Zeit und Raum Komplexität berechnen jeweils 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;
    }
}
Najera
quelle
Funktioniert sofort!
Revobtz
1
Vielleicht verstehe ich die O (n) -Notation nicht. Bezieht sich das N nicht darauf, wie viele "innere Schleifen" erforderlich sind, damit Ihr Algorithmus funktioniert? Mir scheint, wenn Sie N Zahlen haben, scheint es O (N * N!) zu sein (weil es N! mal N Swaps machen muss). Außerdem muss eine Menge Array kopiert werden. Dieser Code ist "ordentlich", aber ich würde ihn nicht verwenden.
Eric Frazer
@ericfrazer Jede Permutation verwendet nur eine Array-Kopie und zwar O(N-1)für die Sequenz und O(N)für die Swaps O(N). Und ich benutze dies immer noch in der Produktion, aber mit einem Refactor, um nur eine Permutation zu generieren, wie: GetPermutation(i)wo 0 <= i <= N!-1. Gerne verwende ich etwas mit einer besseren Leistung als dieses. Rufen Sie also eine Referenz für etwas Besseres an, die meisten Alternativen werden O(N!)im Speicher verwendet, damit Sie dies auch überprüfen können.
Najera
11
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]);
  }
}

Sie können Ihre Swap-Funktion schreiben, um Zeichen auszutauschen.
Dies ist als permute (string, 0) zu bezeichnen;


quelle
5
Das sieht aus wie C, nicht wie C #.
Jon Schneider
9

Zuallererst haben Mengen Permutationen, keine Zeichenketten oder Ganzzahlen, also gehe ich einfach davon aus, dass Sie "die Zeichensätze in einer Zeichenkette" meinen.

Beachten Sie, dass ein Satz der Größe n n hat! n-Permutationen.

Der folgende Pseudocode (aus Wikipedia), aufgerufen mit k = 1 ... n! wird alle Permutationen geben:

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

Hier ist der entsprechende Python-Code (für 0-basierte Array-Indizes):

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
Kann Berk Güder
quelle
5
Welche Sprache ist das? Die Frage ist mit C # markiert. Ich weiß nicht was k := k / j;.
Shawn Kovac
8

Leicht modifizierte Version in C #, die die erforderlichen Permutationen in einem Array vom Typ ANY liefert.

    // 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;
    }
}
Yurik
quelle
Eine kleine Einschränkung bei dieser Implementierung: Sie funktioniert nur dann ordnungsgemäß, wenn Sie nicht versuchen, den Aufzählungswert zu speichern. Wenn Sie versuchen, so etwas zu tun, erhalten Permutations(vals).ToArray()Sie N Verweise auf dasselbe Array. Wenn Sie die Ergebnisse speichern möchten, müssen Sie manuell eine Kopie erstellen. ZBPermutations(values).Select(v => (T[])v.Clone())
Pharap
8
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]);
        }
    }
}
Meng Xue
quelle
1
Wahnsinnige Lösung. Danke dir!
Cristian E.
7

Ich mochte den FBryant87- Ansatz, da er einfach ist. Leider bietet es wie viele andere "Lösungen" nicht alle Permutationen oder zB eine ganze Zahl, wenn es dieselbe Ziffer mehr als einmal enthält. Nehmen Sie als Beispiel 656123. Die Linie:

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

mit Ausnahme werden alle Vorkommen verursachen entfernt werden, das heißt , wenn c = 6 sind zwei Stellen entfernt , und wir sind links mit zB 5123 Da keine der Lösungen , die ich dieses Problem gelöst versucht, entschied ich mich , um zu versuchen und es zu lösen mich von FBryant87 ‚s Code als Basis. Folgendes habe ich mir ausgedacht:

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

Ich entferne einfach das erste gefundene Vorkommen mit .Remove und .IndexOf. Scheint zumindest für meinen Gebrauch wie vorgesehen zu funktionieren. Ich bin sicher, es könnte klüger gemacht werden.

Beachten Sie jedoch Folgendes: Die resultierende Liste kann Duplikate enthalten. Stellen Sie daher sicher, dass Sie die Methode entweder zurückgeben, z. B. ein HashSet, oder entfernen Sie die Duplikate nach der Rückgabe mit einer beliebigen Methode.

Umarmung
quelle
Funktioniert wie eine absolute Schönheit, zuerst habe ich festgestellt, dass doppelte Zeichen +1
Jack Casey
5

Hier ist eine rein funktionale F # -Implementierung:


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 }

Die Leistung kann erheblich verbessert werden, indem der Swap geändert wird, um die veränderliche Natur von CLR-Arrays zu nutzen. Diese Implementierung ist jedoch in Bezug auf das Quellarray threadsicher und kann in einigen Kontexten wünschenswert sein. Bei Arrays mit mehr als 16 Elementen muss int durch Typen mit größerer / beliebiger Genauigkeit ersetzt werden, da Fakultät 17 zu einem int32-Überlauf führt.

em70
quelle
5

Hier ist eine einfache Lösung in c # mit Rekursion:

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)));
        }
    }
}
raghavankl
quelle
Vielen Dank für die sehr einfache und kurze Lösung! :)
Kristaps Vilerts
4

Hier ist eine leicht verständliche Permutationsfunktion für String und Integer als Eingabe. Hiermit können Sie sogar Ihre Ausgabelänge einstellen (die im Normalfall der Eingabelänge entspricht).

String

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

und für Integer ändern Sie einfach die Aufrufermethode und MakePermutations () bleibt unberührt:

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

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

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

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

Amir Chatrbahr
quelle
Ich mag Ihre Lösung, weil dies leicht zu verstehen ist, danke dafür! Ich habe mich jedoch für dieses entschieden: stackoverflow.com/questions/756055/… . Der Grund dafür ist, dass ToList, ToArray und RemoveAt alle eine zeitliche Komplexität von O (N) haben. Grundsätzlich müssen Sie also alle Elemente der Sammlung durchgehen (siehe stackoverflow.com/a/15042066/1132522 ). Gleiches gilt für das int, bei dem Sie am Ende im Grunde alle Elemente erneut durchgehen, um sie in int zu konvertieren. Ich bin damit einverstanden, dass dies für "abc" oder 486 keine großen Auswirkungen hat.
Andrew
2

Hier ist die Funktion, die alle Permutationen druckt. Diese Funktion implementiert die von Peter erklärte Logik.

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

    }
Amit Patel
quelle
2

Das Folgende ist meine Implementierung der Permutation. Kümmere dich nicht um die Variablennamen, da ich es zum Spaß gemacht habe :)

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;

    }
}
Priyank
quelle
2

Hier ist ein Beispiel auf hoher Ebene, das ich geschrieben habe und das die Erklärung der menschlichen Sprache veranschaulicht, die Peter gegeben hat:

    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;
    }
FBryant87
quelle
Diese Lösung ist tatsächlich insofern fehlerhaft, als sie fehlschlägt, wenn der Zeichenfolgensatz Wiederholungszeichen enthält. Beim Wort "Test" entfernt der Befehl "Ausnehmen" beispielsweise bei Bedarf beide Instanzen von "t" anstelle nur der ersten und der letzten.
Middas
1
@Middas gut entdeckt, zum Glück hat hug eine Lösung gefunden, um dies zu beheben.
FBryant87
1

Wenn Leistung und Speicher ein Problem sind, empfehle ich diese sehr effiziente Implementierung. Nach dem Heap-Algorithmus in Wikipedia sollte es der schnellste sein. Hoffe es passt zu deinem Bedürfnis :-)!

Nur zum Vergleich mit einer Linq-Implementierung für 10! (Code enthalten):

  • Dies: 36288000 Artikel in 235 Millisekunden
  • Linq: 36288000 Artikel in 50051 Millisekunden

    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");
    
            }
        }
    }
Eric Ouellet
quelle
1

Hier ist meine Lösung in JavaScript (NodeJS). Die Hauptidee ist, dass wir jeweils ein Element nehmen, es aus der Zeichenfolge "entfernen", den Rest der Zeichen variieren und das Element vorne einfügen.

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;

Und hier sind die 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);
    })
  })
})
Maria Ines Parnisari
quelle
1

Hier ist die einfachste Lösung, die ich mir vorstellen kann:

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

Die distributeFunktion verwendet ein neues Element eund eine n-Element-Liste und gibt eine Liste von n+1Listen zurück, die jeweils ean einer anderen Stelle eingefügt wurden. Beispiel: Einfügen 10an jeder der vier möglichen Stellen in der 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]]

Die permuteFunktion faltet sich nacheinander über jedes Element und verteilt sich auf die bisher akkumulierten Permutationen, die in allen Permutationen gipfeln. Zum Beispiel die 6 Permutationen der 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]]

Das Ändern von foldauf a scan, um die Zwischenakkumulatoren beizubehalten, gibt Aufschluss darüber, wie die Permutationen jeweils für ein Element erzeugt werden:

> 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]]]
Jon Harrop
quelle
1

Listet Permutationen einer Zeichenfolge auf. Vermeidet Doppelarbeit, wenn Zeichen wiederholt werden:

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);
  }
}
Val
quelle
2
Bei so vielen bereits vorhandenen Arbeitslösungen möchten Sie möglicherweise beschreiben, was Ihre Lösung von allen anderen Lösungen hier unterscheidet.
nvoigt
Vermeidet Doppelarbeit, wenn Zeichen wiederholt werden (von chindirala für eine andere Antwort). Für "aab": aab aba baa
Val
1

Aufbauend auf der Lösung von @ Peter finden Sie hier eine Version, die eine einfache Permutations()Erweiterungsmethode im LINQ-Stil deklariert , die für alle funktioniert IEnumerable<T>.

Verwendung (Beispiel für Zeichenfolgen):

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

Ausgänge:

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

Oder auf einem anderen Sammlungstyp:

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

Ausgänge:

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

Hier ist die Funktion, die alle Permutationen rekursiv druckt.

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;
    }
user2674028
quelle
0
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);
    }
}
Pankaj
quelle
0

Hier ist eine C # -Antwort, die etwas vereinfacht ist.

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

Ausgabe:

1 2 3
1 3 2

2 1 3
2 3 1

3 2 1
3 1 2
Sai
quelle
0

Dies ist meine Lösung, die für mich leicht zu verstehen ist

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 });
}
Eduardo Teixeira
quelle
0

Hier ist noch eine Implementierung des erwähnten Algo.

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

    }
}
Deepak Rohilla
quelle
new Permutation().GenerateFor("aba")Ausgängestring[4] { "ab", "baa", "baa", "ab" }
Atomosk
0
    //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);
Bolajiniy
quelle
Es wäre großartig, wenn Sie ein wenig erläutern könnten, wie dieser Code funktioniert, anstatt ihn hier in Ruhe zu lassen.
iBug
-1
    /// <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);
        }
    }        
CodeR
quelle