Algoritmo para retornar todas as combinações de elementos k de n

Eu quero escrever uma função que leva uma matriz de letras como argumento e um número dessas letras para selecionar.

Digamos que você forneça uma matriz de 8 letras e deseje selecionar 3 delas. Então você deve obter:

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

Matrizes (ou palavras) em troca consistindo em 3 letras cada.

Arte da programação de computadores Volume 4: Fascículo 3 tem uma tonelada dessas que podem se encaixar melhor em sua situação específica do que a que eu descrevo.

Códigos Cinzentos

Um problema que você encontrará é a memória e, rapidamente, você terá problemas em 20 elementos em seu conjunto - ²⁰ C ₃ = 1140. E se você quiser percorrer o conjunto, é melhor usar um cinza modificado algoritmo de código para que você não esteja mantendo todos eles na memória. Eles geram a próxima combinação da anterior e evitam repetições. Existem muitos deles para diferentes usos. Queremos maximizar as diferenças entre combinações sucessivas? minimizar? et cetera.

Alguns dos documentos originais que descrevem códigos em cinza:

1. Alguns caminhos de Hamilton e um algoritmo de mudança mínima
2. Algoritmo de geração de combinação de intercâmbio adjacente

Aqui estão alguns outros artigos que abordam o tópico:

1. Uma implementação eficiente do algoritmo de geração de combinação de intercâmbio adjacente Eades, Hickey, Read (PDF, com código em Pascal)
2. Geradores combinados
3. Pesquisa de códigos combinatórios de cinza (PostScript)
4. Um algoritmo para códigos cinza

Chase's Twiddle (algoritmo)

Phillip J Chase, ` Algoritmo 382: Combinações de M de N Objetos '(1970)

O algoritmo em C ...

Índice de combinações em ordem lexicográfica (algoritmo de curvatura 515)

Você também pode fazer referência a uma combinação por seu índice (em ordem lexicográfica). Percebendo que o índice deve sofrer alguma alteração da direita para a esquerda com base no índice, podemos construir algo que deve recuperar uma combinação.

Então, temos um conjunto {1,2,3,4,5,6} ... e queremos três elementos. Digamos que {1,2,3} podemos dizer que a diferença entre os elementos é uma e em ordem e mínima. {1,2,4} tem uma alteração e é lexicograficamente o número 2. Portanto, o número de 'alterações' no último local é responsável por uma alteração na ordem lexicográfica. O segundo lugar, com uma alteração {1,3,4}, tem uma alteração, mas é responsável por mais alterações, pois fica em segundo lugar (proporcional ao número de elementos no conjunto original).

O método que descrevi é uma desconstrução, ao que parece, do conjunto para o índice, precisamos fazer o inverso - o que é muito mais complicado. É assim que a Buckles resolve o problema. Escrevi C para computá-los , com pequenas alterações - usei o índice dos conjuntos em vez de um intervalo numérico para representar o conjunto, por isso estamos sempre trabalhando de 0 ... n. Nota:

1. Como as combinações são desordenadas, {1,3,2} = {1,2,3} - ordenamos que sejam lexicográficas.
2. Este método possui um 0 implícito para iniciar o conjunto para a primeira diferença.

Índice de combinações em ordem lexicográfica (McCaffrey)

Existe outra maneira : seu conceito é mais fácil de entender e programar, mas sem as otimizações do Buckles. Felizmente, também não produz combinações duplicadas:

O conjunto que maximiza , onde .

Para um exemplo: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Portanto, a 27ª combinação lexicográfica de quatro coisas é: {1,2,5,6}, esses são os índices de qualquer conjunto que você queira examinar. O exemplo abaixo (OCaml) requer choosefunção, deixada para o leitor:

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

Um iterador de combinações pequenas e simples

Os dois algoritmos a seguir são fornecidos para fins didáticos. Eles implementam um iterador e combinações gerais de pastas (mais gerais). Eles são o mais rápido possível, tendo a complexidade O ( ⁿ C _k ). O consumo de memória é limitado por k.

Começaremos com o iterador, que chamará uma função fornecida pelo usuário para cada combinação

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

Uma versão mais geral chamará a função fornecida pelo usuário juntamente com a variável state, iniciando no estado inicial. Como precisamos passar o estado entre estados diferentes, não usaremos o loop for, mas usar recursão,

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

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

Uso:

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

Resultado:

123
124
125
134
135
145
234
235
245
345

Solução Java curta:

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

O resultado será

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

Posso apresentar minha solução Python recursiva para esse problema?

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

Exemplo de uso:

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

Eu gosto pela sua simplicidade.

Digamos que sua matriz de letras fique assim: "ABCDEFGH". Você tem três índices (i, j, k) indicando quais letras você usará para a palavra atual. Você começa com:

ABCDEFGH
^ ^ ^
ijk

Primeiro você varia k, então a próxima etapa é assim:

ABCDEFGH
^ ^ ^
ijk

Se você chegou ao fim, continua e varia j e depois k novamente.

ABCDEFGH
^ ^ ^
ijk

ABCDEFGH
^ ^ ^
ijk

Quando você alcança G, você também começa a variar i.

ABCDEFGH
  ^ ^ ^
  ijk

ABCDEFGH
  ^ ^ ^
  ijk
...

Escrito em código isso parece algo assim

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

O seguinte algoritmo recursivo seleciona todas as combinações de elementos k de um conjunto ordenado:

• escolha o primeiro elemento ida sua combinação
• combine icom cada uma das combinações de k-1elementos escolhidos recursivamente do conjunto de elementos maior que i.

Repita o procedimento acima para cada um ino conjunto.

É essencial que você escolha o restante dos elementos como maior que i, para evitar repetições. Dessa forma, [3,5] será escolhido apenas uma vez, como [3] combinado com [5], em vez de duas vezes (a condição elimina [5] + [3]). Sem essa condição, você obtém variações em vez de combinações.

Em C ++, a seguinte rotina produzirá todas as combinações de distância de comprimento (primeiro, k) entre o intervalo [primeiro, último):

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

Pode ser usado assim:

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

Isso imprimirá o seguinte:

123
124
125
134
135
145
234
235
245
345

Achei este tópico útil e pensei em adicionar uma solução Javascript que você possa acessar no Firebug. Dependendo do seu mecanismo JS, pode demorar um pouco se a sequência inicial for grande.

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

A saída deve ser a seguinte:

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

Pequeno exemplo em 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

Para explicação, o método recursivo é descrito com o seguinte exemplo:

Exemplo: ABCDE
Todas as combinações de 3 seriam:

• A com todas as combinações de 2 do resto (BCDE)
• B com todas as combinações de 2 do resto (CDE)
• C com todas as combinações de 2 do resto (DE)

Algoritmo recursivo simples em Haskell

import Data.List

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

Primeiro, definimos o caso especial, ou seja, a seleção de zero elementos. Produz um único resultado, que é uma lista vazia (ou seja, uma lista que contém uma lista vazia).

Para n> 0, xpercorre todos os elementos da lista e xstodos os elementos apósx .

restescolhe n - 1elementos do xsuso de uma chamada recursiva para combinations. O resultado final da função é uma lista em que cada elemento está x : rest(ou seja, uma lista que tem xcomo cabeçalho e restcomo cauda) para cada valor diferente de xe rest.

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

E, é claro, como Haskell é preguiçoso, a lista é gerada gradualmente conforme necessário, para que você possa avaliar parcialmente combinações exponencialmente grandes.

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

E aqui vem o avô COBOL, a linguagem muito difamada.

Vamos assumir uma matriz de 34 elementos de 8 bytes cada (seleção puramente arbitrária). A idéia é enumerar todas as combinações possíveis de 4 elementos e carregá-las em uma matriz.

Utilizamos 4 índices, um para cada posição no grupo de 4

A matriz é processada assim:

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

Nós variamos idx4 de 4 até o final. Para cada idx4, obtemos uma combinação única de grupos de quatro. Quando o idx4 chega ao final da matriz, incrementamos o idx3 em 1 e configuramos o idx4 como idx3 + 1. Então rodamos o idx4 até o fim novamente. Prosseguimos dessa maneira, aumentando idx3, idx2 e idx1, respectivamente, até que a posição de idx1 seja menor que 4 do final da matriz. Isso termina o algoritmo.

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

Primeiras iterações:

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

Um exemplo de 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.

Aqui está uma implementação elegante e genérica no Scala, conforme descrito em 99 Scala Problems .

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

Se você pode usar a sintaxe SQL - por exemplo, se estiver usando o LINQ para acessar campos de uma estrutura ou matriz ou acessando diretamente um banco de dados que possui uma tabela chamada "Alfabeto" com apenas um campo de caracteres "Carta", você pode adaptar-se a seguir código:

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

Isso retornará todas as combinações de 3 letras, não obstante quantas letras você tenha na tabela "Alfabeto" (pode ser 3, 8, 10, 27, etc.).

Se o que você deseja são todas permutações, em vez de combinações (ou seja, você deseja que "ACB" e "ABC" sejam contados como diferentes, em vez de aparecer apenas uma vez), exclua a última linha (a AND) e está pronta.

Pós-edição: Depois de reler a pergunta, percebo que o necessário é o algoritmo geral , não apenas um específico para o caso de seleção de 3 itens. A resposta de Adam Hughes é a completa, infelizmente ainda não posso votar. Essa resposta é simples, mas funciona apenas para quando você deseja exatamente 3 itens.

Outra versão C # com geração lenta dos índices de combinação. Esta versão mantém uma única matriz de índices para definir um mapeamento entre a lista de todos os valores e os valores da combinação atual, ou seja, constantemente usa O (k) espaço adicional durante todo o tempo de execução. O código gera combinações individuais, incluindo a primeira, em 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;
        }
    }
}

Código do teste:

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

Resultado:

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

Existe uma implementação para JavaScript. Possui funções para obter combinações k e todas as combinações de uma matriz de qualquer objeto. Exemplos:

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

Aqui você tem uma versão avaliada preguiçosa desse algoritmo codificado em 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));
        }
    }

E peça de teste:

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

Espero que isso ajude você!

Eu tinha um algoritmo de permutação que usei para o projeto euler, em 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

E se

n<len(l) 

você deve ter todas as combinações necessárias sem repetição, precisa?

É um gerador, então você o usa em algo assim:

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

Versão 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))))

Digamos que sua matriz de letras fique assim: "ABCDEFGH". Você tem três índices (i, j, k) indicando quais letras você usará para a palavra atual. Você começa com:

ABCDEFGH
^ ^ ^
ijk

Primeiro você varia k, então a próxima etapa é assim:

ABCDEFGH
^ ^ ^
ijk

Se você chegou ao fim, continua e varia j e depois k novamente.

ABCDEFGH
^ ^ ^
ijk

ABCDEFGH
^ ^ ^
ijk

Quando você alcança G, você também começa a variar 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);

Com base em https://stackoverflow.com/a/127898/2628125 , mas mais abstrato, para qualquer tamanho de ponteiro.

Tudo dito e feito aqui vem o código O'caml para isso. Algoritmo é evidente a partir do código ..

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

Aqui está um método que fornece todas as combinações de tamanho especificado a partir de uma sequência de comprimento aleatório. Semelhante à solução dos quinmars, mas funciona para entradas variadas e k.

O código pode ser alterado para contornar, ou seja, 'dab' da entrada '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);
    }
}

Saída para "abcde":

abc abd abe acd ace ade bcd bce bde cde

código python curto, gerando posições de índice

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

Criei uma solução no SQL Server 2005 para isso e publiquei no meu site: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Aqui está um exemplo para mostrar o uso:

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

resultados:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Aqui está minha proposição em C ++

Tentei impor o mínimo de restrição possível ao tipo de iterador, portanto esta solução assume apenas o iterador para a frente e pode ser um const_iterator. Isso deve funcionar com qualquer contêiner padrão. Nos casos em que os argumentos não fazem sentido, lança 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));
    }
}

Aqui está um código que escrevi recentemente em Java, que calcula e retorna toda a combinação de elementos "num" de elementos "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);
    }
}

Uma solução Javascript concisa:

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

Algoritmo:

• Conte de 1 a 2 ^ n.
• Converta cada dígito em sua representação binária.
• Traduza cada bit 'on' para elementos do seu conjunto, com base na posição.

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

Por que isso funciona?

Há uma bijeção entre os subconjuntos de um conjunto de elementos n e seqüências de n bits.

Isso significa que podemos descobrir quantos subconjuntos existem contando seqüências.

por exemplo, o conjunto de quatro elementos abaixo pode ser representado por {0,1} X {0, 1} X {0, 1} X {0, 1} (ou 2 ^ 4) diferentes seqüências.

Então - tudo o que precisamos fazer é contar de 1 a 2 ^ n para encontrar todas as combinações. (Ignoramos o conjunto vazio.) Em seguida, traduza os dígitos para sua representação binária. Em seguida, substitua os elementos do seu conjunto por bits 'on'.

Se você deseja apenas resultados do elemento k, imprima apenas quando k bits estiverem 'ativados'.

(Se você deseja todos os subconjuntos, em vez de k length, remova a parte cnt / kElement.)

(Para comprovação, consulte os cursos gratuitos do MIT, Matemática para Ciência da Computação, Lehman et al, seção 11.2.2. Https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- for-computer-science-fall-2010 / leituras / )

Eu escrevi uma classe para lidar com funções comuns para trabalhar com o coeficiente binomial, que é o tipo de problema em que seu problema se enquadra. Ele executa as seguintes tarefas:

1. Produz todos os índices K em um bom formato para qualquer N, escolha K em um arquivo. Os índices K podem ser substituídos por seqüências ou letras mais descritivas. Esse método torna a solução desse tipo de problema bastante trivial.

2. Converte os índices K no índice adequado de uma entrada na tabela de coeficientes binomiais classificados. Essa técnica é muito mais rápida que as técnicas publicadas mais antigas que dependem da iteração. Isso é feito usando uma propriedade matemática inerente ao Triângulo de Pascal. Meu trabalho fala sobre isso. Acredito que sou o primeiro a descobrir e publicar essa técnica, mas posso estar errado.

3. Converte o índice em uma tabela de coeficiente binomial classificado nos índices K correspondentes.

4. Usa o método Mark Dominus para calcular o coeficiente binomial, que tem muito menos probabilidade de transbordar e funciona com números maiores.

5. A classe é escrita no .NET C # e fornece uma maneira de gerenciar os objetos relacionados ao problema (se houver) usando uma lista genérica. O construtor dessa classe usa um valor bool chamado InitTable que, quando true, criará uma lista genérica para armazenar os objetos a serem gerenciados. Se esse valor for falso, ele não criará a tabela. A tabela não precisa ser criada para executar os 4 métodos acima. Métodos de assessor são fornecidos para acessar a tabela.

6. Existe uma classe de teste associada que mostra como usar a classe e seus métodos. Foi extensivamente testado com 2 casos e não há bugs conhecidos.

Para ler sobre esta classe e fazer o download do código, consulte Tablizing The Binomial Coeffieicent .

Não deve ser difícil converter essa classe para C ++.