C++ alle Kombinationen eines Strings mit der Länge L mit zurücklegen?
Hallo,
ich möchte so etwas wie einen Password-List-Generator schreiben, komme aber nicht auf die richtige Rekursionsfunktion.
Es soll zum Beispiel aus einem Zeichensatz wie "abcdef" und der information L = 9 Passwörter im vector<string> zurückgegeben werden, bei denen jeder der Buchstaben an jeder Position 0, 1, .., 9 mal vorkommt, wie beim Passwortgenerator "crunch".
Hat mir jemand ein Code-Beispiel parat?
Viele Grüße
Lukas Z
2 Antworten
Eine Möglichkeit, alle Kombinationen eines Zeichenstrings mit einer bestimmten Länge zu generieren, besteht darin, eine rekursive Funktion zu verwenden. Diese Funktion nimmt drei Argumente entgegen: den Zeichenstring, die Länge des gewünschten Passworts und einen vector<string>, in dem die generierten Passwörter gespeichert werden.
Die Funktion verwendet dann eine Schleife, um über jedes Zeichen im Zeichenstring zu iterieren, und fügt jedes Zeichen in einen temporären String ein. Dieser temporäre String wird dann an die rekursive Funktion weitergeleitet, um die nächste Stelle des Passworts zu generieren. Wenn der temporäre String die gewünschte Passwortlänge erreicht hat, wird er in den vector<string> gespeichert und die rekursive Funktion beendet.
Hier ist ein Beispiel für eine solche Funktion:
void generatePasswords(const string& charset, int passwordLength, vector<string>& passwords) {
// Wenn das Passwort die gewünschte Länge erreicht hat, wird es in den vector<string> gespeichert.
if (passwordLength == 0) {
passwords.push_back(tempPassword);
return;
}
// Iteration über jedes Zeichen im Zeichenstring.
for (int i = 0; i < charset.length(); i++) {
// Hinzufügen des aktuellen Zeichens zum temporären Passwort.
tempPassword += charset[i];
Um die Funktion aufzurufen, können Sie Folgendes verwenden:
vector<string> passwords;
string charset = "abcdef";
int passwordLength = 9;
generatePasswords(charset, passwordLength, passwords);
// Rekursive Aufruf der Funktion, um die nächste Stelle des Passworts zu generieren.
generatePasswords(charset, passwordLength - 1, passwords);
// Entfernen des zuletzt hinzugefügten Zeichens aus dem temporären Passwort.
tempPassword.pop_back();
}
}
Es gibt einige Möglichkeiten, um das zu erreichen. Eine davon wäre, eine generator-Funktion zu verwenden, die ein Iterator-Objekt zurückgibt, das jedes Mal das nächste Element liefert, wenn es aufgerufen wird. Ein Generator-Funktion kann in C++14 mit dem Schlüsselwort co_yield erstellt werden. Hier ist ein Beispiel für eine solche Funktion:
generator<string> next_combination(string dataset, int k)
{
// Dies ist eine rekursive Funktion, die alle möglichen
// Kombinationen von Elementen aus dataset mit Länge k
// generiert.
auto generate = [&](string prefix, int k) -> void
{
// Wenn k = 0, ist die aktuelle Kombination bereitet
// und kann zurückgegeben werden.
if (k == 0)
{
co_yield prefix;
}
else
{
// Für jedes Element i in dataset, füge es zum
// aktuellen Präfix hinzu und rekursiv weiter.
for (int i = 0; i < dataset.size(); i++)
{
string new_prefix = prefix + dataset.at(i);
co_generate(new_prefix, k - 1);
}
}
};
// Starte die Rekursion mit einem leeren Präfix und der
// gewünschten Länge k.
co_generate("", k);
}
Diese Funktion kann dann verwendet werden, um über alle möglichen Kombinationen von Elementen aus dataset mit Länge k zu iterieren. Zum Beispiel:
auto combos = next_combination("abc", 2);
for (const auto& c : combos)
{
std::cout << c << std::endl;
}
Dieser Code würde alle möglichen Kombinationen von 2 Elementen aus "abc" ausgeben: "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb" und "cc".
Danke.
Ich bekomme aber für den Rückgabewert folgenden error:
In file included from uselib.cpp:2:
cracklib.h:124:13: error: 'generator' does not name a type
generator<string> next(string prefix, int k)
^~~~~~~~~
uselib.cpp: In function 'int main()':
uselib.cpp:78:21: error: 'struct CrackLib::combinations' has no member named 'ne
xt'
std::cout << lc.next("", 3);
Implementation:
generator<string> next(string prefix, int k)
{
auto generate = [&](string prefix, int k) -> void
{
if (k == 0)
{
IND++;
co_yield prefix;
}
for (int i = 0; i < DATASET.size(); i++)
{
string new_Prefix = "";
new_Prefix = prefix + DATASET.at(i);
co_generate(new_Prefix, k - 1);
}
};
co_generate("", k);
}
aber es gibt doch gar kein lambda "co_generate"
wenn du alle Passwörter mit einem Zeichensatz von m Zeichen mit einer Länge von n erzeugen willst, würde ich einfach einen Zähler von 0 bis (m^n)-1 laufen lassen und den Zähler jeweils in eine Zahl zur Basis m umwandeln.
Jede Ziffer dieser Zahl steht dann für genau ein Zeichen in deinem Zeichensatz.
Da braucht es keine Rekursion.
Wobei die Rekursion nicht so sonderlich tief ist und damit die Kosten für die Aufrufe überschaubar bleiben.
Im iterativen Fall muß ich statt des Calls für die wiederkehrende Konversion entsprechend bezahlen.
Andererseits, wenn es eine Tailrecursion ist und der Compiler hart optimiert, dann ist die Rekursion vmöglicherweise weg.
Ok, danke
Wie genau meinst du das?
Bisher habe ich das so verstanden:
std::vector<string> getzs(const std::string zeichen, int n)
{
std::vector<string> res;
for (int i = 0; i < pow(zeichen.size(), n); i++)
{
for (char ch : std::to_string(i))
{
// und weiter?
}
}
}
aber ich verstehe nicht, was du mit
jeweils in eine Zahl zur Basis m umwandeln
meintest..
Jede Ziffer dieser Zahl steht dann für genau ein Zeichen in deinem Zeichensatz.
Das wäre optimal
Ok, ich habe das wie folgt gemacht:
Jetzt frage ich mich aber, wie ich immer nur eines nach dem anderen zurückgeben kann, ohne einen vector mit 1000000 elementen zu brauchen...
Bei mir bekomme ich nun aber immer nur die erste Permutation.
Ich muss die Rekursion also immer nach einem Teilergebnis kurz "anhalten"