Permutation von String-Buchstaben: Wie entfernt man wiederholte Permutationen?

Question

Hier ist eine Standardfunktion, die die Permutationen von Zeichen einer Zeichenkette ausgibt:

void permute(char *a, int i, int n)
{
   int j;
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j < n; j++) //check till end of string
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

Es funktioniert gut, aber es gibt ein Problem, es druckt auch einige doppelte Permutationen, exapmle:

wenn die Zeichenkette "AAB" ist

ist die Ausgabe:

AAB
ABA
AAB
ABA
BAA
BAA

Auch hier gibt es 3 doppelte Einträge.

Gibt es eine Möglichkeit, dies zu verhindern?

--

Gracias

Alok Kr.

Answer 1

Notieren Sie sich, welche Zeichen Sie zuvor ausgetauscht haben:

 char was[256];
 /*
 for(j = 0; j <= 255; j++)
    was[j] = 0;
 */
 bzero(was, 256);
 for (j = i; j <= n; j++)
 {
    if (!was[*(a+j)]) {
      swap((a+i), (a+j));
      permute(a, i+1, n);
      swap((a+i), (a+j)); //backtrack
      was[*(a+j)] = 1;
    }
 }

Dies muss die schnellste der bisher eingereichten Arbeiten sein, ein Benchmark auf einem "AAAABBBCCD" (100 Schleifen):

native C             - real    0m0.547s
STL next_permutation - real    0m2.141s

Answer 2

Die Standardbibliothek hat alles, was Sie brauchen:

#include <algorithm>
#include <iostream>
#include <ostream>
#include <string>
using namespace std;

void print_all_permutations(const string& s)
{
    string s1 = s;
    sort(s1.begin(), s1.end()); 
    do {
        cout << s1 << endl;
    } while (next_permutation(s1.begin(), s1.end()));
}

int main()
{
    print_all_permutations("AAB");
}

Ergebnis:

$ ./a.out
AAB
ABA
BAA

Answer 3

Ein anderer Ansatz könnte sein:

1. Das Array vorsortieren.

2. Dadurch wird sichergestellt, dass alle Duplikate nun aufeinander folgen.

3. Wir brauchen also nur das vorherige Element zu sehen, das wir repariert (und andere umgewandelt) haben

4. wenn das aktuelle Element dasselbe ist wie das vorherige, wird nicht permutiert.

Answer 4

Ich würde es folgendermaßen machen: Zuerst erzeuge ich "Gruppen" von Zeichen (d.h. AABBBC ergibt zwei Gruppen: (AA) and (BBB) and (C) .

Zunächst iterieren wir über alle Verteilungen von AA auf die n Zeichen. Für jede gefundene Verteilung iterieren wir über alle Verteilungen von BBB auf die n-2 die verbleibenden Zeichen (die nicht von einem A ). Für jede dieser Verteilungen mit A s und B s, iterieren wir über alle Verteilungen von C auf die verbleibenden freien Zeichenpositionen.

Answer 5

Sie können verwenden std::set um die Einzigartigkeit der Ergebnisse zu gewährleisten. Das heißt, wenn es sich um C++ handelt (weil Sie es als solches gekennzeichnet haben).

Andernfalls gehen Sie die Liste der Ergebnisse manuell durch und entfernen Sie Duplikate.

Sie müssen die Ergebnisse natürlich speichern und nachbearbeiten und nicht wie jetzt sofort drucken.