Algorithmus zur Rückgabe aller Kombinationen von k Elementen aus n

Question

Ich möchte eine Funktion schreiben, die ein Array von Buchstaben als Argument und eine Anzahl von diesen Buchstaben zur Auswahl nimmt.

Angenommen, Sie stellen ein Feld mit 8 Buchstaben zur Verfügung und möchten 3 Buchstaben daraus auswählen. Dann sollten Sie erhalten:

8! / ((8 - 3)! * 3!) = 56

Arrays (oder Wörter), die aus jeweils 3 Buchstaben bestehen.

Answer 1

Kunst der Computerprogrammierung Band 4: Faszikel 3 hat eine Menge davon, die vielleicht besser zu Ihrer speziellen Situation passen als das, was ich beschrieben habe.

Graue Codes

Ein Problem, auf das Sie stoßen werden, ist natürlich der Speicherplatz und ziemlich schnell werden Sie Probleme mit 20 Elementen in Ihrer Menge haben. 20 C ₃ \= 1140. Und wenn Sie die Menge iterieren wollen, verwenden Sie am besten einen modifizierten Gray-Code-Algorithmus, damit Sie nicht alle Daten im Speicher halten müssen. Diese generieren die nächste Kombination aus der vorherigen und vermeiden Wiederholungen. Es gibt viele dieser Algorithmen für verschiedene Zwecke. Wollen wir die Unterschiede zwischen aufeinander folgenden Kombinationen maximieren? minimieren? usw.

Einige der Originalarbeiten, die Gray Codes beschreiben:

1. Einige Hamilton-Pfade und ein Algorithmus für minimale Änderungen
2. Algorithmus zur Erzeugung von Kombinationen benachbarter Übergänge

Hier finden Sie einige andere Beiträge zu diesem Thema:

1. Eine effiziente Implementierung des Algorithmus zur Erzeugung von Kombinationen aus Eades, Hickey und Read Adjacent Interchange (PDF, mit Code in Pascal)
2. Kombinierte Generatoren
3. Übersicht über kombinatorische Gray-Codes (PostScript)
4. Ein Algorithmus für Gray Codes

Chase's Twiddle (Algorithmus)

Phillip J Chase, ` Algorithmus 382: Kombinationen von M aus N Objekten ' (1970)

Der Algorithmus in C ...

Index der Kombinationen in lexikografischer Reihenfolge (Buckles Algorithmus 515)

Sie können eine Kombination auch über ihren Index (in lexikografischer Reihenfolge) referenzieren. Wenn man bedenkt, dass der Index eine gewisse Veränderung von rechts nach links auf der Grundlage des Index sein sollte, kann man etwas konstruieren, das eine Kombination wiederherstellen sollte.

Wir haben also eine Menge {1,2,3,4,5,6}... und wir wollen drei Elemente. Sagen wir {1,2,3}, so können wir sagen, dass der Unterschied zwischen den Elementen eins ist und in Ordnung und minimal. {1,2,4} hat eine Änderung und ist lexikografisch die Nummer 2. Die Anzahl der "Änderungen" an der letzten Stelle entspricht also einer Änderung in der lexikographischen Ordnung. 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, denn es scheint, dass wir vom Satz zum Index den umgekehrten Weg gehen müssen - was viel schwieriger ist. Dies ist wie Schnallen löst das Problem. Ich schrieb einige C, um sie zu berechnen Ich habe den Index der Mengen anstelle eines Zahlenbereichs verwendet, um die Menge darzustellen, so dass wir immer von 0...n ausgehen. Anmerkung:

1. Da die Kombinationen nicht geordnet sind, {1,3,2} = {1,2,3}, ordnen wir sie lexikografisch.
2. Diese Methode hat eine implizite 0, um die Menge für die erste Differenz zu beginnen.

Index der Kombinationen in lexikografischer Reihenfolge (McCaffrey)

Es gibt andere Art : Das Konzept ist einfacher zu verstehen und zu programmieren, aber es fehlen die Optimierungen von Buckles. Glücklicherweise erzeugt es auch keine doppelten Kombinationen:

Das Set die das Maximum ausmacht , donde .

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. Beispiel unten (OCaml), erfordert choose Funktion, links zum Leser:

(* 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)

Ein kleiner und einfacher Iterator für Kombinationen

Die folgenden beiden Algorithmen werden zu didaktischen Zwecken bereitgestellt. Sie implementieren einen Iterator und (eine allgemeinere) Ordnergesamtkombination. Sie sind so schnell wie möglich und haben die Komplexität O( n C _k ). Der Speicherverbrauch ist begrenzt durch k .

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, ausgehend vom Anfangszustand. Da wir den Zustand zwischen verschiedenen Zuständen weitergeben müssen, werden wir keine for-Schleife verwenden, sondern stattdessen eine Rekursion,

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

Answer 2

In C#:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
  return k == 0 ? new[] { new T[0] } :
    elements.SelectMany((e, i) =>
      elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}

Verwendung:

var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);

Ergebnis:

123
124
125
134
135
145
234
235
245
345

Answer 3

Kurze Java-Lösung:

import java.util.Arrays;

public class Combination {
    public static void main(String[] args){
        String[] arr = {"A","B","C","D","E","F"};
        combinations2(arr, 3, 0, new String[3]);
    }

    static void combinations2(String[] arr, int len, int startPosition, String[] result){
        if (len == 0){
            System.out.println(Arrays.toString(result));
            return;
        }       
        for (int i = startPosition; i <= arr.length-len; i++){
            result[result.length - len] = arr[i];
            combinations2(arr, len-1, i+1, result);
        }
    }       
}

Das Ergebnis wird sein

[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]

Answer 4

Darf ich Ihnen meine rekursive Python-Lösung für dieses Problem vorstellen?

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

Beispiel für die Verwendung:

>>> len(list(choose_iter("abcdefgh",3)))
56

Ich mag ihn wegen seiner Einfachheit.

Answer 5

Nehmen wir an, Ihre Buchstabenreihe 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, so dass der nächste Schritt so aussieht:

A B C D E F G H
^ ^   ^
i j   k

Wenn du das Ende erreicht hast, machst du weiter und variierst j und dann wieder k.

A B C D E F G H
^   ^ ^
i   j k

A B C D E F G H
^   ^   ^
i   j   k

Sobald Sie j G erreicht haben, beginnen Sie auch i zu variieren.

A B C D E F G H
  ^ ^ ^
  i j k

A B C D E F G H
  ^ ^   ^
  i j   k
...

In Code geschrieben sieht das 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]);
        }
    }
}