Algorithmus, um alle Kombinationen von k Elementen aus n zurückzugeben

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

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

Verwendungsbeispiel:

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

Ich mag es wegen seiner Einfachheit.

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]

Nehmen wir an, Ihr Buchstabenfeld 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 
 ^ ^ ^ 
 I j k 

Zuerst variieren Sie k, so dass der nächste Schritt so aussieht:

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

Wenn Sie das Ende erreicht haben, gehen Sie weiter und variieren j und dann wieder k.

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

 A B C D E FG H.

Sobald Sie j 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 
...

Geschrieben im Code sieht das 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 i Ihrer Kombination aus
• kombiniere i mit jeder der Kombinationen von k-1-Elementen, die rekursiv aus der Menge der Elemente ausgewählt werden, die größer als i sind.

Wiederholen Sie das obige für jede i im Set.

Es ist wichtig, dass Sie die restlichen Elemente als größer als i auswählen, um Wiederholungen zu vermeiden. Auf diese Weise wird [3,5] nur einmal ausgewählt, und zwar als [3] in Kombination mit [5] anstelle von zweimal (die Bedingung beseitigt [5] + [3]). Ohne diese Bedingung erhalten Sie Variationen statt Kombinationen.

Ich fand diesen Thread nützlich und dachte, ich würde eine Javascript-Lösung hinzufügen, die Sie in Firebug einblenden können. Je nach JS-Engine kann es etwas 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 aussehen:

abc
ab
ac
a
bc
b
c

In C++ führt die folgende Routine alle Kombinationen der Längenentfernung (first, k) zwischen dem Bereich [first, last)] aus

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

Dadurch wird Folgendes gedruckt:

123
124
125
134
135
145
234
235
245
345

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: A B C D E
Alle Kombinationen von 3 wären:

• A mit allen Kombinationen von 2 vom Rest (B C D E)
• B mit allen Kombinationen von 2 vom Rest (C D E)
• C mit allen Kombinationen von 2 vom Rest (D E)

Ein 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 zuerst den Sonderfall, d. H. Das Auswählen von Nullelementen. Es erzeugt ein einzelnes Ergebnis, dh eine leere Liste (d. H. Eine Liste, die eine leere Liste enthält).

Für n> 0 durchläuft x jedes Element der Liste und xs ist jedes Element nach x.

rest wählt n - 1 Elemente aus xs mit einem rekursiven Aufruf von combinations aus. Das Endergebnis der Funktion ist eine Liste, in der jedes Element x : rest ist (d. H. Eine Liste, die x als Kopf und rest als Ende hat) für jeden unterschiedlichen Wert von x und rest.

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

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

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

Und hier kommt Opa COBOL, die viel verschmutzte Sprache.

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

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

Das Array wird folgendermaßen verarbeitet:

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

Wir ändern idx4 von 4 bis zum Ende. Für jedes idx4 erhalten wir eine einzigartige Kombination von Gruppen von vier. Wenn idx4 das Ende des Arrays erreicht, erhöhen wir idx3 um 1 und setzen idx4 auf idx3 + 1. Dann lassen wir idx4 wieder bis zum Ende laufen. Wir gehen auf diese Weise vor und erweitern idx3, idx2 und idx1, bis die Position von idx1 vom Ende des Arrays kleiner als 4 ist. 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 auf 99 Scala Problems beschrieben.

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case [email protected](_ :: 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, beispielsweise, wenn Sie LINQ verwenden, um auf Felder einer Struktur oder eines Arrays zuzugreifen, oder direkt auf eine Datenbank zugreifen, die eine Tabelle mit dem Namen "Alphabet" mit nur einem Zeichenfeld "Letter" enthält, 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

Dadurch werden alle Kombinationen von 3 Buchstaben zurückgegeben, unabhängig davon, wie viele Buchstaben Sie in der Tabelle "Alphabet" haben (es können 3, 8, 10, 27 usw. sein).

Wenn Sie möchten, sind alle Permutationen und nicht die Kombinationen (d. H. Sie möchten, dass "ACB" und "ABC" als unterschiedlich gezählt werden und nicht nur einmal angezeigt werden). Löschen Sie einfach die letzte Zeile (die AND-Zeile) und fertig.

Post-Edit: Nachdem ich die Frage nochmals gelesen habe, ist mir klar, dass der Algorithmus general nicht nur ein spezieller Algorithmus für die Auswahl von 3 Elementen ist. Die Antwort von Adam Hughes ist die vollständige, leider kann ich sie (noch) nicht wählen. Diese Antwort ist einfach, funktioniert jedoch nur, wenn Sie genau 3 Elemente wünschen.

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

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

Ob 

n<len(l) 

sie sollten alle Kombinationen haben, die Sie ohne Wiederholung benötigen. Brauchen Sie sie?

Es ist ein Generator, also benutzt man es in etwa wie folgt:

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

Hier haben Sie eine faul bewertete Version dieses Algorithmus, die in C # codiert ist:

    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 test teil:

    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!

Eine weitere C # -Version mit fauler 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 sie verwendet während der gesamten Zeit ständig O(k) zusätzlichen Platz Laufzeit. Der Code generiert individuelle Kombinationen, einschließlich der ersten, in O(k) time.

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

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

https://Gist.github.com/3118596

Es gibt eine Implementierung für JavaScript. Es hat Funktionen, um K-Kombinationen und alle Kombinationen eines Arrays beliebiger Objekte 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]]

Nehmen wir an, Ihr Buchstabenfeld 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 
 ^ ^ ^ 
 I j k 

Zuerst variieren Sie k, so dass der nächste Schritt so aussieht:

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

Wenn Sie das Ende erreicht haben, gehen Sie weiter und variieren j und dann wieder k.

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

 A B C D E FG H.

Sobald Sie j 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 
...

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 alle Zeigergrößen.

Hier ist eine Methode, die alle Kombinationen der angegebenen Größe aus einer zufälligen Zeichenfolge ergibt. Ähnlich wie die Lösung von Quinmars, funktioniert aber für unterschiedliche Eingabe und k.

Der Code kann so geändert werden, dass er von der Eingabe 'abcd' w k = 3 umgeschrieben wird.

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

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

Hier ist ein Code, den ich kürzlich in Java geschrieben habe, der alle Kombinationen 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);
    }
}

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

Hier ist ein Beispiel für die Verwendung:

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

ergebnisse:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Alles gesagt und getan, hier kommt der O'caml-Code für den Algorithmus. 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 mein Vorschlag in C++

Ich habe versucht, den Iterator-Typ so wenig wie möglich einzuschränken, so dass diese Lösung nur einen Iterator für die Weiterleitung voraussetzt. 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));
    }
}

Algorithmus:

• Zähle von 1 bis 2 ^ n.
• Wandeln Sie jede Ziffer in ihre binäre Darstellung um.
• Übersetzen Sie jedes Ein-Bit auf Elemente Ihres Satzes, basierend auf der 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?

Zwischen den Teilmengen eines Satzes aus n Elementen und n-Bit-Sequenzen besteht ein Schnitt.

Das heißt, wir können durch Zählen von Sequenzen herausfinden, wie viele Teilmengen es gibt. 

zum Beispiel kann der vier-Element-Satz unten durch {0,1} X {0, 1} X {0, 1} X {0, 1} (oder 2 ^ 4) verschiedene Sequenzen dargestellt werden.

Also - wir müssen 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 die Elemente Ihres Sets durch Ein-Bits.

Wenn Sie nur Ergebnisse mit k Elementen wünschen, drucken Sie nur, wenn k Bits "Ein" sind. 

(Wenn Sie alle Subsets anstelle von k-Length-Subsets verwenden möchten, entfernen Sie den Part cnt/kElement.) 

(Zum Beweis siehe MIT kostenlose Kurse für 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-science-fall-2010/lesungen/ )

Ich habe eine Klasse geschrieben, um allgemeine Funktionen für das Arbeiten mit dem Binomialkoeffizienten zu behandeln. Hierbei handelt es sich um die Art von Problem, unter das Ihr Problem fällt. Es führt die folgenden Aufgaben aus:

1. Gibt alle K-Indizes in einem Nice-Format aus, und wählen Sie N in eine Datei. Die K-Indizes können durch aussagekräftigere Zeichenketten oder Buchstaben ersetzt werden. Diese Methode macht das Lösen 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 dem Pascalschen Dreieck innewohnt. Mein Papier spricht darüber. Ich glaube, ich bin der Erste, der diese Technik entdeckt und veröffentlicht hat, aber ich könnte mich irren.

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

4. Verwendet die Methode Mark Dominus zur Berechnung des Binomialkoeffizienten, bei dem die Wahrscheinlichkeit eines Überlaufs geringer ist und mit größeren Zahlen gearbeitet wird.

5. Die Klasse ist in .NET C # geschrieben und bietet eine Möglichkeit, die mit dem Problem in Zusammenhang stehenden Objekte (sofern vorhanden) mithilfe einer generischen Liste zu verwalten. Der Konstruktor dieser Klasse benötigt einen bool-Wert namens InitTable, der bei true eine generische Liste für die zu verwaltenden Objekte erstellt. Wenn dieser Wert "false" ist, wird die Tabelle nicht erstellt. Die Tabelle muss nicht erstellt werden, um die 4 oben genannten Methoden auszuführen. Es werden Zugriffsmethoden bereitgestellt, um auf die Tabelle zuzugreifen.

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

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

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

Ich habe nach einer ähnlichen Lösung für PHP gesucht und bin auf Folgendes gestoßen

class Combinations implements Iterator
{
    protected $c = null;
    protected $s = null;
    protected $n = 0;
    protected $k = 0;
    protected $pos = 0;

    function __construct($s, $k) {
        if(is_array($s)) {
            $this->s = array_values($s);
            $this->n = count($this->s);
        } else {
            $this->s = (string) $s;
            $this->n = strlen($this->s);
        }
        $this->k = $k;
        $this->rewind();
    }
    function key() {
        return $this->pos;
    }
    function current() {
        $r = array();
        for($i = 0; $i < $this->k; $i++)
            $r[] = $this->s[$this->c[$i]];
        return is_array($this->s) ? $r : implode('', $r);
    }
    function next() {
        if($this->_next())
            $this->pos++;
        else
            $this->pos = -1;
    }
    function rewind() {
        $this->c = range(0, $this->k);
        $this->pos = 0;
    }
    function valid() {
        return $this->pos >= 0;
    }

    protected function _next() {
        $i = $this->k - 1;
        while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)
            $i--;
        if($i < 0)
            return false;
        $this->c[$i]++;
        while($i++ < $this->k - 1)
            $this->c[$i] = $this->c[$i - 1] + 1;
        return true;
    }
}


foreach(new Combinations("1234567", 5) as $substring)
    echo $substring, ' ';

Quelle

Ich weiß nicht, wie effizient die Klasse ist, aber ich habe sie nur für eine Sämaschine verwendet.

Ein LISP-Makro generiert den Code für alle Werte r (einmal genommen)

(defmacro txaat (some-list taken-at-a-time)
  (let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
    `(
      ,@(loop for i below taken-at-a-time 
           for j in vars 
           with nested = nil 
           finally (return nested) 
           do
             (setf 
              nested 
              `(loop for ,j from
                    ,(if (< i (1- (length vars)))
                         `(1+ ,(nth (1+ i) vars))
                         0)
                  below (- (length ,some-list) ,i)
                    ,@(if (equal i 0) 
                          `(collect 
                               (list
                                ,@(loop for k from (1- taken-at-a-time) downto 0
                                     append `((nth ,(nth k vars) ,some-list)))))
                          `(append ,nested))))))))

So,

CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
    COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
                   COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
      APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
                   APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
                                COLLECT (LIST (NTH A '(A B C D))
                                              (NTH B '(A B C D))
                                              (NTH C '(A B C D))))))
T

CL-USER> 

Und,

CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER> 

Kurzer PHP-Algorithmus, um alle Kombinationen von k Elementen aus n (Binomialkoeffizienten) basierend auf einer Java-Lösung zurückzugeben:

$array = array(1,2,3,4,5);

$array_result = NULL;

$array_general = NULL;

function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
    if($len == 0)
    {
        $general_array[] = $result_array;
        return;
    }

    for ($i = $start_position; $i <= count($array) - $len; $i++)
    {
        $result_array[$result_len - $len] = $array[$i];
        combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
    }
} 

combinations($array, 3, 0, $array_result, 3, $array_general);

echo "<pre>";
print_r($array_general);
echo "</pre>";

Die gleiche Lösung aber in Javascript:

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];

function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
    if(len === 0) {
        var tempArray = [];
        resultArray.forEach(value => tempArray.Push(value));
        arrayGeneral.Push(tempArray);
        return;
    }
    for (var i = startPosition; i <= newArray.length - len; i++) {
        resultArray[resultLen - len] = newArray[i];
        combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
    }
} 

combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);

console.log(arrayGeneral);

Hier ist meine Scala-Lösung :

def combinations[A](s: List[A], k: Int): List[List[A]] = 
  if (k > s.length) Nil
  else if (k == 1) s.map(List(_))
  else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)

Dies ist ein rekursives Programm, das Kombinationen für nCk.Elements in der Sammlung generiert, wobei angenommen wird, dass es von 1 bis n verläuft

#include<stdio.h>
#include<stdlib.h>

int nCk(int n,int loopno,int ini,int *a,int k)
{
    static int count=0;
    int i;
    loopno--;
    if(loopno<0)
    {
        a[k-1]=ini;
        for(i=0;i<k;i++)
        {
            printf("%d,",a[i]);
        }
        printf("\n");
        count++;
        return 0;
    }
    for(i=ini;i<=n-loopno-1;i++)
    {
        a[k-1-loopno]=i+1;
        nCk(n,loopno,i+1,a,k);
    }
    if(ini==0)
    return count;
    else
    return 0;
}

void main()
{
    int n,k,*a,count;
    printf("Enter the value of n and k\n");
    scanf("%d %d",&n,&k);
    a=(int*)malloc(k*sizeof(int));
    count=nCk(n,k,0,a,k);
    printf("No of combinations=%d\n",count);
}

JavaScript, generatorbasierter, rekursiver Ansatz:

function *nCk(n,k){
  for(var i=n-1;i>=k-1;--i)
    if(k===1)
      yield [i];
    else
      for(var temp of nCk(i,k-1)){
        temp.unshift(i);
        yield temp;
      }
}

function test(){
  try{
    var n=parseInt(ninp.value);
    var k=parseInt(kinp.value);
    log.innerText="";
    var stop=Date.now()+1000;
    if(k>=1)
      for(var res of nCk(n,k))
        if(Date.now()<stop)
          log.innerText+=JSON.stringify(res)+" ";
        else{
          log.innerText+="1 second passed, stopping here.";
          break;
        }
  }catch(ex){}
}

n:<input id="ninp" oninput="test()">
&gt;= k:<input id="kinp" oninput="test()"> &gt;= 1
<div id="log"></div>

Auf diese Weise (durch Verringern von i und unshift()) werden Kombinationen und Elemente innerhalb von Kombinationen in absteigender Reihenfolge erzeugt, was das Auge ein wenig erfreut.
Der Test stoppt nach 1 Sekunde, sodass die Eingabe seltsamer Zahlen relativ sicher ist.

In VB.Net erfasst dieser Algorithmus alle Kombinationen von n Zahlen aus einer Menge von Zahlen (PoolArray). z.B. alle Kombinationen von 5 Plektren von "8,10,20,33,41,44,47".

Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
    If PicksIndex < PicksArray.Length Then
        For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
            PicksArray(PicksIndex) = PoolArray(i)
            CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
        Next
    Else
        ' completed combination. build your collections using PicksArray.
    End If
End Sub

        Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
        Dim nPicks as UInteger = 5
        Dim Picks(nPicks - 1) As UInteger
        CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)

Und hier ist eine Clojure -Version, die denselben Algorithmus verwendet, den ich in meiner OCaml -Implementierungsantwort beschrieben habe:

(defn select
  ([items]
     (select items 0 (inc (count items))))
  ([items n1 n2]
     (reduce concat
             (map #(select % items)
                  (range n1 (inc n2)))))
  ([n items]
     (let [
           lmul (fn [a list-of-lists-of-bs]
                     (map #(cons a %) list-of-lists-of-bs))
           ]
       (if (= n (count items))
         (list items)
         (if (empty? items)
           items
           (concat
            (select n (rest items))
            (lmul (first items) (select (dec n) (rest items))))))))) 

Es gibt drei Möglichkeiten, es aufzurufen:

(a) für genau n ausgewählte Elemente, wenn die Frage verlangt:

  user=> (count (select 3 "abcdefgh"))
  56

(b) für zwischen n1 und n2 ausgewählte Elemente:

user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))

(c) Für zwischen 0 und der Größe der ausgewählten Sammlung ausgewählte Elemente:

user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))

C-Code für Algorithmus L (Lexikographische Kombinationen) in Abschnitt 7.2.1.3 von Die Kunst der Computerprogrammierung, Band 4A: Kombinatorische Algorithmen, Teil 1 :

#include <stdio.h>
#include <stdlib.h>

void visit(int* c, int t) 
{
  // for (int j = 1; j <= t; j++)
  for (int j = t; j > 0; j--)
    printf("%d ", c[j]);
  printf("\n");
}

int* initialize(int n, int t) 
{
  // c[0] not used
  int *c = (int*) malloc((t + 3) * sizeof(int));

  for (int j = 1; j <= t; j++)
    c[j] = j - 1;
  c[t+1] = n;
  c[t+2] = 0;
  return c;
}

void comb(int n, int t) 
{
  int *c = initialize(n, t);
  int j;

  for (;;) {
    visit(c, t);
    j = 1;
    while (c[j]+1 == c[j+1]) {
      c[j] = j - 1;
      ++j;
    }
    if (j > t) 
      return;
    ++c[j];
  }
  free(c);
}

int main(int argc, char *argv[])
{
  comb(5, 3);
  return 0;
}

#include <stdio.h>

unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
    unsigned int finished = 0;
    unsigned int changed = 0;
    unsigned int i;

    if (k > 0) {
        for (i = k - 1; !finished && !changed; i--) {
            if (ar[i] < (n - 1) - (k - 1) + i) {
                /* Increment this element */
                ar[i]++;
                if (i < k - 1) {
                    /* Turn the elements after it into a linear sequence */
                    unsigned int j;
                    for (j = i + 1; j < k; j++) {
                        ar[j] = ar[j - 1] + 1;
                    }
                }
                changed = 1;
            }
            finished = i == 0;
        }
        if (!changed) {
            /* Reset to first combination */
            for (i = 0; i < k; i++) {
                ar[i] = i;
            }
        }
    }
    return changed;
}

typedef void(*printfn)(const void *, FILE *);

void print_set(const unsigned int *ar, size_t len, const void **elements,
    const char *brackets, printfn print, FILE *fptr)
{
    unsigned int i;
    fputc(brackets[0], fptr);
    for (i = 0; i < len; i++) {
        print(elements[ar[i]], fptr);
        if (i < len - 1) {
            fputs(", ", fptr);
        }
    }
    fputc(brackets[1], fptr);
}

int main(void)
{
    unsigned int numbers[] = { 0, 1, 2 };
    char *elements[] = { "a", "b", "c", "d", "e" };
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    do {
        print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
        putchar('\n');
    } while (next_combination(numbers, n, k));
    getchar();
    return 0;
}

Eine andere Lösung mit C #:

 static List<List<T>> GetCombinations<T>(List<T> originalItems, int combinationLength)
    {
        if (combinationLength < 1)
        {
            return null;
        }

        return CreateCombinations<T>(new List<T>(), 0, combinationLength, originalItems);
    }

 static List<List<T>> CreateCombinations<T>(List<T> initialCombination, int startIndex, int length, List<T> originalItems)
    {
        List<List<T>> combinations = new List<List<T>>();
        for (int i = startIndex; i < originalItems.Count - length + 1; i++)
        {
            List<T> newCombination = new List<T>(initialCombination);
            newCombination.Add(originalItems[i]);
            if (length > 1)
            {
                List<List<T>> newCombinations = CreateCombinations(newCombination, i + 1, length - 1, originalItems);
                combinations.AddRange(newCombinations);
            }
            else
            {
                combinations.Add(newCombination);
            }
        }

        return combinations;
    }

Verwendungsbeispiel:

   List<char> initialArray = new List<char>() { 'a','b','c','d'};
   int combinationLength = 3;
   List<List<char>> combinations = GetCombinations(initialArray, combinationLength);

void combine(char a[], int N, int M, int m, int start, char result[]) {
    if (0 == m) {
        for (int i = M - 1; i >= 0; i--)
            std::cout << result[i];
        std::cout << std::endl;
        return;
    }
    for (int i = start; i < (N - m + 1); i++) {
        result[m - 1] = a[i];
        combine(a, N, M, m-1, i+1, result);
    }
}

void combine(char a[], int N, int M) {
    char *result = new char[M];
    combine(a, N, M, M, 0, result);
    delete[] result;
}

In der ersten Funktion gibt m an, wie viele weitere Sie auswählen müssen, und start gibt an, von welcher Position im Array aus Sie auswählen müssen.

Hier ist ein einfacher Code, der alle C (n, m) -Kombinationen druckt. Es funktioniert, indem eine Reihe von Arrayindizes initialisiert und verschoben wird, die auf die nächste gültige Kombination zeigen. Die Indizes werden so initialisiert, dass sie auf die niedrigsten m-Indizes zeigen (lexikographisch die kleinste Kombination). Dann, beginnend mit dem m-ten Index, versuchen wir, die Indizes vorwärts zu bewegen. Wenn ein Index sein Limit erreicht hat, versuchen wir den vorherigen Index (bis hin zu Index 1). Wenn wir einen Index nach vorne verschieben können, setzen wir alle größeren Indizes zurück.

m=(Rand()%n)+1; // m will vary from 1 to n

for (i=0;i<n;i++) a[i]=i+1;

// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);

// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination

done=false;
while (!done)
{
    // print combination
    for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
    printf("\n");

    // update combination
    // method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
    // if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
    // if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
    // repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
    j=m-1;
    i=1;
    move_found=false;
    while ((j>=0) && !move_found)
    {
        if (p[j]<(n-i)) 
        {
            move_found=true;
            p[j]++; // point p[j] to next index
            for (k=j+1;k<m;k++)
            {
                p[k]=p[j]+(k-j);
            }
        }
        else
        {
            j--;
            i++;
        }
    }
    if (!move_found) done=true;
}

Da die Programmiersprache nicht erwähnt wird, gehe ich davon aus, dass auch die Listen in Ordnung sind. Hier ist eine OCaml-Version, die sich für kurze Listen eignet (nicht rekursiv). Wenn eine Liste l der Elemente von any type und eine ganze Zahl n gegeben wird, wird eine Liste aller möglichen Listen mit _ zurückgegeben.n Elemente von l, wenn wir davon ausgehen, dass die Reihenfolge der Elemente in den Ergebnislisten ignoriert wird, dh list ['a'; 'b'] ist dasselbe wie ['b'; 'a'] und wird einmal gemeldet. Die Größe der resultierenden Liste ist also ((List.length l) Choose n).

Die Intuition der Rekursion ist folgende: Sie nehmen den Kopf der Liste und führen dann zwei rekursive Aufrufe durch:

• rekursiver Aufruf 1 (RC1): bis zum Ende der Liste, aber wählen Sie n-1 Elemente
• rekursiver Aufruf 2 (RC2): bis zum Ende der Liste, aber wählen Sie n Elemente

um die rekursiven Ergebnisse zu kombinieren, listen Sie den Kopf der Liste mit den Ergebnissen von RC1 und fügen Sie dann (@) die Ergebnisse von RC2 an (bitte tragen Sie den ungeraden Namen). Listenmultiplizieren ist die folgende Operation lmul:

a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]

lmul ist im folgenden Code als implementiert

List.map (fun x -> h::x)

Die Rekursion wird beendet, wenn die Größe der Liste der Anzahl der Elemente entspricht, die Sie auswählen möchten. In diesem Fall geben Sie einfach die Liste selbst zurück.

Hier ist ein Vier-Liner in OCaml, der den obigen Algorithmus implementiert:

    let rec choose l n = match l, (List.length l) with                                 
    | _, lsize  when n==lsize  -> [l]                                
    | h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)   
    | [], _ -> []    

Auf den Zug springen und eine andere Lösung posten. Dies ist eine generische Java-Implementierung. Eingabe: (int k) ist die Anzahl der auszuwählenden Elemente und (List<T> list) ist die Liste zur Auswahl. Gibt eine Liste von Kombinationen (List<List<T>>) zurück.

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

kurzer Python-Code, der Indexpositionen ergibt

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

    i = 0
    a = [0 for i in range(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

Hier ist eine einfache JS-Lösung:

function getAllCombinations(n, k, f1) {
	indexes = Array(k);
  for (let i =0; i< k; i++) {
  	indexes[i] = i;
  }
  var total = 1;
  f1(indexes);
  while (indexes[0] !== n-k) {
  	total++;
		getNext(n, indexes);
    f1(indexes);
  }
  return {total};
}

function getNext(n, vec) {
	const k = vec.length;
  vec[k-1]++;
	for (var i=0; i<k; i++) {
  	var currentIndex = k-i-1;
    if (vec[currentIndex] === n - i) {
	  	var nextIndex = k-i-2;
      vec[nextIndex]++;
      vec[currentIndex] = vec[nextIndex] + 1;
    }
  }

	for (var i=1; i<k; i++) {
    if (vec[i] === n - (k-i - 1)) {
      vec[i] = vec[i-1] + 1;
    }
  }
	return vec;
} 



let start = new Date();
let result = getAllCombinations(10, 3, indexes => console.log(indexes)); 
let runTime = new Date() - start; 

console.log({
result, runTime
});

Hier ist ein LISP-Ansatz unter Verwendung eines Makros. Dies funktioniert in Common LISP und sollte in anderen LISP-Dialekten funktionieren.

Der folgende Code erstellt 'n' verschachtelte Schleifen und führt für jede Kombination von 'n' Elementen aus der Liste body einen beliebigen Codeabschnitt aus (in der Variablen lst gespeichert). Die Variable var zeigt auf eine Liste mit den für die Schleifen verwendeten Variablen.

(defmacro do-combinations ((var lst num) &body body)
  (loop with syms = (loop repeat num collect (gensym))
        for i on syms
        for k = `(loop for ,(car i) on (cdr ,(cadr i))
                         do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
                then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
        finally (return k)))

Mal schauen...

(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))

(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
 (LOOP FOR #:G3216 ON (CDR #:G3217) DO
  (LOOP FOR #:G3215 ON (CDR #:G3216) DO
   (LOOP FOR #:G3214 ON (CDR #:G3215) DO
    (LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
     (PROGN (PPRINT (MAPCAR #'CAR P))))))))

(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))

(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...

Da Kombinationen nicht standardmäßig gespeichert werden, wird der Speicherplatz auf ein Minimum beschränkt. Die Möglichkeit, den body-Code zu wählen, anstatt alle Ergebnisse zu speichern, bietet auch mehr Flexibilität.

Hier ist eine C++ - Lösung, die ich mit Rekursion und Bit-Shifting gefunden habe. Es kann auch in C funktionieren.

void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Wie das funktioniert, finden Sie hier hier .

Hier ist ein Algorithmus, mit dem ich dieses Problem gelöst habe. Es ist in c ++ geschrieben, kann aber an fast jede Sprache angepasst werden, die bitweise Operationen unterstützt.

void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
    unsigned int n = (startNum - bitVal) << 1;
    n += bitVal ? 1 : 0;

    for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
        cout << (n >> (i - 1) & 1);
    cout << endl;

    if (!(n & testNum) && n != startNum)
        r_nCr(n, bitVal, testNum);

    if (bitVal && bitVal < testNum)
        r_nCr(startNum, bitVal >> 1, testNum);
}

Sie sehen eine Erklärung, wie es funktioniert hier .

C # einfacher Algorithmus . (Ich veröffentliche ihn, seit ich versucht habe, den von Ihnen hochgeladenen zu verwenden, aber aus irgendeinem Grund konnte ich ihn nicht kompilieren - eine Klasse erweitern?) Also schrieb ich meine eigene nur für den Fall, dass jemand anderes vor dem gleichen Problem steht wie ich ...) Ich bin nicht viel mehr mit c # beschäftigt als mit der grundlegenden Programmierung, aber dieses funktioniert gut.

public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
        {
            List<List<int>> lSubsets = new List<List<int>>();
            GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
            return lSubsets;
        }

public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
        {
            if (lCurrSet.Count == k)
            {
                lSubsets.Add(lCurrSet);
                return;
            }

            if (i >= lInputSet.Count)
                return;

            List<int> lWith = new List<int>(lCurrSet);
            List<int> lWithout = new List<int>(lCurrSet);
            lWith.Add(lInputSet[i++]);

            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
            GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
        }

VERWENDUNG: GetSubsetsOfSizeK(set of type List<int>, integer k)

Sie können es so ändern, dass es mit dem abläuft, mit dem Sie gerade arbeiten.

Viel Glück!

In Python wird die Rekursion ausgenutzt und die Tatsache, dass alles durch Verweis erledigt wird. Dies erfordert viel Speicher für sehr große Mengen, hat jedoch den Vorteil, dass die anfängliche Menge ein komplexes Objekt sein kann. Es werden nur eindeutige Kombinationen gefunden.

import copy

def find_combinations( length, set, combinations = None, candidate = None ):
    # recursive function to calculate all unique combinations of unique values
    # from [set], given combinations of [length].  The result is populated
    # into the 'combinations' list.
    #
    if combinations == None:
        combinations = []
    if candidate == None:
        candidate = []

    for item in set:
        if item in candidate:
            # this item already appears in the current combination somewhere.
            # skip it
            continue

        attempt = copy.deepcopy(candidate)
        attempt.append(item)
        # sorting the subset is what gives us completely unique combinations,
        # so that [1, 2, 3] and [1, 3, 2] will be treated as equals
        attempt.sort()

        if len(attempt) < length:
            # the current attempt at finding a new combination is still too
            # short, so add another item to the end of the set
            # yay recursion!
            find_combinations( length, set, combinations, attempt )
        else:
            # the current combination attempt is the right length.  If it
            # already appears in the list of found combinations then we'll
            # skip it.
            if attempt in combinations:
                continue
            else:
                # otherwise, we append it to the list of found combinations
                # and move on.
                combinations.append(attempt)
                continue
    return len(combinations)

Du verwendest es so. Das Übergeben von 'result' ist optional, so dass Sie es einfach verwenden können, um die Anzahl der möglichen Kombinationen zu erhalten ... obwohl das wirklich ineffizient wäre (es ist besser, dies durch Berechnung zu tun).

size = 3
set = [1, 2, 3, 4, 5]
result = []

num = find_combinations( size, set, result ) 
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

Sie sollten die folgende Ausgabe von diesen Testdaten erhalten:

size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]

Und es wird genauso gut funktionieren, wenn Ihr Set so aussieht:

set = [
    [ 'Vanilla', 'cupcake' ],
    [ 'chocolate', 'pudding' ],
    [ 'Vanilla', 'pudding' ],
    [ 'chocolate', 'cookie' ],
    [ 'mint', 'cookie' ]
]

Sehr schnelle Kombinationen für MetaTrader MQL4, implementiert als Iterator-Objekt.

Der Code ist so einfach zu verstehen.

Ich habe viele Algorithmen getestet, dieser ist wirklich sehr schnell - etwa dreimal schneller als die meisten next_combination () - Funktionen.

class CombinationsIterator
{
private:
	int input_array[];  // 1 2 3 4 5
	int index_array[];  // i j k
	int m_elements;     // N
	int m_indices;      // K

public:
	CombinationsIterator(int &src_data[], int k)
	{
		m_indices = k;
		m_elements = ArraySize(src_data);
		ArrayCopy(input_array, src_data);
		ArrayResize(index_array, m_indices);

		// create initial combination (0..k-1)
		for (int i = 0; i < m_indices; i++)
		{
			index_array[i] = i;
		}
	}

	// https://stackoverflow.com/questions/5076695
	// bool next_combination(int &item[], int k, int N)
	bool advance()
	{
		int N = m_elements;
		for (int i = m_indices - 1; i >= 0; --i)
		{
			if (index_array[i] < --N)
			{
				++index_array[i];
				for (int j = i + 1; j < m_indices; ++j)
				{
					index_array[j] = index_array[j - 1] + 1;
				}
				return true;
			}
		}
		return false;
	}

	void getItems(int &items[])
	{
		// fill items[] from input array
		for (int i = 0; i < m_indices; i++)
		{
			items[i] = input_array[index_array[i]];
		}
	}
};

Ein Treiberprogramm zum Testen der obigen Iterator-Klasse:

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above class

#define N 5
#define K 3

void OnStart()
{
	int myset[N] = {1, 2, 3, 4, 5};
	int items[K];

	CombinationsIterator comboIt(myset, K);

	do
	{
		comboIt.getItems(items);

		printf("%s", ArrayToString(items));

	} while (comboIt.advance());

}

Output:
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

Kurze, schnelle C # -Implementierung

public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
    return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));                
}      

public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
    var result = new List<int[]>();

    var lastIndex = subSetLenght - 1;
    var dif = setLenght - subSetLenght;
    var prevSubSet = new int[subSetLenght];
    var lastSubSet = new int[subSetLenght];
    for (int i = 0; i < subSetLenght; i++)
    {
        prevSubSet[i] = i;
        lastSubSet[i] = i + dif;
    }

    while(true)
    {
        //add subSet ad result set
        var n = new int[subSetLenght];
        for (int i = 0; i < subSetLenght; i++)
            n[i] = prevSubSet[i];

        result.Add(n);

        if (prevSubSet[0] >= lastSubSet[0])
            break;

        //start at index 1 because index 0 is checked and breaking in the current loop
        int j = 1;
        for (; j < subSetLenght; j++)
        {
            if (prevSubSet[j] >= lastSubSet[j])
            {
                prevSubSet[j - 1]++;

                for (int p = j; p < subSetLenght; p++)
                    prevSubSet[p] = prevSubSet[p - 1] + 1;

                break;
            }
        }

        if (j > lastIndex)
            prevSubSet[lastIndex]++;
    }

    return result;
}

eine weitere rekursive Lösung (Sie sollten in der Lage sein, diese zu portieren, um Buchstaben anstelle von Zahlen zu verwenden). 

stack = [] 
def choose(n,x):
   r(0,0,n+1,x)

def r(p, c, n,x):
   if x-c == 0:
      print stack
      return

   for i in range(p, n-(x-1)+c):
      stack.append(i)
      r(i+1,c+1,n,x)
      stack.pop()

4 Wählen Sie 3 oder ich möchte alle 3 Zahlenkombinationen, die mit 0 bis 4 beginnen

choose(4,3) 

[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 2, 3]
[0, 2, 4]
[0, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

Ich möchte meine Lösung vorstellen. Keine rekursiven Aufrufe oder geschachtelten Schleifen in next. Der Kern des Codes ist die next()-Methode.

public class Combinations {
    final int pos[];
    final List<Object> set;

    public Combinations(List<?> l, int k) {
        pos = new int[k];
        set=new ArrayList<Object>(l);
        reset();
    }
    public void reset() {
        for (int i=0; i < pos.length; ++i) pos[i]=i;
    }
    public boolean next() {
        int i = pos.length-1;
        for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
            if (i==0) return false;
            --i;
        }
        ++pos[i];
        while (++i < pos.length)
            pos[i]=pos[i-1]+1;
        return true;
    }

    public void getSelection(List<?> l) {
        @SuppressWarnings("unchecked")
        List<Object> ll = (List<Object>)l;
        if (ll.size()!=pos.length) {
            ll.clear();
            for (int i=0; i < pos.length; ++i)
                ll.add(set.get(pos[i]));
        }
        else {
            for (int i=0; i < pos.length; ++i)
                ll.set(i, set.get(pos[i]));
        }
    }
}

Und Anwendungsbeispiel:

static void main(String[] args) {
    List<Character> l = new ArrayList<Character>();
    for (int i=0; i < 32; ++i) l.add((char)('a'+i));
    Combinations comb = new Combinations(l,5);
    int n=0;
    do {
        ++n;
        comb.getSelection(l);
        //Log.debug("%d: %s", n, l.toString());
    } while (comb.next());
    Log.debug("num = %d", n);
}

Hier ist eine Kaffeescript-Implementierung 

combinations: (list, n) ->
        permuations = Math.pow(2, list.length) - 1
        out = []
        combinations = []

        while permuations
            out = []

            for i in [0..list.length]
                y = ( 1 << i )
                if( y & permuations and (y isnt permuations))
                    out.Push(list[i])

            if out.length <= n and out.length > 0
                combinations.Push(out)

            permuations--

        return combinations 

Vielleicht habe ich den Punkt verpasst (dass Sie den Algorithmus und nicht die fertige Lösung benötigen), aber es scheint, als würde Scala das sofort tun (jetzt):

def combis(str:String, k:Int):Array[String] = {
  str.combinations(k).toArray 
}

Verwenden Sie die Methode wie folgt:

  println(combis("abcd",2).toList)

Wird herstellen:

  List(ab, ac, ad, bc, bd, cd)

Dies ist mein Beitrag in Javascript (keine Rekursion)

set = ["q0", "q1", "q2", "q3"]
collector = []


function comb(num) {
  results = []
  one_comb = []
  for (i = set.length - 1; i >= 0; --i) {
    tmp = Math.pow(2, i)
    quotient = parseInt(num / tmp)
    results.Push(quotient)
    num = num % tmp
  }
  k = 0
  for (i = 0; i < results.length; ++i)
    if (results[i]) {
      ++k
      one_comb.Push(set[i])
    }
  if (collector[k] == undefined)
    collector[k] = []
  collector[k].Push(one_comb)
}


sum = 0
for (i = 0; i < set.length; ++i)
  sum += Math.pow(2, i)
 for (ii = sum; ii > 0; --ii)
  comb(ii)
 cnt = 0
for (i = 1; i < collector.length; ++i) {
  n = 0
  for (j = 0; j < collector[i].length; ++j)
    document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
  document.write("<hr>")
}   

Rekursiv eine sehr einfache Antwort, combo, in Free Pascal.

    procedure combinata (n, k :integer; producer :oneintproc);

        procedure combo (ndx, nbr, len, lnd :integer);
        begin
            for nbr := nbr to len do begin
                productarray[ndx] := nbr;
                if len < lnd then
                    combo(ndx+1,nbr+1,len+1,lnd)
                else
                    producer(k);
            end;
        end;

    begin
        combo (0, 0, n-k, n-1);
    end;

"Produzent" verfügt über das für jede Kombination erstellte Produktarray.

Sammelmanipulationen sind nicht erforderlich. Das Problem ist fast dasselbe wie das Durchlaufen von K verschachtelten Schleifen, aber Sie müssen vorsichtig mit den Indizes und Begrenzungen sein (Java und OOP ignorieren):

 public class CombinationsGen {
    private final int n;
    private final int k;
    private int[] buf;

    public CombinationsGen(int n, int k) {
        this.n = n;
        this.k = k;
    }

    public void combine(Consumer<int[]> consumer) {
        buf = new int[k];
        rec(0, 0, consumer);
    }

    private void rec(int index, int next, Consumer<int[]> consumer) {
        int max = n - index;

        if (index == k - 1) {
            for (int i = 0; i < max && next < n; i++) {
                buf[index] = next;
                next++;
                consumer.accept(buf);
            }
        } else {
            for (int i = 0; i < max && next + index < n; i++) {
                buf[index] = next;
                next++;
                rec(index + 1, next, consumer);
            }
        }
    }
}

Verwenden Sie wie folgt:

 CombinationsGen gen = new CombinationsGen(5, 2);

 AtomicInteger total = new AtomicInteger();
 gen.combine(arr -> {
     System.out.println(Arrays.toString(arr));
     total.incrementAndGet();
 });
 System.out.println(total);

Erwartete Ergebnisse erhalten:

[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10

Ordnen Sie schließlich die Indizes Ihren Datenbeständen zu.

Kurze, schnelle C-Implementierung

#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
}

Um zu sehen, wie schnell es ist, verwenden Sie diesen Code und testen Sie ihn

#include <time.h>
#include <stdio.h>

void main(int argc, char *argv[]) {
  const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
  const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
  int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */

  int c = 0; int i = 0;
  for (int j = 0; j <= n; j++) comb[j] = 0;
  while (i >= 0) {
    if (comb[i] < n + i - p + 1) {
       comb[i]++;
       /* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
       if (i == p - 1) c++;
       else            { comb[++i] = comb[i - 1]; }
    } else i--; }
  printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}

test mit cmd.exe (windows):

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in          5.781 second(s)

c:\Program Files\lcc\projects>

Einen schönen Tag noch.

Hier ist meine JavaScript-Lösung, die durch die Verwendung von remove/map etwas funktionaler ist, wodurch fast alle Variablen eliminiert werden

function combinations(arr, size) {
  var len = arr.length;

  if (size > len) return [];
  if (!size) return [[]];
  if (size == len) return [arr];

  return arr.reduce(function (acc, val, i) {
    var res = combinations(arr.slice(i + 1), size - 1)
      .map(function (comb) { return [val].concat(comb); });
    
    return acc.concat(res);
  }, []);
}

var combs = combinations([1,2,3,4,5,6,7,8],3);
combs.map(function (comb) {
  document.body.innerHTML += comb.toString() + '<br />';
});

document.body.innerHTML += '<br /> Total combinations = ' + combs.length;

Wie wäre es mit dieser Antwort ... dies druckt alle Kombinationen der Länge 3 ... und kann für jede Länge generalisiert werden ....

#include<iostream>
#include<string>
using namespace std;

void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l  == 3 ){
 cout<<dest<<endl;}
else{
  if(!a.empty() && dest.length() < 3 ){
     combination(a.substr(1,a.length()),dest+a[0]);}
  if(!a.empty() && dest.length() <= 3 ){
      combination(a.substr(1,a.length()),dest);}
 }

 }

 int main(){
 string demo("abcd");
 combination(demo,"");
 return 0;
 }

Wir können das Konzept der Bits verwenden, um dies zu tun. Lassen Sie uns eine Folge von "abc" haben, und wir möchten alle Kombinationen der Elemente mit der Länge 2 haben (d. H. "Ab", "ac", "bc").

Wir können die gesetzten Bits in Zahlen von 1 bis 2 ^ n (exklusiv) finden. Hier 1 bis 7, und wo immer wir Bits = 2 gesetzt haben, können wir den entsprechenden Wert aus einem String drucken.

zum Beispiel:

• 1 - 001
• 2 - 010
• 3 - 011 -> print ab (str[0] , str[1])
• 4 - 100
• 5 - 101 -> print ac (str[0] , str[2])
• 6 - 110 -> print ab (str[1] , str[2])
• 7 - 111.

Codebeispiel:

public class StringCombinationK {   
    static void combk(String s , int k){
        int n = s.length();
        int num = 1<<n;
        int j=0;
        int count=0;

        for(int i=0;i<num;i++){
            if (countSet(i)==k){
                setBits(i,j,s);
                count++;
                System.out.println();
            }
        }

        System.out.println(count);
    }

    static void setBits(int i,int j,String s){ // print the corresponding string value,j represent the index of set bit
        if(i==0){
            return;
        }

        if(i%2==1){
            System.out.print(s.charAt(j));                  
        }

        setBits(i/2,j+1,s);
    }

    static int countSet(int i){ //count number of set bits
        if( i==0){
            return 0;
        }

        return (i%2==0? 0:1) + countSet(i/2);
    }

    public static void main(String[] arhs){
        String s = "abcdefgh";
        int k=3;
        combk(s,k);
    }
}

Ich habe eine allgemeine Klasse für Kombinationen in C++ ... erstellt, die so verwendet wird.

char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
    for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
    cout << ' ';
}

Meine Bibliothek ncr [i] gibt von 1 zurück, nicht von 0 Deshalb enthält das Array 0. Wenn Sie die Reihenfolge berücksichtigen möchten, müssen Sie nur die nCr-Klasse auf nPr . Setzen. Die Verwendung ist identisch.

Ergebnis

ABC ABD ABE ABF ABG ABH ACD ACE ACF ACG ACH ADE ADF ADG ADH AEF AEG AEH AFG AFH AGH BCD BCE BCF BCG BCH BDE BDF BDG BDH BEF BEG BEH BFG BFH BGH CDE CDF CDG CDH CEF CEG CEH CFG CFH CGH DEF DEG DEH DFG DFH DGH EFG EFH EGH FGH

Hier geht die Headerdatei.

#pragma once
#include <exception>

class NRexception : public std::exception
{
public:
    virtual const char* what() const throw() {
        return "Combination : N, R should be positive integer!!";
    }
};

class Combination
{
public:
    Combination(int n, int r);
    virtual ~Combination() { delete [] ar;}
    int& operator[](unsigned i) {return ar[i];}
    bool next();
    int size() {return r;}
    static int factorial(int n);

protected:
    int* ar;
    int n, r;
};

class nCr : public Combination
{
public: 
    nCr(int n, int r);
    bool next();
    int count() const;
};

class nTr : public Combination
{
public:
    nTr(int n, int r);
    bool next();
    int count() const;
};

class nHr : public nTr
{
public:
    nHr(int n, int r) : nTr(n,r) {}
    bool next();
    int count() const;
};

class nPr : public Combination
{
public:
    nPr(int n, int r);
    virtual ~nPr() {delete [] on;}
    bool next();
    void rewind();
    int count() const;

private:
    bool* on;
    void inc_ar(int i);
};

Und die Umsetzung.

#include "combi.h"
#include <set>
#include<cmath>

Combination::Combination(int n, int r)
{
    //if(n < 1 || r < 1) throw NRexception();
    ar = new int[r];
    this->n = n;
    this->r = r;
}

int Combination::factorial(int n) 
{
    return n == 1 ? n : n * factorial(n-1);
}

int nPr::count() const
{
    return factorial(n)/factorial(n-r);
}

int nCr::count() const
{
    return factorial(n)/factorial(n-r)/factorial(r);
}

int nTr::count() const
{
    return pow(n, r);
}

int nHr::count() const
{
    return factorial(n+r-1)/factorial(n-1)/factorial(r);
}

nCr::nCr(int n, int r) : Combination(n, r)
{
    if(r == 0) return;
    for(int i=0; i<r-1; i++) ar[i] = i + 1;
    ar[r-1] = r-1;
}

nTr::nTr(int n, int r) : Combination(n, r)
{
    for(int i=0; i<r-1; i++) ar[i] = 1;
    ar[r-1] = 0;
}

bool nCr::next()
{
    if(r == 0) return false;
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n-r+2+i) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++] + 1;
    return true;
}

bool nTr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        ar[i] = 1;
        if(--i == -1) return false;
        ar[i]++;
    }
    return true;
}

bool nHr::next()
{
    ar[r-1]++;
    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        ar[i]++;
    }
    while(i < r-1) ar[i+1] = ar[i++];
    return true;
}

nPr::nPr(int n, int r) : Combination(n, r)
{
    on = new bool[n+2];
    for(int i=0; i<n+2; i++) on[i] = false;
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

void nPr::rewind()
{
    for(int i=0; i<r; i++) {
        ar[i] = i + 1;
        on[i] = true;
    }
    ar[r-1] = 0;
}

bool nPr::next()
{   
    inc_ar(r-1);

    int i = r-1;
    while(ar[i] == n+1) {
        if(--i == -1) return false;
        inc_ar(i);
    }
    while(i < r-1) {
        ar[++i] = 0;
        inc_ar(i);
    }
    return true;
}

void nPr::inc_ar(int i)
{
    on[ar[i]] = false;
    while(on[++ar[i]]);
    if(ar[i] != n+1) on[ar[i]] = true;
}

Einfacher, aber langsamer C++ - Backtracking-Algorithmus.

#include <iostream>

void backtrack(int* numbers, int n, int k, int i, int s)
{
    if (i == k)
    {
        for (int j = 0; j < k; ++j)
        {
            std::cout << numbers[j];
        }
        std::cout << std::endl;

        return;
    }

    if (s > n)
    {
        return;
    }

    numbers[i] = s;
    backtrack(numbers, n, k, i + 1, s + 1);
    backtrack(numbers, n, k, i, s + 1);
}

int main(int argc, char* argv[])
{
    int n = 5;
    int k = 3;

    int* numbers = new int[k];

    backtrack(numbers, n, k, 0, 1);

    delete[] numbers;

    return 0;
}

In Python wie Andrea Ambu, aber für die Wahl von drei nicht hartcodiert.

def combinations(list, k):
    """Choose combinations of list, choosing k elements(no repeats)"""
    if len(list) < k:
        return []
    else:
        seq = [i for i in range(k)]
        while seq:
            print [list[index] for index in seq]
            seq = get_next_combination(len(list), k, seq)

def get_next_combination(num_elements, k, seq):
        index_to_move = find_index_to_move(num_elements, seq)
        if index_to_move == None:
            return None
        else:
            seq[index_to_move] += 1

            #for every element past this sequence, move it down
            for i, elem in enumerate(seq[(index_to_move+1):]):
                seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1

            return seq

def find_index_to_move(num_elements, seq):
        """Tells which index should be moved"""
        for rev_index, elem in enumerate(reversed(seq)):
            if elem < (num_elements - rev_index - 1):
                return len(seq) - rev_index - 1
        return None   

Wenn Sie dem Haskell-Code folgen, berechnen Sie die Kombinationsnummer und Kombinationen gleichzeitig , und dank Haskells Faulheit können Sie einen Teil davon erhalten, ohne den anderen zu berechnen.

import Data.Semigroup
import Data.Monoid

data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)

instance Semigroup Comb where
    (MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)

instance Monoid Comb where
    mempty = MkComb 0 []

addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)

comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))

Es funktioniert wie folgt:

*Main> comb 0 1
MkComb {count = 0, combinations = []}

*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}

*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}

*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}

*Main> count (comb 10 5)
252