Wie bekomme ich alle Permutationen von xPy?

Question

Ich möchte alle Permutationen der Größe Y aus einer Reihe von Größe X berechnen, ist, wenn ich habe (1,2,3) und will, dass alle Permutationen der Größe 2, 3P2, wäre es (1, 2) (1,3) (2,1) (2,3) (3,1) (3,2).

Sowohl die GSL und C ++ STL nur XPX liefern, die ich sehen kann. Könnte mir jemand bei einer C / C ++ Bibliothek Punkt, dies zu tun oder einen schnellen und Speicher effizienten Algorithmus buchstabieren?

Ich versuche, eine sehr kurze Kryptogramm zu lösen. Ich habe zwei Briefe herausgefunden und beschlossen habe, einen Brute-Force-Angriff zu tun. Ich habe „ouglg ouyakl“ und bin jede Permutation gegen ein sehr gutes Wörterbuch zu überprüfen. Ich habe 2 Buchstaben eliminiert, so seine 24P7 oder 1744364160 Möglichkeiten, die nicht so schlecht ist. Ich habe ein Perl-Programm läuft jetzt, so dass dies ein interessanter Test des Gesamtwirkungsgrades der Programmierzeit + Laufzeit sein. :)

(Nein, ich möchte nicht nur die Antwort auf die Krypto.)

Answer 1

Ich habe verwendet diese Bibliothek vor (beachten Sie, es ist C ++ in Code), die etwas ähnliches tun musste. Es hat Permutationen und Kombinationen, mit und ohne Wiederholung. Für Ihr Problem sollte dies genügen (ungetestet ...):

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator first = v.begin(), middle = v.begin() + 2, last = v.end();

do {
    // do stuff with elements in range first...middle (but dont change them)
} while(next_partial_permutation(first, middle, last));

Answer 2

Sie können die Kombinationen erhalten, indem std::next_permutation() auf einem vector<bool> von Fahnen verwenden. Unter Ihrem Beispiel aus 2 Elementen aus (1,2,3) Kommissionierung, starten Sie Ihren Vektor als (false, true, true). Die Wiederholung next_permutation() auf dies wird Ihnen (true, false, true) dann (true, true, false), vor dem Start über.

Da Sie Permutationen nicht Kombinationen wollen, Karte jede Kombination mit dem Satz von tatsächlichen Elementen (z (true, false, true) wird (1, 3)) und dann erzeugen alle Permutationen dieses mit next_permutation() wieder.

Answer 3

Ich habe nicht exacly Ihre Frage zu Kryptogramm. Aber wenn Sie wollen längste Permutation (Anagramm) dieser Wörter in Ihrem Wörterbuch finden, kann sich seinen Weg versuchen.

1. bitmask deines Wortes erstellen. Sie können sich wahrscheinlich 64-Bit-Arithmetik verwenden, so dass Sie in fast 3 alpahbets passen.

a-> erster Bit, b-> zweites Bit und so weiter. Wenn Sie Wort in Ihrem „ouglg ouyakl“ Fall dieses Mittelwert

 abcdefghijklmnopqrstuvxyzabcdefghijklmnopqrstuvxyzabcdefghijklmnop
 100000100011001000001001000000010000100100000100000000000000000000

(hoffe, dass ich etwas nicht verpasst haben) Jetzt haben Sie gleiche Bitmasken für Ihren Wortschatz erstellen.

Und wenn du gegen Vokabular Chek Sie nur tun müssen, ist

 vocabulary & ( ouglg_ouyakl ^ vocabulary)

und diese trows 0, wenn Ihr Vokabel aus ouglg_ouyakl ist.

Über Permutationen

for each permutation of numbers fom  1-n // that is 1,2 and 2,1
  for(i=0;i<end;i++)
    for(j=i+1;j<end;j++)
      SET[permutation[i]],SET[permutation[j]]

EDIT: prevous soluton war inapropriate für 24P7

.