Dada una matriz de tamaño n, ¿cómo encuentra todos los subconjuntos posibles de la matriz de tamaño k?

EDITAR: Gracias a los comentarios de los usuarios de Quora.

En primer lugar, elimine los duplicados de la matriz ordenándolos o su método de eliminación de duplicados favorito.
Deje que el tamaño de la matriz filtrada sea la nueva ‘n’.
Ahora el problema dado es el mismo que encontrar todos los números de k dígitos en la base n (o con radix n) pero no repetir ninguno de los dígitos.
Esto se puede hacer generando todos los números desde [matemática] n ^ k [/ matemática] a [matemática] n ^ {k + 1} -1 [/ matemática] en la raíz n y excluyendo los números con dígitos replicados que pueden ser hecho en [matemáticas] O \ left (n ^ {k + 1} \ right) [/ math]
Por ejemplo, n = 10 & k siendo 3, queremos que se repitan todos los números del 100 al 999 sin un dígito, es decir, 123,124,125,126, .. 985,986,987. El problema según lo dicho por Quora User es que da como resultado una permutación redundante como 123,132,213,231,312 y 321 que dan el mismo conjunto. Una forma de eliminarlos y acelerar la iteración será que cada vez que encuentre dos dígitos en el número generado que sean iguales, diga [math] i ^ {th} [/ math] y [math] j ^ {th} [ / matemático] desde la derecha (es decir, desde el lugar de la unidad) con [matemática] i> j [/ matemática], luego incremente el dígito [matemático] i ^ {th} [/ matemático] en 1 y establezca los dígitos desde el [matemático ] j ^ {th} [/ math] al primer dígito con la secuencia [math] j-1, j-2, .. 0 [/ math]. De esta manera, tenemos la garantía de generar un nuevo número válido después de cada k iteración. Por lo tanto, la resolución en tiempo de ejecución de [matemáticas] O \ left (k \ cdot n \ cdot \ binom {n} {k} \ right) [/ math] (n para manipular todos los dígitos al encontrar un número con dígitos repetidos, puede ser reducido a O (1) mediante el uso de una operación memset de secuencias de bits ya calculadas y almacenadas para tales operaciones o utilizando una representación de número personalizada como se hizo en el enfoque 2).

Puede implementarlo de dos maneras:
Enfoque 1 (Fácil pero está limitado a [matemáticas] n ^ {k + 1} -1 [/ matemáticas] es menor que
El valor int máximo para su idioma también incurre en un registro adicional (n)
factor para la conversión de base)

• A partir de i = [matemática] n ^ k [/ matemática] convierta el número a la raíz n por división de módulo
• si el número de número convertido tiene un dígito repetido, diga [math] i ^ {th} [/ math] y [math] j ^ {th} [/ math] dígito desde la derecha (es decir, del lugar de la unidad) con [math] i> j [/ math], luego incremente el dígito [math] i ^ {th} [/ math] en 1 y establezca los dígitos de [math] j ^ {th} [/ math] al primer dígito con la secuencia [ matemáticas] j-1, j-2, .. 0 [/ matemáticas]. de lo contrario, guarde sus dígitos en una matriz 2D de tamaño [math] \ binom {n} {k} [/ math] * k para mantener el índice de elementos de todos los subconjuntos.
• siga los dos pasos anteriores para i + 1 hasta que obtenga toda la permutación, es decir, si se convierte en [matemáticas] \ binom {n} {k} [/ matemáticas]

El siguiente código será una mejor ilustración (se actualizará para avanzar en la búsqueda de un dígito repetido)

  subconjuntos int [nCk] [K];  // matriz para contener los índices de los subconjuntos
     bool valid_i, dup_hit [N];  // dup_hit es una matriz de resultados para verificar si el número evaluado tiene un dígito duplicado   
     int i, j, si, sk, rem, N_min, N_max, n, k;
     N_min = ipow (N, K);  // n elevado al poder k   
     N_max = ipow (N, K + 1);  // n elevado al poder k + 1 
     si = 0;
     para (i = N_min; i  0)
         {
            rem = j% N;
            if (dup_hit [rem])
                {
                válido_i = falso;  // no es un subconjunto válido
                descanso;
                }
            dup_hit [rem] = verdadero;  // establece la aparición de este dígito como verdadero.   
            subconjuntos [si] [sk] = rem;
            j = j / N;                              
            ++ sk;  // incrementa el lugar del dígito
            
         }
         if (válido_i) ++ si;  // si el último número fue válido, entonces incremente si
     }

     devuelve 0;

El enfoque 2 consistirá en diseñar su propia implementación del número n-radix con n siendo una entrada utilizando una lista vinculada de vectores de n bits y realizando una aritmética simple de incremento de 1 en él. Usando esta estructura de datos, resolverá cualquier valor de n & k. Supongo que puede acelerar las iteraciones incrementando el valor del número en el lugar más alto de los dos lugares que comparten el mismo número y luego estableciendo el lugar del dígito inferior, digamos jth desde la derecha con j-1 y los derechos con j-2, j-3, j-4 .., 0

Ejecute este código en Turbo Prolog para obtener subconjuntos de una matriz de longitud k

  dominios
 i = entero
 l = i *

 predicados
 subs (i, l, l)
 succ (i, i)

 cláusulas
 succ (X, Y): - X = Y-1.

 subs (0, [], []).
 subs (Len, [E | Tail], [E | NTail]): - succ (PLen, Len), PLen> 0, subs (PLen, Tail, NTail); NTail = [].
 subs (Len, [_ | Tail], NTail): - subs (Len, Tail, NTail). 

Ejemplo:

  Objetivo: subs (2, [1,2,3], X)
 X = [1,2]
 X = [1,3]
 X = [1]
 X = [2,3]
 X = [2]
 X = [3]
 6 soluciones 

(nota: Esto todavía da un subconjunto de longitud

Aquí está mi enfoque. Comienzo generando todos los subconjuntos posibles y luego imprimiendo aquellos que tienen un tamaño k.

Por ejemplo, A = {1,2,3}

Como tenemos 3 elementos, ejecutamos un ciclo de 0 a (2 ^ 3) -1.

echemos un vistazo a la representación binaria de cada número.

0 000

1 001

2 010

3 011

4 100

5 101

6 110

7 111

Ahora la lógica se ejecuta en forma de bucle 0 a (2 ^ 3) -1 y para cada elemento imprima ese elemento que tiene 1 en su índice correspondiente.

entonces para

0 000 {}

1 001 {3}

2 010 {2}

3 011 {2,3}

4 100 {1}

5 101 {1,3}

6 110 {1,2}

7 111 {1,2,3}

Así es como generamos todos los subconjuntos de un conjunto. Claramente para imprimir subconjuntos de tamaño k tomaremos solo aquellos números que tienen número de unos en su representación binaria número = k.

código en

http://ideone.com/Uc8i0a

Aquí está mi solución al problema anterior

  import java.util.ArrayList;
 import java.util.HashSet;
 import java.util.Set;


 Subconjunto_K de clase pública {
     public static void main (String [] args)
     {
         Establecer  x;
         int n = 4;
         int k = 2;
         int arr [] = {1,2,3,4};
         StringBuilder sb = new StringBuilder ();
         para (int i = 1; i <= (nk); i ++)
             sb.append ("0");
         para (int i = 1; i <= k; i ++)
             sb.append ("1");
         Cadena bin = sb.toString ();
         x = generatePerm (bin);
         Establezca > external = new HashSet > ();
         para (Cadena s: x) {
             int dec = Integer.parseInt (s, 2);
             ArrayList 

Estoy trabajando en un conjunto de 4 elementos para fines de prueba y uso k = 2.
Lo que intento hacer es generar inicialmente una cadena binaria en la que se establezcan k bits y nk bits (en este caso "0011"). Ahora, usando esta cadena, encuentro todas las permutaciones posibles (más bien combinaciones) de esta cadena. Y luego, usando estas permutaciones (1100,1001,0101, etc.), saco el elemento respectivo en el conjunto. Creo que este algo se ejecuta en O (C (n, k)).