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

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

Angenommen, Sie geben ein Array mit 8 Buchstaben an und möchten 3 Buchstaben daraus auswählen. Dann sollten Sie bekommen:

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

Arrays (oder Wörter) bestehen im Gegenzug aus jeweils 3 Buchstaben.

Kunst der Computerprogrammierung Band 4: Fascicle 3 enthält eine Menge davon, die möglicherweise besser zu Ihrer speziellen Situation passen, als ich es beschreibe.

Gray Codes

Ein Problem, auf das Sie stoßen werden, ist natürlich der Speicher. Ziemlich schnell treten Probleme mit 20 Elementen in Ihrem Satz auf - ²⁰ C ₃ = 1140. Wenn Sie den Satz durchlaufen möchten, verwenden Sie am besten ein modifiziertes Grau Code-Algorithmus, damit Sie nicht alle im Speicher halten. Diese erzeugen die nächste Kombination aus der vorherigen und vermeiden Wiederholungen. Es gibt viele davon für verschiedene Zwecke. Wollen wir die Unterschiede zwischen aufeinanderfolgenden Kombinationen maximieren? minimieren? und so weiter.

Einige der Originalarbeiten, die Gray-Codes beschreiben:

1. Einige Hamilton-Pfade und ein Minimal-Change-Algorithmus
2. Algorithmus zur Erzeugung benachbarter Austauschkombinationen

Hier sind einige andere Artikel zum Thema:

1. Eine effiziente Implementierung des Eades, Hickey, Read Adjacent Interchange Combination Generation-Algorithmus (PDF, mit Code in Pascal)
2. Kombinationsgeneratoren
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 lexikographischer Reihenfolge (Buckles-Algorithmus 515)

Sie können eine Kombination auch anhand ihres Index (in lexikografischer Reihenfolge) referenzieren. Wenn wir erkennen, dass sich der Index basierend auf dem Index von rechts nach links ändern sollte, können wir etwas konstruieren, das eine Kombination wiederherstellen sollte.

Wir haben also eine Menge {1,2,3,4,5,6} ... und wir wollen drei Elemente. Nehmen wir an, {1,2,3} wir können sagen, dass der Unterschied zwischen den Elementen eins und in Ordnung und minimal ist. {1,2,4} hat eine Änderung und ist lexikografisch die Nummer 2. Die Anzahl der 'Änderungen' an der letzten Stelle macht also eine Änderung der lexikografischen Reihenfolge aus. Der zweite Platz mit einer Änderung {1,3,4} hat eine Änderung, führt jedoch zu mehr Änderungen, da er an zweiter Stelle steht (proportional zur Anzahl der Elemente in der ursprünglichen Menge).

Die Methode, die ich beschrieben habe, ist eine Dekonstruktion, wie es scheint, von der Menge bis zum Index müssen wir das Gegenteil tun - was viel schwieriger ist. So löst Buckles das Problem. Ich habe ein C geschrieben, um sie mit geringfügigen Änderungen zu berechnen. Ich habe den Index der Mengen anstelle eines Zahlenbereichs verwendet, um die Menge darzustellen, also arbeiten wir immer von 0 ... n. Hinweis:

1. Da Kombinationen ungeordnet sind, ist {1,3,2} = {1,2,3} - wir ordnen an, dass sie lexikografisch sind.
2. Diese Methode hat eine implizite 0, um die Menge für die erste Differenz zu starten.

Index der Kombinationen in lexikographischer Reihenfolge (McCaffrey)

Es gibt noch einen anderen Weg : Das Konzept ist leichter zu verstehen und zu programmieren, aber ohne die Optimierungen von Buckles. Glücklicherweise werden auch keine doppelten Kombinationen erzeugt:

Das Set , das maximiert , wo .

Zum Beispiel : 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Die 27. lexikografische Kombination von vier Dingen lautet also: {1,2,5,6}, das sind die Indizes aller Mengen, die Sie betrachten möchten. Das folgende Beispiel (OCaml) erfordert eine chooseFunktion, die dem Leser überlassen bleibt:

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

Die folgenden zwei Algorithmen werden für didaktische Zwecke bereitgestellt. Sie implementieren einen Iterator und eine (allgemeinere) Ordner-Gesamtkombination. Sie sind so schnell wie möglich und haben die Komplexität O ( ⁿ 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 Statusvariablen ab dem Anfangszustand auf. Da wir den Zustand zwischen verschiedenen Zuständen übergeben müssen, verwenden wir nicht die for-Schleife, sondern die 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

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)));
}

Verwendungszweck:

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

Ergebnis:

123
124
125
134
135
145
234
235
245
345

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);
        }
    }       
}

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]

Darf ich 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))

Anwendungsbeispiel:

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

Ich mag es wegen seiner Einfachheit.

Nehmen wir an, Ihre Buchstabenreihe sieht folgendermaßen aus: "ABCDEFGH". Sie haben drei Indizes (i, j, k), die angeben, welche Buchstaben Sie für das aktuelle Wort verwenden werden. Sie beginnen mit:

A B C D E F G H
^^^
ijk

Zuerst variierst du k, also sieht der nächste Schritt so aus:

A B C D E F G H
^^^
ijk

Wenn Sie das Ende erreicht haben, fahren Sie fort und variieren j und dann wieder k.

A B C D E F G H
^^^
ijk

A B C D E F G H
^^^
ijk

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

A B C D E F G H
  ^^^
  ijk

A B C D E F G H
  ^^^
  ijk
...

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

Der folgende rekursive Algorithmus wählt alle k-Element-Kombinationen aus einer geordneten Menge aus:

• Wählen Sie das erste Element iIhrer Kombination
• Kombinieren Sie imit jeder der Kombinationen von k-1Elementen, die rekursiv aus der Menge der Elemente ausgewählt wurden, die größer als sind i.

Wiederholen Sie die obigen Schritte für jeden iim Set.

Es ist wichtig, dass Sie den Rest der Elemente als größer als auswählen i, um Wiederholungen zu vermeiden. Auf diese Weise wird [3,5] nur einmal ausgewählt, da [3] mit [5] kombiniert wird, anstatt zweimal (die Bedingung beseitigt [5] + [3]). Ohne diese Bedingung erhalten Sie Variationen anstelle von Kombinationen.

In C ++ erzeugt die folgende Routine alle Kombinationen des Längenabstands (first, k) zwischen dem Bereich [first, last]:

#include <algorithm>

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

Es kann folgendermaßen verwendet werden:

#include <string>
#include <iostream>

int main()
{
    std::string s = "12345";
    std::size_t comb_size = 3;
    do
    {
        std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
    } while (next_combination(s.begin(), s.begin() + comb_size, s.end()));

    return 0;
}

Dadurch wird Folgendes gedruckt:

123
124
125
134
135
145
234
235
245
345

Ich fand diesen Thread nützlich und dachte, ich würde eine Javascript-Lösung hinzufügen, die Sie in Firebug einfügen können. Abhängig von Ihrer JS-Engine kann es einige Zeit dauern, wenn die Startzeichenfolge groß ist.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

Die Ausgabe sollte wie folgt sein:

abc
ab
ac
a
bc
b
c

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;
    }
}

Kurzes Beispiel in Python:

def comb(sofar, rest, n):
    if n == 0:
        print sofar
    else:
        for i in range(len(rest)):
            comb(sofar + rest[i], rest[i+1:], n-1)

>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde

Zur Erläuterung wird die rekursive Methode anhand des folgenden Beispiels beschrieben:

Beispiel: ABCDE
Alle Kombinationen von 3 wären:

• A mit allen Kombinationen von 2 aus dem Rest (BCDE)
• B mit allen Kombinationen von 2 aus dem Rest (CDE)
• C mit allen Kombinationen von 2 aus dem Rest (DE)

Einfacher rekursiver Algorithmus in Haskell

import Data.List

combinations 0 lst = [[]]
combinations n lst = do
    (x:xs) <- tails lst
    rest   <- combinations (n-1) xs
    return $ x : rest

Wir definieren zunächst den Sonderfall, dh die Auswahl von Nullelementen. Es wird ein einzelnes Ergebnis erzeugt, bei dem es sich um eine leere Liste handelt (dh eine Liste, die eine leere Liste enthält).

Für n> 0 xgeht jedes Element der Liste durch und xsist jedes Element danach x.

restwählt n - 1Elemente aus xseinem rekursiven Aufruf von aus combinations. Das Endergebnis der Funktion ist eine Liste, in der jedes Element x : rest(dh eine Liste mit xKopf und restSchwanz) für jeden unterschiedlichen Wert von xund angegeben ist rest.

> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]

Und da Haskell faul ist, wird die Liste natürlich nach Bedarf nach und nach generiert, sodass Sie teilweise exponentiell große Kombinationen auswerten können.

> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
 "abcdefgo","abcdefgp","abcdefgq"]

Und hier kommt Großvater COBOL, die viel bösartige Sprache.

Nehmen wir ein Array von 34 Elementen mit jeweils 8 Bytes an (rein willkürliche Auswahl). Die Idee ist, alle möglichen 4-Element-Kombinationen aufzulisten und in ein Array zu laden.

Wir verwenden 4 Indizes, jeweils einen für jede Position in der Gruppe von 4

Das Array wird wie folgt verarbeitet:

    idx1 = 1
    idx2 = 2
    idx3 = 3
    idx4 = 4

Wir variieren idx4 von 4 bis zum Ende. Für jedes idx4 erhalten wir eine eindeutige Kombination von Vierergruppen. Wenn idx4 am Ende des Arrays ankommt, erhöhen wir idx3 um 1 und setzen idx4 auf idx3 + 1. Dann führen wir idx4 wieder bis zum Ende aus. Wir gehen auf diese Weise vor und erweitern idx3, idx2 bzw. idx1, bis die Position von idx1 vom Ende des Arrays weniger als 4 beträgt. Damit ist der Algorithmus beendet.

1          --- pos.1
2          --- pos 2
3          --- pos 3
4          --- pos 4
5
6
7
etc.

Erste Iterationen:

1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.

Ein COBOL-Beispiel:

01  DATA_ARAY.
    05  FILLER     PIC X(8)    VALUE  "VALUE_01".
    05  FILLER     PIC X(8)    VALUE  "VALUE_02".
  etc.
01  ARAY_DATA    OCCURS 34.
    05  ARAY_ITEM       PIC X(8).

01  OUTPUT_ARAY   OCCURS  50000   PIC X(32).

01   MAX_NUM   PIC 99 COMP VALUE 34.

01  INDEXXES  COMP.
    05  IDX1            PIC 99.
    05  IDX2            PIC 99.
    05  IDX3            PIC 99.
    05  IDX4            PIC 99.
    05  OUT_IDX   PIC 9(9).

01  WHERE_TO_STOP_SEARCH          PIC 99  COMP.

* Stop the search when IDX1 is on the third last array element:

COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3     

MOVE 1 TO IDX1

PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
   COMPUTE IDX2 = IDX1 + 1
   PERFORM UNTIL IDX2 > MAX_NUM
      COMPUTE IDX3 = IDX2 + 1
      PERFORM UNTIL IDX3 > MAX_NUM
         COMPUTE IDX4 = IDX3 + 1
         PERFORM UNTIL IDX4 > MAX_NUM
            ADD 1 TO OUT_IDX
            STRING  ARAY_ITEM(IDX1)
                    ARAY_ITEM(IDX2)
                    ARAY_ITEM(IDX3)
                    ARAY_ITEM(IDX4)
                    INTO OUTPUT_ARAY(OUT_IDX)
            ADD 1 TO IDX4
         END-PERFORM
         ADD 1 TO IDX3
      END-PERFORM
      ADD 1 TO IDX2
   END_PERFORM
   ADD 1 TO IDX1
END-PERFORM.

Hier ist eine elegante, generische Implementierung in Scala, wie unter 99 Scala-Probleme beschrieben .

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
    }

  def combinations[A](n: Int, ls: List[A]): List[List[A]] =
    if (n == 0) List(Nil)
    else flatMapSublists(ls) { sl =>
      combinations(n - 1, sl.tail) map {sl.head :: _}
    }
}

Wenn Sie die SQL-Syntax verwenden können, z. B. wenn Sie mit LINQ auf Felder einer Struktur oder eines Arrays zugreifen oder direkt auf eine Datenbank mit einer Tabelle namens "Alphabet" mit nur einem Zeichenfeld "Letter" zugreifen, können Sie Folgendes anpassen Code:

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

Dies gibt alle Kombinationen von 3 Buchstaben zurück, ungeachtet der Anzahl der Buchstaben in der Tabelle "Alphabet" (es können 3, 8, 10, 27 usw. sein).

Wenn Sie nur Permutationen und keine Kombinationen wünschen (dh "ACB" und "ABC" sollen unterschiedlich sein und nicht nur einmal angezeigt werden), löschen Sie einfach die letzte Zeile (die UND-Zeile) und fertig.

Nachbearbeitung: Nachdem ich die Frage erneut gelesen habe, stelle ich fest, dass der allgemeine Algorithmus erforderlich ist , nicht nur ein spezifischer für den Fall der Auswahl von 3 Elementen. Die Antwort von Adam Hughes ist vollständig, leider kann ich sie (noch) nicht abstimmen. Diese Antwort ist einfach, funktioniert aber nur, wenn Sie genau 3 Elemente möchten.

Eine weitere C # -Version mit verzögerter Generierung der Kombinationsindizes. Diese Version verwaltet ein einzelnes Array von Indizes, um eine Zuordnung zwischen der Liste aller Werte und den Werten für die aktuelle Kombination zu definieren, dh verwendet während der gesamten Laufzeit ständig O (k) zusätzlichen Speicherplatz. Der Code generiert einzelne Kombinationen, einschließlich der ersten, in O (k) -Zeit.

public static IEnumerable<T[]> Combinations<T>(this T[] values, int k)
{
    if (k < 0 || values.Length < k)
        yield break; // invalid parameters, no combinations possible

    // generate the initial combination indices
    var combIndices = new int[k];
    for (var i = 0; i < k; i++)
    {
        combIndices[i] = i;
    }

    while (true)
    {
        // return next combination
        var combination = new T[k];
        for (var i = 0; i < k; i++)
        {
            combination[i] = values[combIndices[i]];
        }
        yield return combination;

        // find first index to update
        var indexToUpdate = k - 1;
        while (indexToUpdate >= 0 && combIndices[indexToUpdate] >= values.Length - k + indexToUpdate)
        {
            indexToUpdate--;
        }

        if (indexToUpdate < 0)
            yield break; // done

        // update combination indices
        for (var combIndex = combIndices[indexToUpdate] + 1; indexToUpdate < k; indexToUpdate++, combIndex++)
        {
            combIndices[indexToUpdate] = combIndex;
        }
    }
}

Testcode:

foreach (var combination in new[] {'a', 'b', 'c', 'd', 'e'}.Combinations(3))
{
    System.Console.WriteLine(String.Join(" ", combination));
}

Ausgabe:

a b c
a b d
a b e
a c d
a c e
a d e
b c d
b c e
b d e
c d e

https://gist.github.com/3118596

Es gibt eine Implementierung für JavaScript. Es hat Funktionen, um k-Kombinationen und alle Kombinationen eines Arrays von beliebigen Objekten zu erhalten. Beispiele:

k_combinations([1,2,3], 2)
-> [[1,2], [1,3], [2,3]]

combinations([1,2,3])
-> [[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Hier haben Sie eine faul evaluierte Version dieses in C # codierten Algorithmus:

    static bool nextCombination(int[] num, int n, int k)
    {
        bool finished, changed;

        changed = finished = false;

        if (k > 0)
        {
            for (int i = k - 1; !finished && !changed; i--)
            {
                if (num[i] < (n - 1) - (k - 1) + i)
                {
                    num[i]++;
                    if (i < k - 1)
                    {
                        for (int j = i + 1; j < k; j++)
                        {
                            num[j] = num[j - 1] + 1;
                        }
                    }
                    changed = true;
                }
                finished = (i == 0);
            }
        }

        return changed;
    }

    static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
    {
        T[] elem = elements.ToArray();
        int size = elem.Length;

        if (k <= size)
        {
            int[] numbers = new int[k];
            for (int i = 0; i < k; i++)
            {
                numbers[i] = i;
            }

            do
            {
                yield return numbers.Select(n => elem[n]);
            }
            while (nextCombination(numbers, size, k));
        }
    }

Und Testteil:

    static void Main(string[] args)
    {
        int k = 3;
        var t = new[] { "dog", "cat", "mouse", "zebra"};

        foreach (IEnumerable<string> i in Combinations(t, k))
        {
            Console.WriteLine(string.Join(",", i));
        }
    }

Hoffe das hilft dir!

Ich hatte einen Permutationsalgorithmus, den ich für Project Euler in Python verwendet habe:

def missing(miss,src):
    "Returns the list of items in src not present in miss"
    return [i for i in src if i not in miss]


def permutation_gen(n,l):
    "Generates all the permutations of n items of the l list"
    for i in l:
        if n<=1: yield [i]
        r = [i]
        for j in permutation_gen(n-1,missing([i],l)):  yield r+j

Wenn

n<len(l) 

Sie sollten alle Kombinationen haben, die Sie brauchen, ohne Wiederholung, brauchen Sie sie?

Es ist ein Generator, also verwenden Sie ihn in etwa so:

for comb in permutation_gen(3,list("ABCDEFGH")):
    print comb 

Array.prototype.combs = function(num) {

    var str = this,
        length = str.length,
        of = Math.pow(2, length) - 1,
        out, combinations = [];

    while(of) {

        out = [];

        for(var i = 0, y; i < length; i++) {

            y = (1 << i);

            if(y & of && (y !== of))
                out.push(str[i]);

        }

        if (out.length >= num) {
           combinations.push(out);
        }

        of--;
    }

    return combinations;
}

Clojure-Version:

(defn comb [k l]
  (if (= 1 k) (map vector l)
      (apply concat
             (map-indexed
              #(map (fn [x] (conj x %2))
                    (comb (dec k) (drop (inc %1) l)))
              l))))

Nehmen wir an, Ihre Buchstabenreihe sieht folgendermaßen aus: "ABCDEFGH". Sie haben drei Indizes (i, j, k), die angeben, welche Buchstaben Sie für das aktuelle Wort verwenden werden. Sie beginnen mit:

A B C D E F G H
^^^
ijk

Zuerst variierst du k, also sieht der nächste Schritt so aus:

A B C D E F G H
^^^
ijk

Wenn Sie das Ende erreicht haben, fahren Sie fort und variieren j und dann wieder k.

A B C D E F G H
^^^
ijk

A B C D E F G H
^^^
ijk

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

A B C D E F G H
  ^^^
  ijk

A B C D E F G H
  ^^^
  ijk
...

function initializePointers($cnt) {
    $pointers = [];

    for($i=0; $i<$cnt; $i++) {
        $pointers[] = $i;
    }

    return $pointers;     
}

function incrementPointers(&$pointers, &$arrLength) {
    for($i=0; $i<count($pointers); $i++) {
        $currentPointerIndex = count($pointers) - $i - 1;
        $currentPointer = $pointers[$currentPointerIndex];

        if($currentPointer < $arrLength - $i - 1) {
           ++$pointers[$currentPointerIndex];

           for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
                $pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
           }

           return true;
        }
    }

    return false;
}

function getDataByPointers(&$arr, &$pointers) {
    $data = [];

    for($i=0; $i<count($pointers); $i++) {
        $data[] = $arr[$pointers[$i]];
    }

    return $data;
}

function getCombinations($arr, $cnt)
{
    $len = count($arr);
    $result = [];
    $pointers = initializePointers($cnt);

    do {
        $result[] = getDataByPointers($arr, $pointers);
    } while(incrementPointers($pointers, count($arr)));

    return $result;
}

$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);

Basierend auf https://stackoverflow.com/a/127898/2628125 , jedoch abstrakter für Zeiger jeder Größe.

Alles, was hier gesagt und getan wurde, ist der O'caml-Code dafür. Der Algorithmus ist aus dem Code ersichtlich.

let combi n lst =
    let rec comb l c =
        if( List.length c = n) then [c] else
        match l with
        [] -> []
        | (h::t) -> (combi t (h::c))@(combi t c)
    in
        combi lst []
;;

Hier ist eine Methode, mit der Sie alle Kombinationen der angegebenen Größe aus einer Zeichenfolge mit zufälliger Länge erhalten. Ähnlich wie die Quinmars-Lösung, funktioniert jedoch für unterschiedliche Eingaben und k.

Der Code kann so geändert werden, dass er umbrochen wird, dh 'tupfen' von der Eingabe 'abcd' wk = 3.

public void run(String data, int howMany){
    choose(data, howMany, new StringBuffer(), 0);
}


//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
    if (result.length()==k){
        System.out.println(result.toString());
        return;
    }

    for (int i=startIndex; i<data.length(); i++){
        result.append(data.charAt(i));
        choose(data,k,result, i+1);
        result.setLength(result.length()-1);
    }
}

Ausgabe für "abcde":

abc abd abe acd ace ade bcd bce bde cde

Ich habe hierfür eine Lösung in SQL Server 2005 erstellt und auf meiner Website veröffentlicht: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Hier ist ein Beispiel, um die Verwendung zu zeigen:

SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')

Ergebnisse:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Hier ist mein Vorschlag in C ++

Ich habe versucht, den Iteratortyp so wenig wie möglich einzuschränken, sodass diese Lösung nur einen Vorwärtsiterator voraussetzt und ein const_iterator sein kann. Dies sollte mit jedem Standardcontainer funktionieren. In Fällen, in denen Argumente keinen Sinn ergeben, wird std :: invalid_argumnent ausgelöst

#include <vector>
#include <stdexcept>

template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
    if(begin == end && combination_size > 0u)
        throw std::invalid_argument("empty set and positive combination size!");
    std::vector<std::vector<Fci> > result; // empty set of combinations
    if(combination_size == 0u) return result; // there is exactly one combination of
                                              // size 0 - emty set
    std::vector<Fci> current_combination;
    current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
                                                        // in my vector to store
                                                        // the end sentinel there.
                                                        // The code is cleaner thanks to that
    for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
    {
        current_combination.push_back(begin); // Construction of the first combination
    }
    // Since I assume the itarators support only incrementing, I have to iterate over
    // the set to get its size, which is expensive. Here I had to itrate anyway to  
    // produce the first cobination, so I use the loop to also check the size.
    if(current_combination.size() < combination_size)
        throw std::invalid_argument("combination size > set size!");
    result.push_back(current_combination); // Store the first combination in the results set
    current_combination.push_back(end); // Here I add mentioned earlier sentinel to
                                        // simplyfy rest of the code. If I did it 
                                        // earlier, previous statement would get ugly.
    while(true)
    {
        unsigned int i = combination_size;
        Fci tmp;                            // Thanks to the sentinel I can find first
        do                                  // iterator to change, simply by scaning
        {                                   // from right to left and looking for the
            tmp = current_combination[--i]; // first "bubble". The fact, that it's 
            ++tmp;                          // a forward iterator makes it ugly but I
        }                                   // can't help it.
        while(i > 0u && tmp == current_combination[i + 1u]);

        // Here is probably my most obfuscated expression.
        // Loop above looks for a "bubble". If there is no "bubble", that means, that
        // current_combination is the last combination, Expression in the if statement
        // below evaluates to true and the function exits returning result.
        // If the "bubble" is found however, the ststement below has a sideeffect of 
        // incrementing the first iterator to the left of the "bubble".
        if(++current_combination[i] == current_combination[i + 1u])
            return result;
        // Rest of the code sets posiotons of the rest of the iterstors
        // (if there are any), that are to the right of the incremented one,
        // to form next combination

        while(++i < combination_size)
        {
            current_combination[i] = current_combination[i - 1u];
            ++current_combination[i];
        }
        // Below is the ugly side of using the sentinel. Well it had to haave some 
        // disadvantage. Try without it.
        result.push_back(std::vector<Fci>(current_combination.begin(),
                                          current_combination.end() - 1));
    }
}

Hier ist ein Code, den ich kürzlich in Java geschrieben habe und der die gesamte Kombination von "num" -Elementen aus "outOf" -Elementen berechnet und zurückgibt.

// author: Sourabh Bhat ([email protected])

public class Testing
{
    public static void main(String[] args)
    {

// Test case num = 5, outOf = 8.

        int num = 5;
        int outOf = 8;
        int[][] combinations = getCombinations(num, outOf);
        for (int i = 0; i < combinations.length; i++)
        {
            for (int j = 0; j < combinations[i].length; j++)
            {
                System.out.print(combinations[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static int[][] getCombinations(int num, int outOf)
    {
        int possibilities = get_nCr(outOf, num);
        int[][] combinations = new int[possibilities][num];
        int arrayPointer = 0;

        int[] counter = new int[num];

        for (int i = 0; i < num; i++)
        {
            counter[i] = i;
        }
        breakLoop: while (true)
        {
            // Initializing part
            for (int i = 1; i < num; i++)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i] = counter[i - 1] + 1;
            }

            // Testing part
            for (int i = 0; i < num; i++)
            {
                if (counter[i] < outOf)
                {
                    continue;
                } else
                {
                    break breakLoop;
                }
            }

            // Innermost part
            combinations[arrayPointer] = counter.clone();
            arrayPointer++;

            // Incrementing part
            counter[num - 1]++;
            for (int i = num - 1; i >= 1; i--)
            {
                if (counter[i] >= outOf - (num - 1 - i))
                    counter[i - 1]++;
            }
        }

        return combinations;
    }

    private static int get_nCr(int n, int r)
    {
        if(r > n)
        {
            throw new ArithmeticException("r is greater then n");
        }
        long numerator = 1;
        long denominator = 1;
        for (int i = n; i >= r + 1; i--)
        {
            numerator *= i;
        }
        for (int i = 2; i <= n - r; i++)
        {
            denominator *= i;
        }

        return (int) (numerator / denominator);
    }
}

Eine prägnante Javascript-Lösung:

Array.prototype.combine=function combine(k){    
    var toCombine=this;
    var last;
    function combi(n,comb){             
        var combs=[];
        for ( var x=0,y=comb.length;x<y;x++){
            for ( var l=0,m=toCombine.length;l<m;l++){      
                combs.push(comb[x]+toCombine[l]);           
            }
        }
        if (n<k-1){
            n++;
            combi(n,combs);
        } else{last=combs;}
    }
    combi(1,toCombine);
    return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);

Algorithmus:

• Zähle von 1 bis 2 ^ n.
• Konvertieren Sie jede Ziffer in ihre Binärdarstellung.
• Übersetzen Sie jedes Ein-Bit basierend auf der Position in Elemente Ihres Satzes.

In C #:

void Main()
{
    var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };

    var kElement = 2;

    for(var i = 1; i < Math.Pow(2, set.Length); i++) {
        var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
        var cnt = Regex.Matches(Regex.Escape(result),  "1").Count; 
        if (cnt == kElement) {
            for(int j = 0; j < set.Length; j++)
                if ( Char.GetNumericValue(result[j]) == 1)
                    Console.Write(set[j]);
            Console.WriteLine();
        }
    }
}

Warum funktioniert es?

Es gibt eine Bijektion zwischen den Teilmengen einer n-Elementmenge und n-Bit-Sequenzen.

Das heißt, wir können herausfinden, wie viele Teilmengen es gibt, indem wir Sequenzen zählen.

Beispielsweise können die folgenden vier Elemente durch {0,1} X {0, 1} X {0, 1} X {0, 1} (oder 2 ^ 4) verschiedene Sequenzen dargestellt werden.

Also müssen wir nur von 1 bis 2 ^ n zählen, um alle Kombinationen zu finden.(Wir ignorieren die leere Menge.) Als nächstes übersetzen Sie die Ziffern in ihre binäre Darstellung. Ersetzen Sie dann 'on'-Bits durch Elemente Ihres Sets.

Wenn Sie nur k Elementergebnisse wünschen, drucken Sie nur, wenn k Bits aktiviert sind.

(Wenn Sie alle Teilmengen anstelle von Teilmengen mit k Länge möchten, entfernen Sie den Teil cnt / kElement.)

(Zum Beweis siehe MIT kostenlose Kursunterlagen Mathematik für Informatik, Lehman et al., Abschnitt 11.2.2. Https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- für-Informatik-Herbst-2010 / Lesungen / )

kurzer Python-Code, der Indexpositionen ergibt

def yield_combos(n,k):
    # n is set size, k is combo size

    i = 0
    a = [0]*k

    while i > -1:
        for j in range(i+1, k):
            a[j] = a[j-1]+1
        i=j
        yield a
        while a[i] == i + n - k:
            i -= 1
        a[i] += 1

Ich habe eine Klasse geschrieben, die allgemeine Funktionen für die Arbeit mit dem Binomialkoeffizienten behandelt. Dies ist die Art von Problem, unter die Ihr Problem fällt. Es führt die folgenden Aufgaben aus:

1. Gibt alle K-Indizes in einem schönen Format für jedes N aus. Wählen Sie K in eine Datei. Die K-Indizes können durch aussagekräftigere Zeichenfolgen oder Buchstaben ersetzt werden. Diese Methode macht die Lösung dieser Art von Problem ziemlich trivial.

2. Konvertiert die K-Indizes in den richtigen Index eines Eintrags in der sortierten Binomialkoeffiziententabelle. Diese Technik ist viel schneller als ältere veröffentlichte Techniken, die auf Iteration beruhen. Dazu wird eine mathematische Eigenschaft verwendet, die Pascals Dreieck innewohnt. Mein Papier spricht darüber. Ich glaube, ich bin der erste, der diese Technik entdeckt und veröffentlicht, aber ich könnte mich irren.

3. Konvertiert den Index in einer sortierten Binomialkoeffiziententabelle in die entsprechenden K-Indizes.

4. Verwendet die Mark Dominus- Methode zur Berechnung des Binomialkoeffizienten, der viel weniger wahrscheinlich überläuft und mit größeren Zahlen arbeitet.

5. Die Klasse ist in .NET C # geschrieben und bietet eine Möglichkeit, die mit dem Problem verbundenen Objekte (falls vorhanden) mithilfe einer generischen Liste zu verwalten. Der Konstruktor dieser Klasse verwendet einen Bool-Wert namens InitTable, der bei true eine generische Liste für die zu verwaltenden Objekte erstellt. Wenn dieser Wert falsch ist, wird die Tabelle nicht erstellt. Die Tabelle muss nicht erstellt werden, um die 4 oben genannten Methoden auszuführen. Für den Zugriff auf die Tabelle werden Zugriffsmethoden bereitgestellt.

6. Es gibt eine zugehörige Testklasse, die zeigt, wie die Klasse und ihre Methoden verwendet werden. Es wurde ausgiebig mit 2 Fällen getestet und es sind keine Fehler bekannt.

Informationen zu dieser Klasse und zum Herunterladen des Codes finden Sie unter Tablizing The Binomial Coeffieicent .

Es sollte nicht schwer sein, diese Klasse in C ++ zu konvertieren.