Algorytm zwracający wszystkie kombinacje elementów k Z n

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

Użycie:

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

Wynik:

123
124
125
134
135
145
234
235
245
345

Krótkie rozwiązanie java:

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

Wynik będzie

[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]

Czy mogę przedstawić moje rekurencyjne rozwiązanie Pythona tego problemu?

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

Przykładowe użycie:

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

Powiedzmy, że tablica liter wygląda tak: "ABCDEFGH". Masz trzy indeksy (i, j, k) wskazujące, które litery zamierzasz użyć dla bieżącego słowa, zaczynasz od:

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

Najpierw zmieniasz k, więc następny krok wygląda tak:

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

Jeśli dotarłeś do końca, dalej zmieniasz j I k.

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

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

Gdy J osiągniesz G, zaczynasz również zmieniać i.

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

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

Napisane w kodzie to tak wygląda

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

Następujący algorytm rekurencyjny wybiera wszystkie kombinacje elementów k z uporządkowanego zbioru:

• wybierz pierwszy element i swojej kombinacji
• połącz i z każdą kombinacją k-1 elementów wybranych rekurencyjnie ze zbioru elementów większych od i.

Powtórz powyższe dla każdego i w zbiorze.

Ważne jest, aby wybrać resztę elementów jako większą niż i, aby uniknąć powtórzeń. W ten sposób [3,5] będzie należy wybrać tylko raz, jako [3] w połączeniu z [5], zamiast dwa razy (warunek eliminuje [5] + [3]). Bez tego warunku dostajesz wariacje zamiast kombinacji.

Krótki przykład w Pythonie:

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

Dla wyjaśnienia metoda rekurencyjna jest opisana następującym przykładem:

Przykład: A B C D E
Wszystkie kombinacje 3 będą:

• A ze wszystkimi kombinacjami 2 od reszty (B C D E)
• B ze wszystkimi kombinacjami 2 od reszty (C D E)
• C ze wszystkimi kombinacjami 2 od reszty (D E)

W C++ poniższa procedura wytworzy wszystkie kombinacje długości odległości (first,k) pomiędzy zakresem [first, last):

#include <algorithm>

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

Można go używać w następujący sposób:

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

To wydrukuje:

123
124
125
134
135
145
234
235
245
345

Uznałem ten wątek za przydatny i pomyślałem, że dodam rozwiązanie Javascript, które można wrzucić do Firebug. W zależności od silnika JS może to zająć trochę czasu, jeśli ciąg startowy jest duży.

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

Wynik powinien być następujący:

abc
ab
ac
a
bc
b
c

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

Prosty algorytm rekurencyjny w Haskell

import Data.List

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

Najpierw definiujemy przypadek szczególny, tzn. wybieramy zero elementów. Tworzy pojedynczy wynik, który jest pustą listą (tzn. listą zawierającą pustą listę).

Dla n > 0, x przechodzi przez każdy element listy, a xs Jest każdym elementem po x.

rest wybiera n - 1 elementy z xs używając rekurencyjnego wywołania do combinations. Wynikiem końcowym funkcji jest lista, gdzie każdy element jest x : rest (tj. lista, która ma x jako głowę i rest jako ogon) dla każdej innej wartości x i rest.

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

I oczywiście, ponieważ Haskell jest leniwy, lista jest stopniowo generowana w razie potrzeby, więc można częściowo ocenić wykładniczo duże kombinacje.

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

I oto nadchodzi dziadek COBOL, bardzo złośliwy język.

Załóżmy tablicę 34 elementów po 8 bajtów każdy (czysto dowolny wybór.) Chodzi o wyliczenie wszystkich możliwych kombinacji 4-elementowych i załadowanie ich do tablicy.

Używamy 4 indeksów, po jednym dla każdej pozycji w grupie 4

Tablica jest przetwarzana w następujący sposób:

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

Różnimy idx4 od 4 do końca. Dla każdego idx4 otrzymujemy unikalną kombinację grupy po cztery osoby. Gdy idx4 pod koniec tablicy zwiększamy idx3 o 1 i ustawiamy idx4 na idx3+1. Następnie uruchamiamy idx4 do końca ponownie. Postępujemy w ten sposób, zwiększając odpowiednio idx3, idx2 i idx1, aż pozycja idx1 będzie mniejsza niż 4 od końca tablicy. To kończy algorytm.

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

Pierwsza iteracja:

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

Przykład COBOLa:

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.

Oto elegancka, generyczna implementacja w Scali, opisana na 99 problemach Scali .

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 :: _}
    }
}

Jeśli możesz użyć składni SQL - powiedzmy, jeśli używasz LINQ do dostępu do pól struktury lub tablicy, lub bezpośrednio uzyskujesz dostęp do bazy danych, która ma tabelę o nazwie "Alfabet" z jednym polem znaków "litera" , możesz dostosować następujący kod:

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

Zwróci to wszystkie kombinacje 3 liter, niezależnie od tego, ile liter masz w tabeli "alfabet" (może to być 3, 8, 10, 27 itd.).

Jeśli to, co chcesz, to wszystkie permutacje, a nie kombinacje (tzn. chcesz " ACB " i "ABC" liczyć jako różne, a nie pojawiają się tylko raz) wystarczy usunąć ostatnią linię (I jeden) i gotowe.

Post-Edit: po ponownym przeczytaniu pytania zdaję sobie sprawę, że potrzebny jest ogólny algorytm, a nie tylko konkretny dla przypadku wyboru 3 pozycji. Odpowiedź Adama Hughesa jest kompletna, niestety nie mogę głosować (jeszcze). Ta odpowiedź jest prosta, ale działa tylko wtedy, gdy chcesz dokładnie 3 elementy.

Kolejna wersja C# z leniwym generowaniem indeksów kombinacji. Ta wersja utrzymuje pojedynczą tablicę indeksów w celu zdefiniowania mapowania pomiędzy listą wszystkich wartości i wartościami dla bieżącej kombinacji, tzn. stale używa O(k) dodatkowej przestrzeni podczas całego runtime. Kod generuje pojedyncze kombinacje, w tym pierwszą, w czasie O(k) .

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

Kod testu:

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

Wyjście:

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

Https://gist.github.com/3118596

Istnieje implementacja dla JavaScript. Posiada funkcje do uzyskiwania kombinacji k i wszystkich kombinacji tablicy dowolnych obiektów. Przykłady:

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

Miałem algorytm permutacji, którego użyłem w projekcie Euler, w Pythonie:

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

If

n<len(l) 

Powinieneś mieć wszystkie kombinacje, których potrzebujesz, bez powtarzania, potrzebujesz?

Jest to generator, więc używasz go w czymś takim:

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

Tutaj masz leniwą wersję tego algorytmu zakodowaną w C#:

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

I część testowa:

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

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

Wersja Clojure:

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

Powiedzmy, że tablica liter wygląda tak: "ABCDEFGH". Masz trzy indeksy (i, j, k) wskazujące, które litery zamierzasz użyć dla bieżącego słowa, zaczynasz od:

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

Najpierw zmieniasz k, więc następny krok wygląda tak:

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

Jeśli dotarłeś do końca, dalej zmieniasz j I k.

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

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

Gdy J osiągniesz G, zaczynasz również zmieniać i.

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

Na podstawie https://stackoverflow.com/a/127898/2628125 , ale więcej abstrakcyjny, dla dowolnej wielkości wskaźników.

/ Align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center / Algorytm jest widoczny z kodu..

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 []
;;

Oto metoda, która daje wszystkie kombinacje określonego rozmiaru z losowego łańcucha długości. Podobnie jak rozwiązanie quinmarsa, ale działa na różne wejścia i K.

Kod można zmienić na "wrap around", czyli " dab "z wejścia" 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);
    }
}

Wyjście dla "abcde":

Abc abd abe acd ace ade BCD bce bde cde

Algorytm:

• Policz od 1 do 2^N.
• konwertuje każdą cyfrę na jej binarną reprezentację.
• przetłumaczyć każdy bit' on ' na elementy zestawu, w zależności od pozycji.

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

Istnieje bijekcja pomiędzy podzbiorami zbioru N-elementowego i N-bitowych sekwencji.

Oznacza to, że możemy dowiedzieć się, ile podzbiorów istnieje, licząc sekwencje.

Np. poniższy zestaw czterech elementów może być reprezentowane przez {0,1} x {0, 1} x {0, 1} x {0, 1} (lub 2^4) różne sekwencje.

Więc - wystarczy policzyć od 1 do 2^n, aby znaleźć wszystkie kombinacje. (ignorujemy pusty zestaw.) Następnie Przetłumacz cyfry na ich binarną reprezentację. Następnie zamień elementy zestawu na bity "na".

Jeśli chcesz mieć tylko wyniki elementu k, Drukuj tylko wtedy, gdy bity k są 'włączone'.

(Jeśli chcesz wszystkie podzbiory zamiast podzbiorów długości K, usuń część cnt / kElement.)

(Dowód, patrz mit Free Courseware Mathematics for Computer Science, Lehman et al, sekcja 11.2.2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/ )

Krótki kod Pythona, dający pozycje indeksu

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

    i = 0
    a = [0]*k

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

Stworzyłem do tego rozwiązanie w SQL Server 2005 i zamieściłem je na mojej stronie: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Oto przykład do pokazania użycia:

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

Wyniki:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Oto moja propozycja w C++

Starałem się narzucić jak najmniej ograniczeń typowi iteratora, więc to rozwiązanie zakłada tylko iterator forward I może to być const_iterator. Powinno to działać z każdym standardowym kontenerem. W przypadku, gdy argumenty nie mają sensu, rzuca 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));
    }
}

Oto kod, który niedawno napisałem w Javie, który oblicza i zwraca wszystkie kombinacje elementów" num "z elementów "outOf".

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

Zwięzłe rozwiązanie Javascript:

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

Napisałem klasę do obsługi wspólnych funkcji do pracy ze współczynnikiem dwumianowym, który jest rodzajem problemu, pod którym znajduje się twój problem. Wykonuje następujące zadania:

1. Wyświetla wszystkie indeksy K w ładnym formacie dla dowolnego N wybierz K do pliku. Indeksy K mogą być zastępowane bardziej opisowymi ciągami lub literami. Ta metoda sprawia, że rozwiązanie tego typu problemu jest dość trywialne.

2. Konwertuje indeksy K na odpowiedni indeks an wpis do posortowanej tabeli współczynnika dwumianu. Technika ta jest znacznie szybsza niż starsze opublikowane techniki, które opierają się na iteracji. Czyni to za pomocą własności matematycznej właściwej trójkątowi Pascala. Moja gazeta o tym mówi. Wierzę, że jestem pierwszym, który odkrył i opublikował tę technikę, ale mogę się mylić.

3. Konwertuje indeks w posortowanej tabeli współczynników dwumianowych na odpowiednie indeksy K.

4. Używa metody Mark Dominus do Oblicz współczynnik dwumianowy, który jest znacznie mniej podatny na przepełnienie i działa z większymi liczbami.

5. Klasa jest napisana w. Net C# i zapewnia sposób zarządzania obiektami związanymi z problemem (jeśli istnieją) za pomocą listy generycznej. Konstruktor tej klasy pobiera wartość bool o nazwie InitTable, która gdy true utworzy ogólną listę do przechowywania obiektów do zarządzania. Jeżeli wartość jest false, wtedy nie wytworzy tabeli. Tabela nie musi być tworzona w celu wykonania 4 powyższych metod. Dostępne są metody dostępu do tabeli.

6. Istnieje powiązana Klasa testowa, która pokazuje, jak korzystać z klasy i jej metod. Został on dokładnie przetestowany w 2 Przypadkach i nie ma znanych błędów.

Aby przeczytać o tej klasie i pobrać kod, zajrzyj do zakładki o współczynniku Dwumianowym .

Nie powinno być trudno przekonwertować tę klasę do C++.