Ich generiere alle Permutationen eines Strings mit Bitmaske.
void recurse(string s, int mask,int taken){
if(taken == n){
cout << " ";
return;
}
for(int i = 0; i < n; i++){
if(((1 << i) & mask) == 0){
cout << s[i];
recurse(s, (mask|(1 << i)), taken + 1);
}
}
}
In dieser Funktion ist n die Länge der Zeichenfolge. Ich verfolge, wie viele Zeichen bisher mit der genommenen Variablen gedruckt wurden. In der Hauptfunktion rufe ich an
recurse(s,0,0);
Das funktioniert aber nicht richtig. Zur Eingabe
rot
Seine Ausgabe ist
red de erd dr dre er
Wo gehe ich falsch?
UPDATE // Der folgende Code funktioniert einwandfrei.
void recurse(string s, int mask,int taken, string pref){
if(taken == n){
cout << pref <<endl;
return;
}
for(int i = 0; i < n; i++){
if(((mask >> i) & 1) == 0){
recurse(s,(mask | (1 << i)),taken + 1, pref + s[i]);
}
}
}
Eigentlich hat der Fragesteller die Antwort selbst gegeben. (Glückwunsch.)
Da ich bereits angefangen habe zu fummeln (konnte nicht widerstehen), möchte ich auch meine Lösung vorstellen:
#include <iostream>
#include <string>
using namespace std;
void recurse(
const string &s, unsigned mask = 0, const string &out = string())
{
size_t n = s.size();
if (out.size() == n) cout << ' ' << out;
for (size_t i = 0; i < n; ++i) {
unsigned bit = 1 << i;
if (mask & bit) continue;
recurse(s, mask | bit, out + s[i]);
}
}
int main()
{
string test = "red";
recurse(test);
cout << endl;
return 0;
}
Zusammengestellt und getestet:
red rde erd edr dre der
recurse()iteriert durch alle Zeichen der sSuche nach einem, der nicht bereits maskals genommen markiert ist . Jedes gefundene Zeichen wird zur Ausgabe hinzugefügt out. Der rekursive Aufruf wiederholt ihn dann für alle nicht aufgenommenen Zeichen.
Schauen Sie sich den Beispielcode selbst auf ideone an .
Dieser Artikel stammt aus dem Internet. Bitte geben Sie beim Nachdruck die Quelle an.
Bei Verstößen wenden Sie sich bitte [email protected] Löschen.
Lass mich ein paar Worte sagen