generar todos los subconjuntos de tamaño k desde un conjunto

Question

Quiero generar todos los subconjuntos de tamaño k de un conjunto.

por ejemplo: -digamos Tengo un conjunto de 6 elementos, tengo que enumerar todos los subconjuntos en el que la cardinalidad de los elementos es 3.

He intentado buscar una solución, pero los que son fragmentos de código. Ha pasado mucho tiempo desde que hice la codificación, por lo que me resulta difícil entender el código y construir un programa ejecutable a su alrededor.

Un programa ejecutable completo en C o C++ será bastante útil. Esperando una solución óptima usando recursividad.

Answer 1

#include <cstdio> 
void g(int s[],int p,int k,int t[],int q=0,int r=0) 
{ 
    if(q==k) 
    { 
     for(int i=0;i<k;i++) 
      printf("%d ",t[i]); 
     printf("\n"); 
    } 
    else 
    { 
     for(int i=r;i<p;i++) 
     { 
      t[q]=s[i]; 
      g(s,p,k,t,q+1,i+1); 
     } 
    } 
} 

main() 
{ 
    int s[]={1,2,3,4,5},t[5]; 
    g(s,5,3,t); 
} 

Answer 2

inicializar una matriz de bits con (1<<nbits)-1 y luego usar este algoritmo:

http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Para los conjuntos más grandes que el tamaño máximo número entero, todavía se puede aplicar el mismo algoritmo para su propio tipo.

Answer 3

El algoritmo más intuitivo usaría recursión. Cuando tienes un conjunto, asumiremos que puedes iterar sobre todos sus elementos.

Si llamo tail (e) a un conjunto de todos los elementos después del elemento e.

Así que quiero ahora combinaciones (s, k)

bucle sobre cada elemento de s y obtener e :: combinaciones (cola (e), k-1) donde :: significa "concatenado a cada uno de "

Por supuesto, a veces no habrá tales combinaciones (está fuera del final de la lista).

Sólo se necesita una colección maestra (conjunto de conjuntos) para añadir sus combinaciones ay una manera de crear

Así que asumiendo que no tenemos globales en cualquier lugar podemos tener algo como:

getCombinations(headset [in], tailset [in], count [in], output [append]) 

auricular o tailset podría estar vacío. count puede ser 0, en cuyo caso escribimos "headset" para la salida (la condición base) de lo contrario iteramos a través de cada elemento en tailset, agregándolo (localmente) a headset, hacemos tailset (localmente) la cola de nuestro elemento, resta 1 de count y "recurse" llamando a la función.

Answer 4

encontrar un código de trabajo inferior a

#include<iostream> 
#include<string> 
#include<list> 

using namespace std; 

void print(list<int> l){ 
    for(list<int>::iterator it=l.begin(); it!=l.end() ; ++it) 
      cout << " " << *it; 
    cout<<endl; 
} 

void subset(int arr[], int size, int left, int index, list<int> &l){ 
    if(left==0){ 
     print(l); 
     return; 
    } 
    for(int i=index; i<size;i++){ 
     l.push_back(arr[i]); 
     subset(arr,size,left-1,i+1,l); 
     l.pop_back(); 
    } 

}  

int main(){ 
    int array[5]={1,2,3,4,5}; 
    list<int> lt; 
    subset(array,5,3,0,lt); 


    return 0; 
} 

Answer 5

Aquí hay algo de pseudocódigo. Puede cortar las mismas llamadas recursivas almacenando los valores de cada llamada sobre la marcha y antes de la comprobación recursiva de llamadas si el valor de la llamada ya está presente.

El siguiente algoritmo tendrá todos los subconjuntos excluyendo el conjunto vacío.

list * subsets(string s, list * v){ 
    if(s.length() == 1){ 
     list.add(s);  
     return v; 
    } 
    else 
    { 
     list * temp = subsets(s[1 to length-1], v);  
     int length = temp->size(); 

     for(int i=0;i<length;i++){ 
      temp.add(s[0]+temp[i]); 
     } 

     list.add(s[0]); 
     return temp; 
    } 
} 

Answer 6

El problema se puede resolver usando recursion. Necesitamos considerar los siguientes casos para recursividad.

1. Se ha elegido el elemento actual.Ahora elegimos recursivamente los elementos restantes k-1 del conjunto restante. (Inclusión)
2. No se ha elegido el elemento actual. Ahora recursivamente elegimos k elementos del conjunto restante. (Exclusión)

A continuación se muestra un programa C++ que muestra el algoritmo anterior.

#include<iostream> 
#include<cstdio> 

using namespace std;  

void KSubset(int *a,int n,int *s,int sindex,int index,int k){ 

    if (index>n) 
     return; 

    if (k==0){ 
     for(int i=0;i<sindex;i++) 
      printf(" %d ",s[i]); 
     printf("\n"); 
     return ; 
     } 

    s[sindex]=a[index]; 
    KSubset(a,n,s,sindex+1,index+1,k-1); 
    KSubset(a,n,s,sindex,index+1,k); 
} 


int main(){ 

    int a[]={1,2,3,4,5}; 
    int s[3]; 
    KSubset(a,5,s,0,0,3); 

    return 0; 
} 

Answer 7

#include <stdio.h> 
#define FIN "subsets.in" 
#define FOUT "subsets.out" 
#define MAXSIZE 100 

void performSubsets(int n, int k){ 

int i, j, s, v[ MAXSIZE ]; 

freopen(FOUT, "w", stdout); 


memset(v, 0, sizeof(v)); 

do { 

    v[ n - 1 ]++; 

    for(i = n - 1; i >= 1; i--) { 

     if(v[ i ] > 1) { 

      v[ i ] -= 2; 

      v[ i - 1 ] += 1; 
     } 
    } 

    s = 0; 

    for(j = 0; j < n; j++) s += v[j]; 

    for(j = 0; j < n; j++) 

     if(v[ j ] && s == k) printf("%d ", (j + 1)); 

    if(s == k) printf("\n"); 

} while(s < n);  

fclose(stdout);  

} 

int main() { 

    int n, k; 

    freopen(FIN, "r", stdin); 

    //read n and size k 
    scanf("%d %d", &n, &k); 

fclose(stdin); 

performSubsets(n,k); 

} 

Este problema se puede resolver utilizando un algoritmo no recursivo.