Algoritmo para devolver todas las combinaciones de k elementos de n

Resuelto Fredrik asked hace 16 años • 77 respuestas

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

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

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

Matrices (o palabras) a su vez que constan de 3 letras cada una.

Fredrik avatar Sep 24 '08 22:09 Fredrik
Aceptado

El arte de la programación informática Volumen 4: Fascículo 3 tiene un montón de estos que podrían adaptarse a su situación particular mejor que como lo describo.

Códigos grises

Un problema con el que te encontrarás es, por supuesto, la memoria y, con bastante rapidez, tendrás problemas con 20 elementos de tu conjunto: 20 C 3 = 1140. Y si quieres iterar sobre el conjunto, es mejor usar un gris modificado. algoritmo de código para que no los guarde todos en la memoria. Estos generan la siguiente combinación a partir 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 artículos originales que describen códigos grises:

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

Aquí hay algunos otros artículos que cubren el tema:

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

Twiddle de Chase (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 515 de Buckles)

También puedes hacer referencia a una combinación por su índice (en orden lexicográfico). Al darnos cuenta de que el índice debería tener cierta cantidad de cambio de derecha a izquierda según el í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 una, en orden y mínima. {1,2,4} tiene un cambio y lexicográficamente es el número 2. Entonces, 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 he descrito es una deconstrucción; al parecer, desde el conjunto hasta el índice, debemos 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 trabajamos desde 0...n. Nota:

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

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

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

El conjunto x_k...x_1 en norteque maximiza i = C(x_1,k) + C(x_2,k-1) + ... + C(x_k,1), donde C(n,r) = {n elige r}.

Para un ejemplo: 27 = C(6,4) + C(5,3) + C(2,2) + C(1,1). Entonces, la combinación lexicográfica número 27 de cuatro cosas es: {1,2,5,6}, esos son los índices de cualquier conjunto que quieras ver. El siguiente ejemplo (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ño y simple.

Los dos algoritmos siguientes se proporcionan con fines didácticos. Implementan combinaciones generales de un iterador y una carpeta (más general). Son lo más rápidos posible y tienen la complejidad O ( n 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 la 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
nlucaroni avatar Sep 24 '2008 15:09 nlucaroni

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
avatar Dec 14 '2009 03:12