algorithm - tomados - Algoritmo para devolver todas las combinaciones de k elementos de n




permutaciones y combinaciones (20)

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

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

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

Arreglos (o palabras) a cambio consisten de 3 letras cada uno.


¿Puedo presentar mi solución de Python recursiva 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 sencillez.


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, seleccionando cero elementos. Produce un solo resultado, que es una lista vacía (es decir, una lista que contiene una lista vacía).

Para n> 0, x recorre todos los elementos de la lista y xs es cada elemento después de x .

rest escoge n - 1 elementos de xs usando 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 x como cabeza y rest como cola) para cada valor diferente de x y rest .

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

Y, por supuesto, dado que Haskell es perezoso, 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"]

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

object P26 {
  def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] = 
    ls match {
      case Nil => Nil
      case [email protected](_ :: 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 :: _}
    }
}

Aquí tienes una versión perezosa 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 prueba parte:

    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!



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

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

Primero debes variar k, entonces el siguiente paso se ve así:

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

Si llegó al final, continúe y varíe j y luego k nuevamente.

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

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

Una vez que alcanzas G, comienzas también a variar i.

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

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

Escrito en código este look algo 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]);
        }
    }
}

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

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

  • Elige el primer elemento i de tu combinación.
  • combine i con cada una de las combinaciones de elementos k-1 elegidos recursivamente del conjunto de elementos más grandes que i .

Iterar lo anterior para cada i en el conjunto.

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


Encontré este hilo útil y pensé que agregaría una solución de Javascript que pueda aparecer en Firebug. Dependiendo de su motor JS, podría tomar 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");

La salida debe ser la siguiente:

abc
ab
ac
a
bc
b
c

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

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]

Tuve un algoritmo de permutación que utilicé 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) 

Debes tener toda la combinación que necesites sin repetición, ¿la necesitas?

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

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

Y aquí viene el abuelo COBOL, el lenguaje tan 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 configuramos idx4 en idx3 + 1. Luego volvemos a ejecutar idx4 hasta el final. 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.

Art of Computer Programming Volume 4: Fascicle 3 tiene una tonelada de estos que podrían adaptarse a su situación particular mejor de lo que describo.

Códigos grises

Por supuesto, un problema con el que se encontrará es la memoria y bastante rápido, tendrá 20 problemas en su conjunto: 20 C 3 = 1140. Y si desea recorrer el conjunto, es mejor usar un gris modificado. Algoritmo de código para que no los guardes 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 papeles 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 de combinación de intercambio de lectura adyacente de Eades, Hickey (PDF, con código en Pascal)
  2. Generadores de combinacion
  3. Encuesta 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 N (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 darse cuenta de que el índice debe ser una 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 que {1,2,3} podemos decir que la diferencia entre los elementos es de 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 da cuenta de un cambio en el ordenamiento lexicográfico. El segundo lugar, con un cambio {1,3,4} tiene un cambio, pero representa un cambio mayor 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, como parece, desde el conjunto hasta el í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 pequeños cambios. Usé 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 manera :, su concepto es más fácil de entender y programar, pero sin las optimizaciones de Buckles. Afortunadamente, tampoco produce combinaciones duplicadas:

El conjunto que maximiza , dónde .

Por 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 quieras ver. El siguiente ejemplo (OCaml), requiere la función de choose , 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)

Algoritmo:

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

Cía#:

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 qué funciona?

Existe una bijección entre los subconjuntos de un conjunto de n elementos y secuencias de n bits.

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

por ejemplo, el conjunto de cuatro elementos a continuación se puede representar 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 sustituye los elementos de tu conjunto por bits "on".

Si solo desea resultados de k elementos, solo imprima 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 la prueba, consulte el material didáctico 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-for-computer-science-fall-2010/readings/ )


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

Aquí hay un método que le da 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 ajustarlo, 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 abe acd as ade bcd bce bde cde


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

  1. Muestra todos los índices K en un formato agradable para cualquier N, elija K para 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 al í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 antiguas que se basan en la iteración. Lo hace usando una propiedad matemática inherente en el Triángulo de Pascal. Mi papel 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 de coeficientes binomiales ordenados a los índices K correspondientes.

  4. Utiliza el método de 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 existe) mediante el uso de una lista genérica. El constructor de esta clase toma un valor bool llamado InitTable que, cuando verdadero, creará una lista genérica para contener los objetos que se administrarán. Si este valor es falso, entonces 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 probado extensivamente con 2 casos y no hay errores conocidos.

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

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


Todo lo dicho y hecho aquí viene el código de O'caml para eso. El algoritmo es evidente a partir del 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 []
;;

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






combinations