Algoritmo para devolver todas las combinaciones de k elementos de n

Quiero escribir una función que tome una matriz de letras como argumento y varias de esas letras para seleccionar.

Supongamos que proporciona una matriz de 8 letras y desea seleccionar 3 letras de eso. Entonces deberías obtener:

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

Matrices (o palabras) a cambio que consisten en 3 letras cada una.

Arte de la programación de computadoras Volumen 4: el Fascículo 3 tiene un montón de estos que podrían adaptarse mejor a su situación particular de lo que describo.

Códigos grises

Un problema que encontrará es, por supuesto, la memoria y bastante rápido, tendrá problemas con 20 elementos en su conjunto: ²⁰ C ₃ = 1140. Y si desea iterar sobre el conjunto, es mejor usar un gris modificado algoritmo de código para que no los tenga todos en la memoria. Estos generan la siguiente combinación de la anterior y evitan repeticiones. Hay muchos de estos para diferentes usos. ¿Queremos maximizar las diferencias entre combinaciones sucesivas? ¿minimizar? etcétera.

Algunos de los documentos originales que describen códigos grises:

1. Algunas rutas de Hamilton y un algoritmo de cambio mínimo
2. Algoritmo de generación de combinación de intercambio adyacente

Aquí hay algunos otros documentos que cubren el tema:

1. Una implementación eficiente del algoritmo de generación combinada de intercambio adyacente de Eades, Hickey y lectura (PDF, con código en Pascal)
2. Generadores Combinados
3. Encuesta de códigos combinados grises (PostScript)
4. Un algoritmo para códigos grises

Chase's Twiddle (algoritmo)

Phillip J Chase, ` Algoritmo 382: Combinaciones de M de N objetos '(1970)

El algoritmo en C ...

Índice de combinaciones en orden lexicográfico (algoritmo de hebillas 515)

También puede hacer referencia a una combinación por su índice (en orden lexicográfico). Al darnos cuenta de que el índice debería ser una cantidad de cambio de derecha a izquierda en función del índice, podemos construir algo que debería recuperar una combinación.

Entonces, tenemos un conjunto {1,2,3,4,5,6} ... y queremos tres elementos. Digamos {1,2,3} podemos decir que la diferencia entre los elementos es uno y en orden y mínima. {1,2,4} tiene un cambio y es lexicográficamente el número 2. Por lo tanto, el número de 'cambios' en el último lugar representa un cambio en el orden lexicográfico. El segundo lugar, con un cambio {1,3,4} tiene un cambio, pero representa más cambios ya que está en el segundo lugar (proporcional al número de elementos en el conjunto original).

El método que describí es una deconstrucción, como parece, desde el conjunto al índice, necesitamos hacer lo contrario, lo cual es mucho más complicado. Así es como Buckles resuelve el problema. Escribí algo de C para calcularlos , con cambios menores: utilicé el índice de los conjuntos en lugar de un rango de números para representar el conjunto, por lo que siempre estamos trabajando desde 0 ... n. Nota:

1. Como las combinaciones no están ordenadas, {1,3,2} = {1,2,3} - ordenamos que sean lexicográficas.
2. Este método tiene un 0 implícito para iniciar el conjunto de la primera diferencia.

Índice de combinaciones en orden lexicográfico (McCaffrey)

Hay otra forma : su concepto es más fácil de entender y programar, pero no tiene las optimizaciones de Buckles. Afortunadamente, tampoco produce combinaciones duplicadas:

El conjunto que maximiza , dónde .

Para un ejemplo: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Entonces, la 27ª combinación lexicográfica de cuatro cosas es: {1,2,5,6}, esos son los índices de cualquier conjunto que desee ver. Ejemplo a continuación (OCaml), requiere choosefunción, se deja al lector:

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

Un iterador de combinaciones pequeñas y simples

Los siguientes dos algoritmos se proporcionan con fines didácticos. Implementan un iterador y combinaciones generales de carpetas (más generales). Son lo más rápidos posible, tienen la complejidad O ( ⁿ C _k ). El consumo de memoria está limitado por k.

Comenzaremos con el iterador, que llamará a una función proporcionada por el usuario para cada combinación

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

Una versión más general llamará a la función proporcionada por el usuario junto con la variable de estado, comenzando desde el estado inicial. Como necesitamos pasar el estado entre diferentes estados, no usaremos el bucle for, sino que usaremos recursividad,

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

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

Solución java corta:

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

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

¿Puedo presentar mi solución recursiva de Python a este 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))

Ejemplo de uso:

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

Me gusta por su simplicidad.

Digamos que su conjunto de letras se ve así: "ABCDEFGH". Tiene tres índices (i, j, k) que indican qué letras va a utilizar para la palabra actual. Comienza con:

ABCDEFGH
^ ^ ^
ijk

Primero varía k, por lo que el siguiente paso se ve así:

ABCDEFGH
^ ^ ^
ijk

Si llegaste al final, continúas y varías j y luego k nuevamente.

ABCDEFGH
^ ^ ^
ijk

ABCDEFGH
^ ^ ^
ijk

Una vez que j llegó a G, comienza a variar también i.

ABCDEFGH
  ^ ^ ^
  ijk

ABCDEFGH
  ^ ^ ^
  ijk
...

Escrito en código esto se ve así

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

El siguiente algoritmo recursivo selecciona todas las combinaciones de elementos k de un conjunto ordenado:

• elige el primer elemento ide tu combinación
• combine icon cada una de las combinaciones de k-1elementos elegidos recursivamente del conjunto de elementos mayores que i.

Iterar lo anterior para cada i en el conjunto.

Es esencial que elija el resto de los elementos como más grandes ipara evitar repeticiones. De esta forma, [3,5] se seleccionará solo una vez, ya que [3] se combinará con [5], en lugar de dos veces (la condición elimina [5] + [3]). Sin esta condición, obtienes variaciones en lugar de combinaciones.

En C ++, la siguiente rutina producirá todas las combinaciones de distancia de longitud (primero, k) entre el rango [primero, ú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;
}

Se puede usar así:

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

Esto imprimirá lo siguiente:

123
124
125
134
135
145
234
235
245
345

Encontré este hilo útil y pensé que agregaría una solución de Javascript que puede introducir en Firebug. Dependiendo de su motor JS, podría llevar un poco de tiempo si la cadena de inicio es 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");

El resultado debe ser el siguiente:

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

Breve ejemplo en 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 explicación, el método recursivo se describe con el siguiente ejemplo:

Ejemplo: ABCDE
Todas las combinaciones de 3 serían:

• A con todas las combinaciones de 2 del resto (BCDE)
• B con todas las combinaciones de 2 del resto (CDE)
• C con todas las combinaciones de 2 del resto (DE)

Algoritmo recursivo simple en Haskell

import Data.List

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

Primero definimos el caso especial, es decir, seleccionamos cero elementos. Produce un único resultado, que es una lista vacía (es decir, una lista que contiene una lista vacía).

Para n> 0, xrecorre cada elemento de la lista y xses cada elemento posterior x.

restselecciona n - 1elementos del xsuso de una llamada recursiva a combinations. El resultado final de la función es una lista donde cada elemento es x : rest( es decir, una lista que tiene xcomo cabeza y restcomo cola) para cada valor diferente de xy rest.

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

Y, por supuesto, dado que Haskell es vago, la lista se genera gradualmente según sea necesario, por lo que puede evaluar parcialmente combinaciones exponencialmente grandes.

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

Y aquí viene el abuelo COBOL, el lenguaje muy difamado.

Supongamos una matriz de 34 elementos de 8 bytes cada uno (selección puramente arbitraria). La idea es enumerar todas las combinaciones posibles de 4 elementos y cargarlas en una matriz.

Utilizamos 4 índices, uno para cada posición en el grupo de 4

La matriz se procesa así:

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

Variamos idx4 desde 4 hasta el final. Para cada idx4 obtenemos una combinación única de grupos de cuatro. Cuando idx4 llega al final de la matriz, incrementamos idx3 en 1 y establecemos idx4 en idx3 + 1. Luego ejecutamos idx4 hasta el final nuevamente. Procedemos de esta manera, aumentando idx3, idx2 e idx1 respectivamente hasta que la posición de idx1 sea inferior a 4 desde el final de la matriz. Eso termina el algoritmo.

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

Primeras iteraciones:

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

Un ejemplo 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.

Aquí hay una implementación elegante y genérica en Scala, como se describe en 99 Problemas de Scala .

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

Si puede usar la sintaxis SQL, por ejemplo, si está usando LINQ para acceder a los campos de una estructura o matriz, o está accediendo directamente a una base de datos que tiene una tabla llamada "Alfabeto" con un solo campo de caracteres "Letra", puede adaptar lo siguiente 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

Esto devolverá todas las combinaciones de 3 letras, independientemente de cuántas letras tenga en la tabla "Alfabeto" (puede ser 3, 8, 10, 27, etc.).

Si lo que desea son todas las permutaciones, en lugar de combinaciones (es decir, desea que "ACB" y "ABC" cuenten como diferentes, en lugar de aparecer solo una vez), simplemente elimine la última línea (la Y) y listo.

Post-Edición: después de volver a leer la pregunta, me doy cuenta de que lo que se necesita es el algoritmo general , no solo uno específico para el caso de seleccionar 3 elementos. La respuesta de Adam Hughes es completa, desafortunadamente no puedo votarla (todavía). Esta respuesta es simple pero solo funciona cuando quieres exactamente 3 elementos.

Otra versión de C # con generación perezosa de los índices de combinación. Esta versión mantiene una única matriz de índices para definir un mapeo entre la lista de todos los valores y los valores para la combinación actual, es decir, usa constantemente espacio adicional O (k) durante todo el tiempo de ejecución. El código genera combinaciones individuales, incluida la primera, en el tiempo 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 de prueba:

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

Salida:

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

Hay una implementación para JavaScript. Tiene funciones para obtener combinaciones k y todas las combinaciones de una matriz de cualquier objeto. Ejemplos:

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

Aquí tiene una versión perezosa evaluada de ese algoritmo codificada en 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));
        }
    }

Y parte de prueba:

    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 esto te ayude!

Tenía un algoritmo de permutación que usé para el proyecto euler, en 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

Si

n<len(l) 

deberías tener toda la combinación que necesitas sin repetición, ¿la necesitas?

Es un generador, así que lo usa en algo como esto:

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

Versión 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 su conjunto de letras se ve así: "ABCDEFGH". Tiene tres índices (i, j, k) que indican qué letras va a utilizar para la palabra actual. Comienza con:

ABCDEFGH
^ ^ ^
ijk

Primero varía k, por lo que el siguiente paso se ve así:

ABCDEFGH
^ ^ ^
ijk

Si llegaste al final, continúas y varías j y luego k nuevamente.

ABCDEFGH
^ ^ ^
ijk

ABCDEFGH
^ ^ ^
ijk

Una vez que j llegó a G, comienza a variar también 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);

Basado en https://stackoverflow.com/a/127898/2628125 , pero más abstracto, para cualquier tamaño de punteros.

Todo dicho y hecho aquí viene el código O'caml para eso. Algoritmo es evidente por el 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 []
;;

Aquí hay un método que le brinda todas las combinaciones de tamaño especificado de una cadena de longitud aleatoria. Similar a la solución de quinmars, pero funciona para entradas variadas y k.

El código se puede cambiar para envolver, es decir, 'dab' de la 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);
    }
}

Salida para "abcde":

abc abd abe acd as ade bcd bce bde cde

código corto de Python, produciendo posiciones 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

Creé una solución en SQL Server 2005 para esto y la publiqué en mi sitio web: http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm

Aquí hay un ejemplo para mostrar el uso:

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

resultados:

Word
----
AB
AC
AD
BC
BD
CD

(6 row(s) affected)

Aquí está mi propuesta en C ++

Intenté imponer tan poca restricción en el tipo de iterador como pude, por lo que esta solución asume solo el iterador directo, y puede ser un const_iterator. Esto debería funcionar con cualquier contenedor estándar. En casos donde los argumentos no tienen sentido, arroja 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));
    }
}

Aquí hay un código que escribí recientemente en Java, que calcula y devuelve toda la combinación de elementos "num" a partir 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);
    }
}

Una solución concisa de 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);

Algoritmo:

• Cuenta de 1 a 2 ^ n.
• Convierta cada dígito en su representación binaria.
• Traduce cada bit 'on' a elementos de tu conjunto, según la posición.

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 funciona

Hay una biyección entre los subconjuntos de un conjunto de elementos n y secuencias de n bits.

Eso significa que podemos calcular cuántos subconjuntos hay contando secuencias.

por ejemplo, el conjunto de cuatro elementos a continuación puede representarse mediante {0,1} X {0, 1} X {0, 1} X {0, 1} (o 2 ^ 4) secuencias diferentes.

Entonces, todo lo que tenemos que hacer es contar de 1 a 2 ^ n para encontrar todas las combinaciones.(Ignoramos el conjunto vacío). Luego, traduzca los dígitos a su representación binaria. Luego, sustituya los elementos de su conjunto por bits 'on'.

Si solo desea resultados de k elementos, imprima solo cuando k bits estén 'activados'.

(Si desea todos los subconjuntos en lugar de los subconjuntos de longitud k, elimine la parte cnt / kElement).

(Para ver una prueba, consulte el curso gratuito MIT Mathematics for Computer Science, Lehman et al, sección 11.2.2. Https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics- para-informática-otoño-2010 / lecturas / )

He escrito una clase para manejar funciones comunes para trabajar con el coeficiente binomial, que es el tipo de problema en el que se encuentra su problema. Realiza las siguientes tareas:

1. Emite todos los índices K en un formato agradable para cualquier N, elija K en un archivo. Los índices K pueden sustituirse por cadenas o letras más descriptivas. Este método hace que resolver este tipo de problema sea bastante trivial.

2. Convierte los índices K en el índice adecuado de una entrada en la tabla de coeficientes binomiales ordenados. Esta técnica es mucho más rápida que las técnicas publicadas más antiguas que se basan en la iteración. Lo hace usando una propiedad matemática inherente al Triángulo de Pascal. Mi artículo habla de esto. Creo que soy el primero en descubrir y publicar esta técnica, pero podría estar equivocado.

3. Convierte el índice en una tabla ordenada de coeficientes binomiales a los índices K correspondientes.

4. Utiliza el método Mark Dominus para calcular el coeficiente binomial, que es mucho menos probable que se desborde y funciona con números más grandes.

5. La clase está escrita en .NET C # y proporciona una forma de administrar los objetos relacionados con el problema (si corresponde) mediante una lista genérica. El constructor de esta clase toma un valor bool llamado InitTable que, cuando sea verdadero, creará una lista genérica para contener los objetos a administrar. Si este valor es falso, no creará la tabla. No es necesario crear la tabla para realizar los 4 métodos anteriores. Se proporcionan métodos de acceso para acceder a la tabla.

6. Hay una clase de prueba asociada que muestra cómo usar la clase y sus métodos. Ha sido ampliamente probado con 2 casos y no hay errores conocidos.

Para leer sobre esta clase y descargar el código, vea Tablizing The Binomial Coeffieicent .

No debería ser difícil convertir esta clase a C ++.