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

Chcę napisać funkcję, która pobiera tablicę liter jako argument i liczbę tych liter do wyboru.

Załóżmy, że podajesz tablicę 8 liter i chcesz z tego wybrać 3 litery. Następnie powinieneś otrzymać:

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

W zamian tablice (lub słowa) składające się z 3 liter każda.

Art of Computer Programming Volume 4: Fascicle 3 ma mnóstwo takich, które mogą lepiej pasować do twojej konkretnej sytuacji niż to, co opisuję.

Szare Kody

Problem, z którym się zetkniesz, to oczywiście pamięć i dość szybko będziesz miał problemy z 20 elementami w zestawie - ²⁰ C ₃ = 1140. A jeśli chcesz iterować po zestawie, najlepiej użyć zmodyfikowanego szarego algorytm kodu, więc nie trzymasz ich wszystkich w pamięci. Generują one następną kombinację z poprzednich i unikają powtórzeń. Istnieje wiele z nich do różnych zastosowań. Czy chcemy zmaksymalizować różnice między kolejnymi kombinacjami? zminimalizować? i tak dalej.

Niektóre z oryginalnych artykułów opisujących szare kody:

1. Niektóre ścieżki Hamiltona i algorytm minimalnej zmiany
2. Algorytm generowania kombinacji sąsiedniej wymiany

Oto kilka innych artykułów na ten temat:

1. Skuteczna implementacja Eadesa, Hickeya, odczytu algorytmu generowania kombinacji przylegającej wymiany (PDF, z kodem w Pascal)
2. Generatory kombinowane
3. Badanie kombinatoryjnych szarych kodów (PostScript)
4. Algorytm dla szarych kodów

Chase's Twiddle (algorytm)

Phillip J Chase, ` Algorytm 382: Kombinacje M z N obiektów (1970)

Algorytm w C ...

Indeks kombinacji w porządku leksykograficznym (algorytm klamry 515)

Możesz także odwoływać się do kombinacji według jej indeksu (w porządku leksykograficznym). Zdając sobie sprawę, że indeks powinien być pewną zmianą od prawej do lewej w oparciu o indeks, możemy skonstruować coś, co powinno odzyskać kombinację.

Mamy więc zestaw {1,2,3,4,5,6} ... i chcemy trzech elementów. Powiedzmy, że {1,2,3} możemy powiedzieć, że różnica między elementami jest jedna, w kolejności i minimalna. {1,2,4} ma jedną zmianę i jest leksykograficznie liczbą 2. Zatem liczba „zmian” na ostatnim miejscu odpowiada jednej zmianie w porządku leksykograficznym. Drugie miejsce, z jedną zmianą {1,3,4}, ma jedną zmianę, ale uwzględnia więcej zmian, ponieważ jest na drugim miejscu (proporcjonalnie do liczby elementów w oryginalnym zestawie).

Metoda, którą opisałem, jest, jak się wydaje, dekonstrukcją od zestawu do indeksu, musimy zrobić odwrotnie - co jest znacznie trudniejsze. W ten sposób Buckles rozwiązuje problem. Napisałem trochę C, aby je obliczyć , z niewielkimi zmianami - użyłem indeksu zbiorów, a nie zakresu liczb, aby przedstawić zbiór, więc zawsze pracujemy od 0 ... n. Uwaga:

1. Ponieważ kombinacje są nieuporządkowane, {1,3,2} = {1,2,3} - porządkujemy je jako leksykograficzne.
2. Ta metoda ma domyślną wartość 0, aby uruchomić zestaw pierwszej różnicy.

Indeks kombinacji w porządku leksykograficznym (McCaffrey)

Jest inny sposób : jego koncepcja jest łatwiejsza do uchwycenia i zaprogramowania, ale bez optymalizacji Buckles. Na szczęście nie tworzy również duplikatów:

Zestaw, który maksymalizuje , gdzie .

Na przykład: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Tak więc 27. kombinacja leksykograficzna czterech rzeczy to: {1,2,5,6}, są to indeksy dowolnego zestawu, na który chcesz spojrzeć. Przykład poniżej (OCaml), wymaga choosefunkcji, pozostawionej czytelnikowi:

(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
    (* maximize function -- maximize a that is aCb              *)
    (* return largest c where c < i and choose(c,i) <= z        *)
    let rec maximize a b x =
        if (choose a b ) <= x then a else maximize (a-1) b x
    in
    let rec iterate n x i = match i with
        | 0 -> []
        | i ->
            let max = maximize n i x in
            max :: iterate n (x - (choose max i)) (i-1)
    in
    if x < 0 then failwith "errors" else
    let idxs =  iterate (List.length set) x k in
    List.map (List.nth set) (List.sort (-) idxs)

Mały i prosty iterator kombinacji

Do celów dydaktycznych podano następujące dwa algorytmy. Implementują iterator i (bardziej ogólne) ogólne kombinacje folderów. Są tak szybkie, jak to możliwe, o złożoności O ( ⁿ C _k ). Zużycie pamięci jest ograniczone przez k.

Zaczniemy od iteratora, który wywoła funkcję podaną przez użytkownika dla każdej kombinacji

let iter_combs n k f =
  let rec iter v s j =
    if j = k then f v
    else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
  iter [] 0 0

Bardziej ogólna wersja wywoła funkcję podaną przez użytkownika wraz ze zmienną stanu, zaczynając od stanu początkowego. Ponieważ musimy przekazać stan między różnymi stanami, nie będziemy używać pętli for, ale zamiast tego będziemy używać rekurencji,

let fold_combs n k f x =
  let rec loop i s c x =
    if i < n then
      loop (i+1) s c @@
      let c = i::c and s = s + 1 and i = i + 1 in
      if s < k then loop i s c x else f c x
    else x in
  loop 0 0 [] x

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

Stosowanie:

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 tego problemu w języku Python?

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

Podoba mi się ze względu na prostotę.

Powiedzmy, że twoja tablica liter wygląda następująco: „ABCDEFGH”. Masz trzy wskaźniki (i, j, k) wskazujące, których liter zamierzasz użyć dla bieżącego słowa, zaczynasz od:

ABCDEFGH
^ ^ ^
ijk

Najpierw różnicujesz k, więc następny krok wygląda następująco:

ABCDEFGH
^ ^ ^
ijk

Jeśli osiągnąłeś koniec, idź dalej i zmieniaj j, a następnie k ponownie.

ABCDEFGH
^ ^ ^
ijk

ABCDEFGH
^ ^ ^
ijk

Gdy j osiągniesz G, zaczynasz także zmieniać i.

ABCDEFGH
  ^ ^ ^
  ijk

ABCDEFGH
  ^ ^ ^
  ijk
...

Zapisane w kodzie wygląda to mniej więcej tak

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

Poniższy algorytm rekurencyjny wybiera wszystkie kombinacje elementów k z uporządkowanego zestawu:

• wybierz pierwszy element iswojej kombinacji
• połączyć iz każdą kombinacją k-1elementów wybranych rekurencyjnie z zestawu elementów większych niż i.

Iteruj powyższe dla każdego iz zestawu.

Ważne jest, aby wybrać pozostałe elementy jako większe niż i, aby uniknąć powtórzeń. W ten sposób [3,5] zostanie wybrany tylko raz, ponieważ [3] w połączeniu z [5], zamiast dwa razy (warunek eliminuje [5] + [3]). Bez tego warunku otrzymasz kombinacje zamiast kombinacji.

W C ++ poniższa procedura wygeneruje wszystkie kombinacje odległości długości (pierwsza, k) między zakresem [pierwsza, ostatnia):

#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żyć 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;
}

Spowoduje to wydrukowanie następujących elementów:

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 włamać do Firebug. W zależności od silnika JS, jeśli ciąg początkowy jest duży, może to zająć trochę czasu.

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

Dane wyjściowe powinny wyglądać następująco:

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

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

W celu wyjaśnienia metodę rekurencyjną opisano w następującym przykładzie:

Przykład: ABCDE
Wszystkie kombinacje 3 byłyby następujące:

• A ze wszystkimi kombinacjami 2 od reszty (BCDE)
• B ze wszystkimi kombinacjami 2 z pozostałych (CDE)
• C ze wszystkimi kombinacjami 2 z pozostałych (DE)

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, tj. Wybierając elementy zerowe. Daje pojedynczy wynik, którym jest pusta lista (tj. Lista zawierająca pustą listę).

Dla n> 0 xprzechodzi przez każdy element listy i xsnastępuje po nim każdy element x.

restwybiera n - 1elementy z xswywołania rekurencyjnego do combinations. Końcowym wynikiem funkcji jest lista, w której każdy element jest x : rest(tj. Lista, która ma xgłowę i restogon) dla każdej innej wartości xi 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żesz 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 arbitralny wybór). Chodzi o wyliczenie wszystkich możliwych kombinacji 4-elementowych i załadowanie ich do tablicy.

Używamy 4 wskaźnikó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

Zmieniamy idx4 od 4 do końca. Dla każdego idx4 otrzymujemy unikalną kombinację czterech grup. Kiedy idx4 dojdzie do końca tablicy, zwiększamy idx3 o 1 i ustawiamy idx4 na idx3 + 1. Następnie uruchamiamy idx4 do końca. 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.

Pierwsze iteracje:

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

Przykład COBOL:

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, ogólna implementacja w Scali, jak opisano w 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, aby uzyskać dostęp do pól struktury lub tablicy, lub bezpośrednio uzyskujesz dostęp do bazy danych, która ma tabelę o nazwie „Alfabet” za pomocą tylko jednego pola znakowego „Litera”, możesz dostosować następujące 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

Spowoduje to zwrócenie wszystkich kombinacji 3 liter, niezależnie od liczby liter zawartych w tabeli „Alfabet” (może to być 3, 8, 10, 27 itd.).

Jeśli chcesz wszystkich permutacji, a nie kombinacji (tzn. Chcesz, aby „ACB” i „ABC” liczyły się jako różne, zamiast pojawiać się tylko raz), po prostu usuń ostatni wiersz (AND) i gotowe.

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

Kolejna wersja C # z leniwą generacją wskaźników kombinacji. Ta wersja utrzymuje jedną tablicę indeksów w celu zdefiniowania odwzorowania między listą wszystkich wartości a wartościami dla bieżącej kombinacji, tj. Stale wykorzystuje dodatkową przestrzeń O (k) podczas całego środowiska wykonawczego. Kod generuje poszczególne 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 testowy:

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

Wynik:

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

Oto leniwa oceniana wersja tego algorytmu zakodowana w języku 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));
        }
    }

Mam nadzieję, że ci to pomoże!

Miałem algorytm permutacji użyty do euler projektu, w python:

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


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

Gdyby

n<len(l) 

powinieneś mieć wszystkie potrzebne kombinacje bez powtórzeń, potrzebujesz?

Jest to generator, więc używasz go w coś takiego:

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

Array.prototype.combs = function(num) {

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

    while(of) {

        out = [];

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

            y = (1 << i);

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

        }

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

        of--;
    }

    return combinations;
}

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 twoja tablica liter wygląda następująco: „ABCDEFGH”. Masz trzy wskaźniki (i, j, k) wskazujące, których liter zamierzasz użyć dla bieżącego słowa, zaczynasz od:

ABCDEFGH
^ ^ ^
ijk

Najpierw różnicujesz k, więc następny krok wygląda następująco:

ABCDEFGH
^ ^ ^
ijk

Jeśli osiągnąłeś koniec, idź dalej i zmieniaj j, a następnie k ponownie.

ABCDEFGH
^ ^ ^
ijk

ABCDEFGH
^ ^ ^
ijk

Gdy j osiągniesz G, zaczynasz także zmieniać i.

ABCDEFGH
  ^ ^ ^
  ijk

ABCDEFGH
  ^ ^ ^
  ijk
...

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

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

    return $pointers;     
}

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

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

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

           return true;
        }
    }

    return false;
}

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

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

    return $data;
}

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

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

    return $result;
}

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

Na podstawie https://stackoverflow.com/a/127898/2628125 , ale bardziej abstrakcyjne, dla dowolnego rozmiaru wskaźników.

Wszystko, co zostało powiedziane i zrobione tutaj, zawiera kod O'camla. 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 ciągu o losowej długości. Podobne do rozwiązania quinmars, ale działa dla różnych danych wejściowych i k.

Kod można zmienić, aby się zawijał, tzn. „Dab” z wejścia „abcd” wk = 3.

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


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

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

Dane wyjściowe dla „abcde”:

abc abd abe acd ace ade bcd bce bde cde

W tym celu utworzyłem rozwiązanie w SQL Server 2005 i opublikowałem je na mojej stronie internetowej: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Oto przykład pokazujący użycie:

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

wyniki:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Oto moja propozycja w C ++

Próbowałem nałożyć jak najmniejsze ograniczenie na typ iteratora, jak mogłem, więc to rozwiązanie zakłada tylko iterator do przodu i może być const_iterator. Powinno to działać z każdym standardowym pojemnikiem. W przypadkach, gdy argumenty nie mają sensu, wyrzuca 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);

Algorytm:

• Policz od 1 do 2 ^ n.
• Konwertuj każdą cyfrę na jej reprezentację binarną.
• Przetłumacz każdy bit „na” 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();
        }
    }
}

Dlaczego to działa?

Występuje biject pomiędzy podzbiorami zestawu n-elementów a sekwencjami n-bitowymi.

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

np. cztery elementy ustawione poniżej mogą być reprezentowane przez {0,1} X {0, 1} X {0, 1} X {0, 1} (lub 2 ^ 4) różnymi sekwencjami.

Więc - wszystko, co musimy zrobić, to policzyć od 1 do 2 ^ n, aby znaleźć wszystkie kombinacje. (Ignorujemy pusty zestaw.) Następnie przetłumacz cyfry na ich reprezentację binarną. Następnie zamień elementy zestawu na „włączone” bity.

Jeśli chcesz tylko k wyników, drukuj tylko wtedy, gdy k bitów jest „włączonych”.

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

(Aby uzyskać dowód, patrz bezpłatne oprogramowanie MIT Matematyka dla informatyki, Lehman i in., Sekcja 11.2.2. Https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- na-informatyka-jesień-2010 / odczyty / )

krótki kod python, 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

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

1. Wyprowadza wszystkie indeksy K w ładnym formacie dla dowolnego N wybierającego K do pliku. Indeksy K można zastąpić bardziej opisowymi ciągami lub literami. Ta metoda sprawia, że ​​rozwiązanie tego typu problemu jest dość proste.

2. Konwertuje indeksy K na właściwy indeks pozycji w posortowanej tabeli współczynników dwumianowych. Ta technika jest znacznie szybsza niż starsze opublikowane techniki oparte na iteracji. Robi to za pomocą właściwości matematycznej właściwej Trójkątowi Pascala. Mój artykuł mówi o tym. Wierzę, że jako pierwszy odkryłem i opublikowałem 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 obliczenia współczynnika dwumianowego, 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 występuje) za pomocą ogólnej listy. Konstruktor tej klasy przyjmuje wartość bool o nazwie InitTable, która w przypadku wartości true utworzy ogólną listę przechowującą obiekty do zarządzania. Jeśli ta wartość jest fałszywa, nie utworzy tabeli. Nie trzeba tworzyć tabeli, aby wykonać 4 powyższe metody. 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ł gruntownie przetestowany w 2 przypadkach i nie ma znanych błędów.

Aby przeczytać o tej klasie i pobrać kod, zobacz Tablizing The Binomial Coeffieicent .

Konwersja tej klasy do C ++ nie powinna być trudna.