Liste aller möglichen Permutationen eines Strings generieren

30 answers
  • Hierfür gibt es mehrere Möglichkeiten. Übliche Methoden verwenden Rekursion, Memoisierung oder dynamische Programmierung. Die Grundidee ist, dass Sie eine Liste aller Zeichenfolgen der Länge 1 erstellen und dann bei jeder Iteration für alle in der letzten Iteration erzeugten Zeichenfolgen die mit jedem Zeichen in der Zeichenfolge verkettete Zeichenfolge einzeln hinzufügen. (Der Variablenindex im nachstehenden Code verfolgt den Beginn der letzten und der nächsten Iteration.)

    Einige Pseudocodes:

     list = originalString.split('')
    index = (0,0)
    list = [""]
    for iteration n in 1 to y:
      index = (index[1], len(list))
      for string s in list.subset(index[0] to end):
        for character c in originalString:
          list.add(s + c)
     

    Sie müssen dann alle Zeichenfolgen mit einer Länge von weniger als x entfernen. Sie werden die ersten (x-1) * len (originalString) -Einträge im Liste.

    27 July 2015
    4 revs, 3 users 80%alumb
  • Verwenden Sie besser die Rückverfolgung

     #include <stdio.h>
    #include <string.h>
    
    void swap(char *a, char *b) {
        char temp;
        temp = *a;
        *a = *b;
        *b = temp;
    }
    
    void print(char *a, int i, int n) {
        int j;
        if(i == n) {
            printf("%s\n", a);
        } else {
            for(j = i; j <= n; j++) {
                swap(a + i, a + j);
                print(a, i + 1, n);
                swap(a + i, a + j);
            }
        }
    }
    
    int main(void) {
        char a[100];
        gets(a);
        print(a, 0, strlen(a) - 1);
        return 0;
    }
     
    20 January 2017
    6 revs, 5 users 47%Unnykrishnan S
  • Sie werden eine Menge Strings bekommen, das ist sicher ...

    {t \ select {s + t} http://www.codecogs.com/eq.latex?%7Bt%20%5Cchoose%20% 7Bs + t% 7D% 7D . Wir können dies herausfinden, indem wir zuerst jede (s, t) -Kombination in binärer Form (also Länge (s + t)) generieren und die Anzahl der Nullen links von jeder 1 zählen.

    10001000011101 - & gt; wird zur Permutation: {0, 3, 4, 4, 4, 1}

    05 August 2008
    nlucaroni
  • Nicht rekursive Lösung nach Knuth, Python-Beispiel:

     def nextPermutation(perm):
        k0 = None
        for i in range(len(perm)-1):
            if perm[i]<perm[i+1]:
                k0=i
        if k0 == None:
            return None
    
        l0 = k0+1
        for i in range(k0+1, len(perm)):
            if perm[k0] < perm[i]:
                l0 = i
    
        perm[k0], perm[l0] = perm[l0], perm[k0]
        perm[k0+1:] = reversed(perm[k0+1:])
        return perm
    
    perm=list("12345")
    while perm:
        print perm
        perm = nextPermutation(perm)
     
    09 November 2010
    rocksportrocker
  • Hier ist eine einfache Lösung in C #.

    Sie generiert nur die unterschiedlichen Permutationen einer gegebenen Zeichenfolge.

         static public IEnumerable<string> permute(string word)
        {
            if (word.Length > 1)
            {
    
                char character = word[0];
                foreach (string subPermute in permute(word.Substring(1)))
                {
    
                    for (int index = 0; index <= subPermute.Length; index++)
                    {
                        string pre = subPermute.Substring(0, index);
                        string post = subPermute.Substring(index);
    
                        if (post.Contains(character))
                                continue;                       
    
                        yield return pre + character + post;
                    }
    
                }
            }
            else
            {
                yield return word;
            }
        }
     
    05 July 2010
    Prakhar Gupta
  • Möglicherweise sehen Sie unter " die Subsets eines Sets effizient auflisten " Beschreibt einen Algorithmus, um einen Teil des gewünschten Ergebnisses auszuführen. Generieren Sie schnell alle Teilmengen von N Zeichen von Länge x bis y. Sie enthält eine Implementierung in C.

    Für jede Teilmenge müssen Sie noch alle Permutationen generieren. Wenn Sie zum Beispiel 3 Zeichen von "abcde" wünschen, würde dieser Algorithmus Ihnen "abc", "abd", "abe" ... geben, aber Sie müssten jeden für "acb", " bac "," bca "usw.

    14 November 2008
    AShelly
  • Einige funktionierende Java-Codes basierend auf Antwort von Sarp :

     public class permute {
    
        static void permute(int level, String permuted,
                        boolean used[], String original) {
            int length = original.length();
            if (level == length) {
                System.out.println(permuted);
            } else {
                for (int i = 0; i < length; i++) {
                    if (!used[i]) {
                        used[i] = true;
                        permute(level + 1, permuted + original.charAt(i),
                           used, original);
                        used[i] = false;
                    }
                }
            }
        }
    
        public static void main(String[] args) {
            String s = "hello";
            boolean used[] = {false, false, false, false, false};
            permute(0, "", used, s);
        }
    }
     
    23 May 2017
    2 revsLazer
  • Hier gibt es viele gute Antworten. Ich schlage auch eine sehr einfache rekursive Lösung in C ++ vor.

     #include <string>
    #include <iostream>
    
    template<typename Consume>
    void permutations(std::string s, Consume consume, std::size_t start = 0) {
        if (start == s.length()) consume(s);
        for (std::size_t i = start; i < s.length(); i++) {
            std::swap(s[start], s[i]);
            permutations(s, consume, start + 1);
        }
    }
    
    int main(void) {
        std::string s = "abcd";
        permutations(s, [](std::string s) {
            std::cout << s << std::endl;
        });
    }
     

    Hinweis : Zeichenfolgen Bei wiederholten Zeichen werden keine eindeutigen Permutationen erzeugt.

    08 January 2014
    gd1
  • Ich habe das in Ruby soeben auf den Punkt gebracht:

     def perms(x, y, possible_characters)
      all = [""]
      current_array = all.clone
      1.upto(y) { |iteration|
        next_array = []
        current_array.each { |string|
          possible_characters.each { |c|
            value = string + c
            next_array.insert next_array.length, value
            all.insert all.length, value
          }
        }
        current_array = next_array
      }
      all.delete_if { |string| string.length < x }
    end
     

    Sie könnten sich mit der Sprach-API beschäftigen Für integrierte Permutationstyp-Funktionen können Sie möglicherweise mehr optimierten Code schreiben, aber wenn die Zahlen so hoch sind, bin ich mir nicht sicher, ob es einen großen Weg gibt, eine Menge Ergebnisse zu erzielen.

    Die Idee hinter dem Code ist immer mit der Zeichenfolge der Länge 0 und verfolgt dann alle Zeichenfolgen der Länge Z, wobei Z die aktuelle Größe in der Iteration ist. Gehen Sie dann jede Zeichenfolge durch und hängen Sie jedes Zeichen an jede Zeichenfolge an. Zum Schluss entfernen Sie alle, die sich unterhalb der x-Schwelle befanden, und geben das Ergebnis zurück.

    Ich habe es nicht mit möglicherweise bedeutungslosen Eingaben getestet (Liste der Nullzeichen, seltsame Werte von x) und y usw.).

    02 August 2008
    Matt Mitchell
  • Rekursive Lösung in C ++

     int main (int argc, char * const argv[]) {
            string s = "sarp";
            bool used [4];
            permute(0, "", used, s);
    }
    
    void permute(int level, string permuted, bool used [], string &original) {
        int length = original.length();
    
        if(level == length) { // permutation complete, display
            cout << permuted << endl;
        } else {
            for(int i=0; i<length; i++) { // try to add an unused character
                if(!used[i]) {
                    used[i] = true;
                    permute(level+1, original[i] + permuted, used, original); // find the permutations starting with this string
                    used[i] = false;
                }
            }
    }
     
    12 July 2012
    KMorazHGM