Algorithmus zurückzukehren alle Kombinationen von k Elementen von n

https://stackoverflow.com/questions/127704

02-07-2019
|

Frage

Ich mag eine Funktion schreiben, die auszuwählen, die eine Reihe von Buchstaben als Argument und eine Anzahl von diesen Buchstaben nehmen.

Angenommen, Sie ein Array von 8 Buchstaben bieten und wollen 3 Buchstaben zur Auswahl, dass. Dann sollten Sie:

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

Arrays (oder Worte) im Gegenzug der aus 3 Buchstaben jeweils.

Lösung

Art of Computer Programming Volume 4: Faszikel 3 hat eine Tonne von diesen, dass Ihre Situation passen könnte besser als wie ich beschreiben.

Gray-Codes

Ein Problem, das Sie stoßen wird, ist natürlich Speicher und ziemlich schnell, Sie haben Probleme, die durch 20 Elemente in Ihrem Set - ²⁰ C ₃ = 1140 . Und wenn Sie den Satz iterieren wollen dann ist es am besten, einen modifizierten gray-Code-Algorithmus zu verwenden, so dass Sie nicht alle von ihnen in Erinnerung halten. Diese erzeugen die nächste Kombination aus dem vorherigen und zur Vermeidung von Wiederholungen. Es gibt viele von diesen für unterschiedliche Verwendungszwecke. Wollen wir die Unterschiede zwischen aufeinander folgenden Kombinationen maximieren? minimieren? und so weiter.

Einige der ursprünglichen Papiere beschreiben Gray-Codes:

Hier sind einige andere Papiere das Thema bedeckt:

eine effiziente Implementierung des Eades, Hickey, lesen Adjacent Interchange Kombination Erzeugungsalgorithmus (PDF, mit dem Code in Pascal)
Kombinationsgeneratoren
Survey of Combinatorial Gray-Codes (Postscript)
Ein Algorithmus für Gray-Codes

Chase Twiddle (Algorithmus)

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

Der Algorithmus in C ...

Index-Kombinationen in lexikographische Ordnung (Buckles Algorithmus 515)

Sie können auch eine Kombination von seinem Index (in lexikographischer Reihenfolge) verweisen. Die Erkenntnis, dass der Index von rechts ein gewisses Maß an Veränderung auf dem Index basiert gelassen werden sollten wir etwas bauen können, die eine Kombination erholen sollte.

, wir haben eine Menge {1,2,3,4,5,6} ... und wir wollen drei Elemente. Lassen Sie uns sagen {1,2,3} können wir sagen, dass der Unterschied zwischen den Elementen ein und um und minimal. {1,2,4} hat eine Änderung und lexikographisch Nummer 2. Also die Zahl der ‚Änderungen‘ in den letzten Platz Konten für eine Änderung der lexikographischen Ordnung. Der zweite Platz, mit einer Änderung {1,3,4} hat eine Änderung aber macht mehr ändern, da es an zweiter Stelle (nach der Anzahl der Elemente in der ursprünglichen Menge proportional) ist.

Die Methode, die ich beschrieben habe, ist eine Dekonstruktion, wie es aus der Menge auf den Index scheint, müssen wir das Gegenteil tun - was viel schwieriger ist. Dies ist, wie Buckles das Problem löst. Ich schrieb einige C zu berechnen, sie , mit geringfügigen Änderungen - ich benutzte den Index der Sätze, anstatt einen Nummernbereich um das Set zu repräsentieren, so arbeiten wir immer von 0 ... n. Hinweis:

Da Kombinationen sind ungeordnet, {1,3,2} = {1,2,3} --wir bestellen sie lexikographischer sein.
Diese Methode hat eine implizites 0 den Satz für den ersten Unterschied zu starten.

Index-Kombinationen in lexikographischer Order (McCaffrey)

Es gibt eine andere Art und Weise: , ist ihr Konzept leichter zu erfassen und Programm, aber es ist, ohne dass die Optimierungen von Schnallen. Glücklicherweise ist es produziert auch keine doppelten Kombinationen:

Der Satz die , wo .

Ein Beispiel: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). So ist die 27.e lexikographische Kombination von vier Dingen: {1,2,5,6}, das sind die Indizes an welchen Geräten Sie wollen, zu betrachten. Beispiel unten (OCaml), erfordert choose Funktion, links für den 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)

Eine kleine und einfache Kombinationen iterator

Die folgenden beiden Algorithmen sind für didaktische Zwecke zur Verfügung gestellt. Sie setzen einen Iterator und (eine allgemeinere) Ordner Gesamt Kombinationen. Sie sind so schnell wie möglich, um die Komplexität O mit (ⁿ C _k). Der Speicherverbrauch wird durch k gebunden.

Wir werden mit dem Iterator beginnen, die es einem Benutzer bereitgestellte Funktion für jede Kombination nennen

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 wird die Benutzer bereitgestellte Funktion zusammen mit den Zustandsvariablen nennt, von dem Anfangszustand beginnen. Da wir den Zustand zwischen verschiedenen Zuständen passieren müssen wir nutzen das nicht for-Schleife, sondern stattdessen verwenden 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

Andere Tipps

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

Verbrauch:

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

Ergebnis:

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

[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 vorstellen für dieses Problem meiner rekursive Python-Lösung?

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 Nutzung:

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

Ich mag es für seine Einfachheit.

Lassen Sie uns sagen Sie Ihre Array von Buchstaben wie folgt aussieht: „ABCDEFGH“. Sie haben drei Indizes (i, j, k) anzeigt, welche Buchstaben Sie für das aktuelle Wort zu verwenden, führen Sie beginnen mit:

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

Zuerst variieren Sie k, so ist der nächste Schritt sieht so aus:

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

Wenn Sie das Ende Sie gehen erreicht und j variieren 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

Wenn Sie j G erreicht beginnen Sie auch i zu verändern.

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

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

Written in Code diesen Look so etwas

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 rekursiven Algorithmus nimmt alle der k-Elementkombinationen aus einem geordneten Satz:

Wählen Sie das erste Element i Ihrer Kombination
kombinieren i mit jeder der Kombinationen von k-1 Elemente rekursiv aus der Menge der Elemente größer als i gewählt.

Iterate die oben für jede i im Satz.

Es ist wichtig, dass Sie den Rest der Elemente als größer als i holen, um Wiederholungen zu vermeiden. Auf diese Weise [3,5] wird nur einmal aufgenommen werden, wie [3] zusammen mit [5], statt zweimal (der Bedingung beseitigt [5] + [3]). Ohne diese Bedingung erhalten Sie Variationen statt Kombinationen.

Ich fand dieses Thema nützlich und dachte, ich würde eine Javascript-Lösung hinzufügen, die Sie in Firebug Pop können. Je nach Ihrem JS Motor, könnte es eine wenig Zeit in Anspruch nehmen, wenn der Start Zeichenfolge 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

In C ++ die folgende Routine wird alle Kombinationen des Längenabstandes (ersten, k) zwischen dem Bereich erzeugt [first, liest):

#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 wie folgt 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;
}

Dies druckt die folgende:

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

Kurz 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 der rekursiven Methode wird mit dem folgenden Beispiel beschrieben:

Beispiel: A B C D E
Alle Kombinationen von 3 wäre:

A mit allen Kombinationen von 2 von dem Rest (B C D E)
B mit allen Kombinationen von zwei aus dem Rest (C D E)
C mit allen Kombinationen von 2 vom Rest (D E)

Einfacher rekursiven 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, das heißt die Auswahl Null-Elemente. Es erzeugt ein einzelnes Ergebnis, die eine leere Liste (das heißt eine Liste, die eine leere Liste enthält).

Für n> 0, x geht durch jedes Element der Liste und xs ist jedes Element nach x.

rest nimmt n - 1 Elemente aus xs einen rekursiven Aufruf mit combinations. Das endgültige Ergebnis der Funktion ist eine Liste, wobei jedes Element x : rest (d.h. eine Liste, die als Leiter und als x tail rest hat) für jeden unterschiedlichen Wert von x und rest.

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

Und natürlich, da Haskell faul ist, wird die Liste nach und nach je nach Bedarf erzeugt, so dass man teilweise exponentiell große Kombinationen auswerten kann.

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

Und hier kommt Urvater COBOL, die viel geschmähte Sprache.

Nehmen wir eine Reihe von Elementen 34 von 8 Byte annehmen jeweils (rein willkürliche Auswahl). Die Idee, alle möglichen 4-Elementkombinationen aufzuzählen ist und sie in einem Array laden.

Wir verwenden vier Indizes, jeweils eine 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 jede idx4 erhalten wir eine einzigartige Kombination von Gruppen zu je vier. Wenn idx4 an das Ende des Arrays kommt, inkrementieren wir IDX3 um 1 und eingestellt idx4 zu IDX3 + 1. Dann laufen wir wieder bis zum Ende idx4. Wir gehen auf diese Weise vermehren IDX3, idx2 und idx1 jeweils bis die Position des idx1 weniger als 4 von dem Ende des Arrays. Das beendet den Algorithmus.

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

Erste Iterationen:

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 beschrieben auf 99 Scala Probleme .

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 SQL-Syntax verwenden können - sagen, wenn Sie LINQ verwenden eine Struktur oder Array zuzugreifen Feldern oder direkt Zugriff auf eine Datenbank, die eine Tabelle „Alphabet“ mit nur einem Zeichen Feld „Letter“ Sie angerufen hat, anpassen können folgenden 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

Damit wird alle Kombinationen von 3 Buchstaben zurückkehren, ungeachtet, wie viele Buchstaben Sie in der Tabelle "Alphabet" (es 3 sein kann, 8, 10, 27, usw.).

Wenn das, was Sie wollen, ist alle Permutationen, anstatt Kombinationen (dh Sie wollen „ACB“ und „ABC“, wie verschieden zu zählen, und nicht nur einmal vorhanden sein) löschen Sie einfach die letzte Zeile (das AND eins) und es ist getan.

Post-Edit: Nachdem die Frage erneut zu lesen, wird mir klar, was gebraucht wird ist die allgemeine Algorithmus, nicht nur ein spezifischer für den Fall von 3 Artikeln auswählen. Adam Hughes' Antwort ist vollständig, leider kann ich es nicht vote up (noch) nicht. Diese Antwort ist einfach, aber funktioniert nur, wenn Sie wollen genau 3 Artikel.

Ein anderer C # -Version mit Lazy Generation der Kombination Indizes. Diese Version enthält eine einzelne Anordnung von Indizes unterhält eine Abbildung zwischen der Liste aller Werte und die Werte für die aktuelle Kombination zu definieren, das heißt ständig verwendet O (k) zusätzlichen Raum während der gesamten Laufzeit. Der Code erzeugt individuelle 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

Hier haben Sie eine faule ausgewertete Version dieses Algorithmus in C # codieren:

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

Hope diese Hilfe Sie!

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

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 Kombination haben Sie ohne Wiederholung benötigen, brauchen Sie es?

Es ist ein Generator, so dass Sie verwenden es in etwa so aus:

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

https://gist.github.com/3118596

Es ist eine Implementierung für JavaScript. Es verfügt über Funktionen k-Kombinationen und alle Kombinationen eines Arrays von 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]]

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

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

Zuerst variieren Sie k, so ist der nächste Schritt sieht so aus:

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

Wenn Sie das Ende Sie gehen erreicht und j variieren 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

Wenn Sie j G erreicht beginnen Sie auch i zu verändern.

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

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

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 , aber mehr abstrakt, für jede Größe von Zeigern.

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

Hier ist ein Beispiel des Verbrauches 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, so wenig Beschränkung des Iteratortyp zu verhängen, wie ich könnte so dass diese Lösung nur vorwärts Iterator geht davon aus, und es kann ein const_iterator sein. Dies sollte mit jedem Standard-Container arbeiten. In Fällen, in denen Argumente keinen Sinn machen es wirft std :: invalid_argumnent

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

Alle gesagt und und hier kommt der O'Caml Code für das getan. Algorithmus ergibt sich aus dem Code ..

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 ein Code, den ich vor kurzem in Java geschrieben, die berechnet und gibt alle die Kombination von „num“ Elemente von „OUTOF“ Elemente.

// author: Sourabh Bhat (heySourabh@gmail.com)

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

Hier ist eine Methode, mit der Sie alle Kombinationen von bestimmten Größe aus einer zufälligen Zeichenfolge gibt. Ähnlich wie quinmars' Lösung, sondern arbeitet für verschiedene Ein- und k.

Der Code kann geändert werden, herum zu wickeln, das heißt 'dab' von Eingang 'abcd' w k = 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 aber acd ace ade bcd BCE bde cde

Ich habe eine Klasse geschrieben gemeinsame Funktionen zu handhaben, um mit dem Binomialkoeffizienten arbeiten, die die Art des Problems ist, dass Ihr Problem unter fällt. Es führt die folgenden Aufgaben:

Gibt alle K-Indizes in einem praktischen Format für jede N K in eine Datei wählen. Der K-Indizes kann mit mehr beschreibenden Strings oder Buchstaben ersetzt werden. Dieses Verfahren macht diese Art von Problem ganz trivial zu lösen.
Wandelt die K-Indizes in den richtigen Index eines Eintrags in der sortierten Binomialkoeffizient Tabelle. Diese Technik ist viel schneller als ältere veröffentlichten Techniken, die auf Iteration verlassen. Es tut dies durch eine mathematische Eigenschaft inhärent Pascals Dreieck verwenden. Mein Papier spricht darüber. Ich glaube, ich bin die erste zu entdecken und diese Technik zu veröffentlichen, aber ich könnte falsch sein.
Wandelt den Index in einer sortierten Binomialkoeffizient Tabelle zu den entsprechenden K-Indizes.
Mark Dominus Verfahren den Binomialkoeffizient zu berechnen, die viel weniger wahrscheinlich zu überlaufen und arbeitet mit einer größeren Anzahl.
Die Klasse ist in .NET C # geschrieben und bietet eine Möglichkeit, die Objekte für das Problem (falls vorhanden) unter Verwendung einer generische Liste mit Bezug zu verwalten. Der Konstruktor dieser Klasse nimmt einen Bool-Wert namens InitTable, dass, wenn true, um eine generische Liste erstellen wird, die Objekte zu halten verwaltet werden. Wenn dieser Wert falsch ist, dann wird es nicht in die Tabelle erstellen. Die Tabelle muss nicht in Reihenfolge erstellt werden, um die obigen Verfahren 4 durchzuführen. Accessormethoden sind vorgesehen, um die Tabelle zugreifen.
Es gibt eine zugehörige Testklasse, die zeigt, wie die Klasse und ihre Methoden verwenden. Es wurde mit 2 Fällen ausgiebig getestet und es gibt keine bekannten Fehler.

über diese Klasse zu lesen und den Code herunterzuladen, finden Sie unter Tablizing Binomialmodelle Coeffieicent .

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

Algorithmus:

Count von 1 bis 2 ^ n.
Konvertieren jede Ziffer in seine binäre Darstellung.
Übersetzen jeder 'auf' Bit auf Elemente des Sets, basierend auf Position.

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 eines n-Menge und n-Bit-Sequenzen.

Das bedeutet, dass wir herausfinden, wie viele Untergruppen gibt es von Sequenzen zu zählen.

z. B., das Element vier nachstehenden kann dargestellt werden durch {0,1} x {0, 1} x {0, 1} x {0, 1} (oder 2 ^ 4) verschiedene Sequenzen.

So - alles, was wir tun müssen, ist von 1 bis 2 ^ n zählt alle Kombinationen finden (Wir ignorieren die leere Menge.) Als nächstes wird die Anzeige auf die binäre Darstellung übersetzen.. Dann Elemente des Satzes ersetzen für ‚auf‘ Bits.

Wenn Sie nur k Element Ergebnisse wollen, drucken Sie nur, wenn k Bits ‚auf‘.

(Wenn Sie alle Untergruppen statt k Länge Subsets möchten, entfernen Sie die cnt / Kelement Teil.)

(Zum Beweis siehe MIT frei Kurs Mathematik für Informatik, Lehman et al, Abschnitt 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/ 6-042j-Mathematik-for-Computer-Wissenschaft-fall-2010 / Lesungen / )

Springen auf den fahrenden Zug, und eine andere Lösung zu veröffentlichen. Dies ist eine generische Java-Implementierung. Input: (int k) ist die Anzahl der Elemente zu wählen und (List<T> list) die Liste zur Auswahl. Gibt eine Liste von Kombinationen (List<List<T>>).

public static <T> List<List<T>> getCombinations(int k, List<T> list) {
    List<List<T>> combinations = new ArrayList<List<T>>();
    if (k == 0) {
        combinations.add(new ArrayList<T>());
        return combinations;
    }
    for (int i = 0; i < list.size(); i++) {
        T element = list.get(i);
        List<T> rest = getSublist(list, i+1);
        for (List<T> previous : getCombinations(k-1, rest)) {
            previous.add(element);
            combinations.add(previous);
        }
    }
    return combinations;
}

public static <T> List<T> getSublist(List<T> list, int i) {
    List<T> sublist = new ArrayList<T>();
    for (int j = i; j < list.size(); j++) {
        sublist.add(list.get(j));
    }
    return sublist;
}

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow