Ich möchte eine Funktion schreiben, die ein Array von Buchstaben als Argument und eine Anzahl von diesen Buchstaben zur Auswahl nimmt.
Angenommen, Sie geben ein Array mit 8 Buchstaben an und wollen 3 Buchstaben daraus auswählen. Dann sollten Sie erhalten:
8! / ((8 - 3)! * 3!) = 56
Arrays (oder Wörter), die jeweils aus 3 Buchstaben bestehen, erhalten.
Ein Problem, auf das Sie stoßen werden, ist natürlich der Speicherplatz, und ziemlich schnell werden Sie bei 20 Elementen in Ihrer Menge Probleme bekommen - 20C3 = 1140. Und wenn Sie über die Menge iterieren wollen, verwenden Sie am besten einen modifizierten Gray-Code-Algorithmus, damit Sie nicht alle Kombinationen im Speicher haben. Diese generieren die nächste Kombination aus der vorherigen und vermeiden Wiederholungen. Es gibt viele dieser Algorithmen für unterschiedliche Zwecke. Wollen wir die Unterschiede zwischen aufeinander folgenden Kombinationen maximieren? minimieren? usw. Einige der Originalarbeiten, die Gray Codes beschreiben:
Sie können eine Kombination auch über ihren Index (in lexikografischer Reihenfolge) referenzieren. Wenn man sich vergegenwärtigt, dass der Index eine gewisse Veränderung von rechts nach links basierend auf dem Index darstellen sollte, kann man etwas konstruieren, das eine Kombination wiederherstellen sollte. Also, wir haben eine Menge {1,2,3,4,5,6}... und wir wollen drei Elemente. Sagen wir {1,2,3}, so können wir sagen, dass die Differenz zwischen den Elementen eins ist und in Ordnung und minimal. {1,2,4} hat eine Änderung und ist lexikographisch die Nummer 2. Die Anzahl der Änderungen an der letzten Stelle macht also eine Änderung in der lexikographischen Ordnung aus. Die zweite Stelle mit einer Änderung {1,3,4} hat eine Änderung, macht aber mehr Änderungen aus, da sie an zweiter Stelle steht (proportional zur Anzahl der Elemente in der ursprünglichen Menge). Die Methode, die ich beschrieben habe, ist eine Dekonstruktion, da es scheint, dass wir von der Menge zum Index den umgekehrten Weg gehen müssen - was viel schwieriger ist. Dies ist, wie Buckles das Problem löst. Ich habe etwas C zur Berechnung geschrieben, mit kleinen Änderungen - ich habe den Index der Mengen verwendet und nicht einen Zahlenbereich, um die Menge darzustellen, so dass wir immer von 0...n ausgehen. Anmerkung:
Es gibt einen anderen Weg: Das Konzept ist einfacher zu verstehen und zu programmieren, aber es fehlen die Optimierungen von Buckles. Glücklicherweise erzeugt sie auch keine doppelten Kombinationen:
Die Menge , die maximiert, wobei .
Ein Beispiel: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1)
. Die 27. lexikographische Kombination von vier Dingen ist also: {1,2,5,6}, das sind die Indizes der Menge, die man sich ansehen will. Das folgende Beispiel (OCaml) erfordert die Funktion choose
, von links nach rechts:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
Die folgenden zwei Algorithmen werden zu didaktischen Zwecken bereitgestellt. Sie implementieren einen Iterator und einen (allgemeineren) Ordner für Gesamtkombinationen.
Sie sind so schnell wie möglich und haben die Komplexität O(nCk). Der Speicherverbrauch ist durch k
begrenzt.
Wir beginnen mit dem Iterator, der für jede Kombination eine vom Benutzer bereitgestellte Funktion aufruft
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
Eine allgemeinere Version ruft die vom Benutzer bereitgestellte Funktion zusammen mit der Zustandsvariablen auf, beginnend mit dem Anfangszustand. Da wir den Zustand zwischen verschiedenen Zuständen weitergeben müssen, werden wir die for-Schleife nicht verwenden, sondern stattdessen eine Rekursion einsetzen,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x
Nehmen wir an, Ihre Anordnung von Buchstaben sieht wie folgt aus: "ABCDEFGH". Sie haben drei Indizes (i, j, k), die angeben, welche Buchstaben Sie für das aktuelle Wort verwenden werden:
A B C D E F G H ^ ^ ^ i j k
Zuerst variiert man k, also sieht der nächste Schritt so aus:
A B C D E F G H ^ ^ ^ i j k
Wenn du das Ende erreicht hast, gehst du weiter und variierst j und dann wieder k.
A B C D E F G H ^ ^ ^ i j kA B C D E F G H ^ ^ ^ i j k
Sobald j G erreicht hat, beginnt man auch i zu variieren.
A B C D E F G H ^ ^ ^ i j kA B C D E F G H ^ ^ ^ i j k ...
In Code geschrieben sieht das in etwa so aus
void print_combinations(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}