Autor Tema: Generar Subconjuntos de tamaño m de un conjutno (Leído 6560 veces)

protoculo · « **en:** Viernes 1 de Mayo de 2009, 15:28 »

Buenas,

partiendo de un método que tiene como entrada dos naturales: n y m.

Se deben generar todos los subconjuntos de tamaño m del conjunto con número de elementos n.

p .ejemplo.

si n = 4 y m =2
[1,2,3,4]

debería devolver [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]

el conjunto inicial siempre se crea desde 1 a n.

Muchas gracias por la ayuda.

Yo había pensado en hacerlo con una lista simplemente enlazada. Lo que no averiguo es como recorrer el conjunto inicial (podria ser un vector) para dar todos los subconjuntos de tamaño m existentes.

Saludos,

Geo · « **Respuesta #1 en:** Viernes 1 de Mayo de 2009, 21:06 »

Lo puedes hacer con listas, con un vector simple, como desees.

Lo más sencillo: tomas el valor inicial y lo emparejas con todos los que le siguen, ahora tomas el segundo valor y lo emparejas con los subsecuentes, tomas el tercero y lo emparejas...

fachamix · « **Respuesta #2 en:** Sábado 2 de Mayo de 2009, 16:43 »

segui el consejo que te acaban de dar.
el programa es muy simple.

porque quieres utilizar listas???? necesitas tener en memoria (RAM) estos subconjuntos o simplemente los tienes que guardar en alguna parte, o simplemente los tienes que imprimir ???

si no necesitas tenerlos en memoria RAM, imprimelos simplemente, o guardalos en un archivo

protoculo · « **Respuesta #3 en:** Martes 5 de Mayo de 2009, 22:54 »

Cita de: "Geo"

Lo puedes hacer con listas, con un vector simple, como desees.

Lo más sencillo: tomas el valor inicial y lo emparejas con todos los que le siguen, ahora tomas el segundo valor y lo emparejas con los subsecuentes, tomas el tercero y lo emparejas...

Creo que no es tan sencillo como lo planteas...

no podemos emparejar el inicial con los siguientes, puesto que en el caso que expongo:

1,2,3,4

si se hacen de tres en tres, como se hace?

1,2,3 ... 1,2,4

no creo que sea tan sencillo... o estoy muy liado.

Si alguien puede postear la estructura solo para encontrar todas las combinaciones como pongo en el primer post, teniendo en cuenta que debe ser subconjuntos de m elementos de un conjunto de n.

no os preocupeis de donde se deben almacenar.

Saludos y gracias de nuevo.

Geo

Cita de: "protoculo"

Cita de: "Geo"
Lo puedes hacer con listas, con un vector simple, como desees.

Lo más sencillo: tomas el valor inicial y lo emparejas con todos los que le siguen, ahora tomas el segundo valor y lo emparejas con los subsecuentes, tomas el tercero y lo emparejas...

Creo que no es tan sencillo como lo planteas...

no podemos emparejar el inicial con los siguientes, puesto que en el caso que expongo:

1,2,3,4

si se hacen de tres en tres, como se hace?

1,2,3 ... 1,2,4

no creo que sea tan sencillo... o estoy muy liado.

¿De tres en tres? En tu enunciado no aparece esa posibilidad.

Cita de: "protoculo"

Si alguien puede postear la estructura solo para encontrar todas las combinaciones como pongo en el primer post, teniendo en cuenta que debe ser subconjuntos de m elementos de un conjunto de n.

Podrías tomar papel, lápiz (y goma) y hacerlo.
4,3
123, 234

9,6
123456, 234567, 345678, 456789

protoculo · « **Respuesta #5 en:** Jueves 7 de Mayo de 2009, 00:15 »

Cita de: "Geo"

Cita de: "protoculo"
Cita de: "Geo"
Lo puedes hacer con listas, con un vector simple, como desees.

Lo más sencillo: tomas el valor inicial y lo emparejas con todos los que le siguen, ahora tomas el segundo valor y lo emparejas con los subsecuentes, tomas el tercero y lo emparejas...

Creo que no es tan sencillo como lo planteas...

no podemos emparejar el inicial con los siguientes, puesto que en el caso que expongo:

1,2,3,4

si se hacen de tres en tres, como se hace?

1,2,3 ... 1,2,4

no creo que sea tan sencillo... o estoy muy liado.
¿De tres en tres? En tu enunciado no aparece esa posibilidad.

Cita de: "protoculo"
Si alguien puede postear la estructura solo para encontrar todas las combinaciones como pongo en el primer post, teniendo en cuenta que debe ser subconjuntos de m elementos de un conjunto de n.
Podrías tomar papel, lápiz (y goma) y hacerlo.
4,3
123, 234

9,6
123456, 234567, 345678, 456789

Ésto es una respuesta?

papel y lápiz?

Geo · « **Respuesta #6 en:** Jueves 7 de Mayo de 2009, 06:21 »

Cita de: "protoculo"

Ésto es una respuesta?

papel y lápiz?

Con papel y lápiz se hace esto:
----------------------
N, M
[subconjuntos]

4, 3
[123], [134], [234]

9, 6
[123456], [134567], [145678], [156789], [234567], [245678], [256789], [345678], [356789], [456789]
-----------------------
Visualizando no me parece que sea muy difícil hallar el patrón (perdone ud. si me equivoco), con lo que se puede pasar a expresarlo mediante un algoritmo y crear el programa.

La idea era ayudar a encontrar la solución, no entregarla, disculpas y suerte con tu tarea.

fachamix · « **Respuesta #7 en:** Jueves 7 de Mayo de 2009, 07:00 »

lindo tu problema.

disculpa si mi codigo esta improlijo, le hice de apuradas, porque me parecia intrigante tu problema.

tambien te pido disculpas si es algo ineficiente o dificil de seguir.

tambien te pido disculpas, porque no hice pruebas necesarias para garantizar que el programa funcione para todos los casos.

pero probalo y decime ok ????

aqui va.... esta compilado en CODE BLOCKS con MINGW:

Código: C++

 
#include <iostream>
 
using namespace std;
 
int N,M;
void imprimir_memoria(int memoria[100][10]);
bool fin_vectorPunteros(int vectorPunteros[]);
bool apunta_elementos_distintos(int vectorPadre[],int vectorPunteros[]);
void inc_vectorPunteros(int vectorPunteros[],int longitud);
void guardar_subconjunto_en_memoria(int memoria[100][10],int vectorPunteros[],int vectorPadre[]);
bool subconjunto_encontrado_en_memoria(int memoria[100][10],int vectorPadre[],int vectorPunteros[]);
void imprimir_vectorPunteros(int vectorPunteros[]);
void imprimir_vectorPadreApuntado(int vectorPadre[],int vectorPunteros[]);
 
 
int main()
{
    cout << "Programa que genera SubConjuntos" << endl;
 
    cout << "Ingrese el numero de elementos del conjunto PADRE:";
    cin >> N; cout << endl;
    cout << "Cargue los elementos del conjunto PADRE:" << endl;
    int vectorPadre[N];
    for (int i = 0;i<N;i++) {
        cout << i << ">";
        cin >> vectorPadre[i];
        cout << endl;
    }
    cout << "Imprimiendo conjunto PADRE:" << endl;
    for (int i = 0; i<N ;i++) {
        cout << vectorPadre[i] << "-";
    }
 
    cout << endl << "----------------------------------------------" << endl;
    cout << endl << "Ingrese el tamaño de los subconjuntos:";
    cin >> M;
 
    cout << endl << "----------------------------------------------" << endl;
    cout << "iniciando vector punteros en 0" << endl;
    int vectorPunteros[M];
    for (int i = 0;i<M;i++){
        vectorPunteros[i] = 0;
    }
 
    cout << endl << "----------------------------------------------" << endl;
    cout << "iniciando matriz de memoria en -1" << endl;
    int memoria[100][10];
    for (int i = 0;i<100;i++) {
        for (int j = 0;j<M;j++){
            memoria[i][j] = -1;
        }
    }
 
    while (!fin_vectorPunteros(vectorPunteros)){
        /*if (apunta_elementos_distintos(vectorPadre,vectorPunteros)) {
            if (subconjunto_encontrado_en_memoria(memoria,vectorPadre,vectorPunteros)){
                cout << endl << "Encontrado:";
                for (int x = 0;x<M;x++){
                    cout << vectorPadre[vectorPunteros[x]];
                }
                cout << endl;
                //guardar_subconjunto(matriz_memoria,vectorA,vectorPunt,M,N);
            }
        }
        */
        if (apunta_elementos_distintos(vectorPadre,vectorPunteros)) {
            //imprimir_vectorPunteros(vectorPunteros);
            //imprimir_vectorPadreApuntado(vectorPadre,vectorPunteros);
            if (!subconjunto_encontrado_en_memoria(memoria,vectorPadre,vectorPunteros)){
                cout << "Subconjunto nuevo {" << endl;
                cout << "t"; imprimir_vectorPunteros(vectorPunteros);
                cout << "t"; imprimir_vectorPadreApuntado(vectorPadre,vectorPunteros);
                cout << endl << "}" << endl;
 
                guardar_subconjunto_en_memoria(memoria,vectorPunteros,vectorPadre);
            }
        }
        inc_vectorPunteros(vectorPunteros,M);
        cout << endl;
    }
    system("pause");
    imprimir_memoria(memoria);
    return 0;
}
 
bool subconjunto_encontrado_en_memoria(int memoria[100][10],int vectorPadre[],int vectorPunteros[]){
    bool ban = false,temp;
    int fila = 0,coincidencias;
 
    while (memoria[fila][0] != -1) {
        coincidencias = 0;
        for (int j = 0;j<M;j++){
            for (int j2 = 0;j2<M;j2++){
                if (memoria[fila][j] == vectorPadre[vectorPunteros[j2]]) {
                    coincidencias++;
                }
            }
        }
        fila++;
        if (coincidencias == M) {
            return true;
        }
    }
    return false;
}
 
void guardar_subconjunto_en_memoria(int memoria[100][10],int vectorPunteros[],int vectorPadre[]) {
    int fila;
    for (fila = 0;((fila<100) && (memoria[fila][0] != -1));fila++);
    for (int j = 0;j<M;j++){
        memoria[fila][j] = vectorPadre[vectorPunteros[j]];
    }
}
 
void inc_vectorPunteros(int vectorPunteros[],int longitud) {
    bool ban = true;
    longitud--;
    while (ban) {
        if (vectorPunteros[longitud] == (N-1)) {
            vectorPunteros[longitud] = 0;
            longitud--;
        }
        else {
            vectorPunteros[longitud] = vectorPunteros[longitud] + 1;
            ban = false;
        }
    }
}
 
bool apunta_elementos_distintos(int vectorPadre[],int vectorPunteros[]) {
    for (int i = 0;i<M;i++){
        for (int j = i+1;j<M;j++) {
            if (vectorPadre[vectorPunteros[i]] == vectorPadre[vectorPunteros[j]]) {
                    return false;
            }
        }
    }
 
    return true;
}
 
bool fin_vectorPunteros(int vectorPunteros[]) {
    bool ban = true;
    for (int i = 0;i<M;i++) {
        if (vectorPunteros[i] != (N-1)) {
            ban = false;
        }
    }
    return ban;
}
 
void imprimir_memoria(int memoria[100][10]) {
    for (int i = 0;i<100;i++){
        for (int j = 0;j<M;j++){
            cout << memoria[i][j] << " ";
        }
        cout << endl;
    }
}
 
void imprimir_vectorPunteros(int vectorPunteros[]){
    cout << " Vector Punteros: ";
    for (int i = 0; i<M ; i++){
        cout << vectorPunteros[i];
    }
}
 
void imprimir_vectorPadreApuntado(int vectorPadre[],int vectorPunteros[]){
    cout << " Vector Padre Apuntado: ";
    for (int i = 0; i<M ; i++){
        cout << vectorPadre[vectorPunteros[i]];
    }
}
 
 
 

EI: juntando mensajes.

vi que andaba con un conjunto de 4 elementos, y generaba sobconjuntos de 2, tambien de 3, y lo postie.

es muy tarde, probalo, mañana lo explico bien cual fue la logica.

por favor, nadie me critique eficiencia y eso ... vuelvo a decir, lo hice a las apuradas (aun pueden ver mis comentarios en el codigo que muestran que estaba depurando y ni siquiera los borre)

saludos

la memoria para guardar los subconjuntos encontrados es de 100 por 10, es decir, puedes almacenar como maximo 100 subconjuntos de 10 elementos cada uno en esa memoria.

saludos, mañana lo explico

protoculo · « **Respuesta #8 en:** Jueves 7 de Mayo de 2009, 18:46 »

Muchas gracias,

no dudo que no funcione, pero no los quiero almacenar.

Solo quiero una estructura de for anidados o recursivo que me devuelva cada subconjunto existente en el conjunto inicial (que rellene un array de m elementos por ejemplo)... luego yo con cada array ya me apaño (los voy a meter en una lista dinámica).

fachamix · « **Respuesta #9 en:** Jueves 7 de Mayo de 2009, 20:34 »

tu estructura recursiva seria esta en mi codigo:

Código: C++

 
while (!fin_vectorPunteros(vectorPunteros)){
        /*if (apunta_elementos_distintos(vectorPadre,vectorPunteros)) {
            if (subconjunto_encontrado_en_memoria(memoria,vectorPadre,vectorPunteros)){
                cout << endl << "Encontrado:";
                for (int x = 0;x<M;x++){
                    cout << vectorPadre[vectorPunteros[x]];
                }
                cout << endl;
                //guardar_subconjunto(matriz_memoria,vectorA,vectorPunt,M,N);
            }
        }
        */
        if (apunta_elementos_distintos(vectorPadre,vectorPunteros)) {
            //imprimir_vectorPunteros(vectorPunteros);
            //imprimir_vectorPadreApuntado(vectorPadre,vectorPunteros);
            if (!subconjunto_encontrado_en_memoria(memoria,vectorPadre,vectorPunteros)){
                cout << "Subconjunto nuevo {" << endl;
                cout << "t"; imprimir_vectorPunteros(vectorPunteros);
                cout << "t"; imprimir_vectorPadreApuntado(vectorPadre,vectorPunteros);
                cout << endl << "}" << endl;
 
                guardar_subconjunto_en_memoria(memoria,vectorPunteros,vectorPadre);
            }
        }
        inc_vectorPunteros(vectorPunteros,M);
        cout << endl;
    }
 
 

desde mi logica, si tienes que almacenar los subconjuntos encontrados, porque SI es lo mismo decir subconjunto {1,2} y {2,1} tienen los mismos elementos, es el mismo conjunto, entonces debes llevar una cuenta de los subconjuntos encontrados.

proba el programa que hice, porque lo e hecho por vos, bajate el codeblocks con mingw, compilalo, analizalo, testealo, y en todo caso depuralo.

vuelvo a repetir, sitienes que almacenar, aunque sea temporalmente como lo hago yo, todos los subconjuntos que vas encontrando para no repetirlos en la salida.

EI: juntando mensajes.

Código: C++

 
#include <iostream>
 
using namespace std;
 
/*
variable N, es la cantidad de elementos del conjunto padre
variable M, es la cantidad de elementos que deben tener los cubconjuntos generados de PADRE
*/
int N,M;
 
void imprimir_memoria(int memoria[100][10]); //imprime los subconjuntos generados
 
/* funcion que devuelve true si ya se evaluaron todos los elementos del conjunto PADRE*/
bool fin_vectorPunteros(int vectorPunteros[]); 
 
/*funcion que nos dice si el vector punteros apunta elementos distintos, es necesario, porque no podemos generar un subconjunto de 3 elementos que sea {1,1,2} por ejemplo */
bool apunta_elementos_distintos(int vectorPadre[],int vectorPunteros[]);
 
/*funcion para incrementar el vector de punteros y apuntar al elemento siguiente del conjunto PADRE*/
void inc_vectorPunteros(int vectorPunteros[],int longitud);
 
/*cuando se encuentra un subconjunto , debo guardarlo, en este caso en una memoria de 100 x 10, es decir podre almacenar hasta 100 subconjuntos de como maximo 10 elementos c/u*/
void guardar_subconjunto_en_memoria(int memoria[100][10],int vectorPunteros[],int vectorPadre[]);
 
/*cuando el vector punteros se actualiza, hay un posible subconjunto de PADRE (apuntado por este vector), por ese debemos averiguar si existe un subconjunto en memoria igualal encontrado, pues puede darse el caso de haber almacenado el subconjunto {1,2} y en algun momento del algoritmo hacer referencia a un subconjunto {2,1} que seria equivalente*/
bool subconjunto_encontrado_en_memoria(int memoria[100][10],int vectorPadre[],int vectorPunteros[]);
 
/*imprime el contenido de vectorPunteros*/
void imprimir_vectorPunteros(int vectorPunteros[]);
 
/*imprime los elementos (que formarian un posible subconjunto) de PADRE apuntados por vectorPunteros*/
void imprimir_vectorPadreApuntado(int vectorPadre[],int vectorPunteros[]);
 
 
int main()
{
    cout << "Programa que genera SubConjuntos" << endl;
    /*digo cuantos elementos tendra PADRE*/
    cout << "Ingrese el numero de elementos del conjunto PADRE:";
    cin >> N; cout << endl; 
    
    /*luego cargo el conjunto PADRE*/
    cout << "Cargue los elementos del conjunto PADRE:" << endl;
    int vectorPadre[N];
    for (int i = 0;i<N;i++) {
        cout << i << ">";
        cin >> vectorPadre[i];
        cout << endl;
    }
    /*imprimo su contenido para verificar*/
    cout << "Imprimiendo conjunto PADRE:" << endl;
    for (int i = 0; i<N ;i++) {
        cout << vectorPadre[i] << "-";
    }
 
    cout << endl << "----------------------------------------------" << endl;
    /* digo cuantos elementos debera tener los subconjuntos generados */
    cout << endl << "Ingrese el tamaño de los subconjuntos:";
    cin >> M;
 
    cout << endl << "----------------------------------------------" << endl;
 
    /* inicio el vector punteros en 0 para asegurar su contenido */
    cout << "iniciando vector punteros en 0" << endl;
    int vectorPunteros[M];
    for (int i = 0;i<M;i++){
        vectorPunteros[i] = 0;
    }
 
    cout << endl << "----------------------------------------------" << endl;
 
    /* genero e inicio una memeoria para almacenar los subconjuntos encontrados */
    cout << "iniciando matriz de memoria en -1" << endl;
    int memoria[100][10];
    for (int i = 0;i<100;i++) {
        for (int j = 0;j<M;j++){
            memoria[i][j] = -1;
        }
    }
    
    /* Parte principal del programa */
    while (!fin_vectorPunteros(vectorPunteros)){
        if (apunta_elementos_distintos(vectorPadre,vectorPunteros)) {
            if (!subconjunto_encontrado_en_memoria(memoria,vectorPadre,vectorPunteros)){
                cout << "Subconjunto nuevo {" << endl;
                cout << "t"; imprimir_vectorPunteros(vectorPunteros);
                cout << "t"; imprimir_vectorPadreApuntado(vectorPadre,vectorPunteros);
                cout << endl << "}" << endl;
 
                guardar_subconjunto_en_memoria(memoria,vectorPunteros,vectorPadre);
            }
        }
        inc_vectorPunteros(vectorPunteros,M);
        cout << endl;
    }
    system("pause");
    imprimir_memoria(memoria);
    return 0;
}
 
bool subconjunto_encontrado_en_memoria(int memoria[100][10],int vectorPadre[],int vectorPunteros[]){
    bool ban = false,temp;
    int fila = 0,coincidencias;
 
    while (memoria[fila][0] != -1) {
        coincidencias = 0;
        for (int j = 0;j<M;j++){
            for (int j2 = 0;j2<M;j2++){
                if (memoria[fila][j] == vectorPadre[vectorPunteros[j2]]) {
                    coincidencias++;
                }
            }
        }
        fila++;
        if (coincidencias == M) {
            return true;
        }
    }
    return false;
}
 
void guardar_subconjunto_en_memoria(int memoria[100][10],int vectorPunteros[],int vectorPadre[]) {
    int fila;
    for (fila = 0;((fila<100) && (memoria[fila][0] != -1));fila++);
    for (int j = 0;j<M;j++){
        memoria[fila][j] = vectorPadre[vectorPunteros[j]];
    }
}
 
void inc_vectorPunteros(int vectorPunteros[],int longitud) {
    bool ban = true;
    longitud--;
    while (ban) {
        if (vectorPunteros[longitud] == (N-1)) {
            vectorPunteros[longitud] = 0;
            longitud--;
        }
        else {
            vectorPunteros[longitud] = vectorPunteros[longitud] + 1;
            ban = false;
        }
    }
}
 
bool apunta_elementos_distintos(int vectorPadre[],int vectorPunteros[]) {
    for (int i = 0;i<M;i++){
        for (int j = i+1;j<M;j++) {
            if (vectorPadre[vectorPunteros[i]] == vectorPadre[vectorPunteros[j]]) {
                    return false;
            }
        }
    }
 
    return true;
}
 
bool fin_vectorPunteros(int vectorPunteros[]) {
    bool ban = true;
    for (int i = 0;i<M;i++) {
        if (vectorPunteros[i] != (N-1)) {
            ban = false;
        }
    }
    return ban;
}
 
void imprimir_memoria(int memoria[100][10]) {
    for (int i = 0;i<100;i++){
        for (int j = 0;j<M;j++){
            cout << memoria[i][j] << " ";
        }
        cout << endl;
    }
}
 
void imprimir_vectorPunteros(int vectorPunteros[]){
    cout << " Vector Punteros: ";
    for (int i = 0; i<M ; i++){
        cout << vectorPunteros[i];
    }
}
 
void imprimir_vectorPadreApuntado(int vectorPadre[],int vectorPunteros[]){
    cout << " Vector Padre Apuntado: ";
    for (int i = 0; i<M ; i++){
        cout << vectorPadre[vectorPunteros[i]];
    }
}
 
 

EI: juntando mensajes por ULTIMA VEZ (para algo esta el boton Editar), la proxima borro.

ya esta flaco, hasta e programado por vos, que mas ayuda quieres, por lo menos analiza lo que te paso

fachamix

y ??? desaparecio este chango che, como boludo yo haciendo el codigo para el niño.

en fin, por las dudas, te digo que es lo que e hecho:

_me e dado cuenta que si queria subconjuntos de 2 elementos por ejemplo, esos subconjuntos ivan a estar "incluidos" en la totalidad de pares que se puedan formar con los elementos del conjutno PADRE.
_Si queria subconjuntos de 3 elementos, me di cuenta que esos subconjuntos ivan a estar "incluidos" en todas las ternas posibles a armar con los elemtnos del conjunto padre

asi llegas a la conclusion de que el problema lo puedes dividir en 2:
1) encontrar todos los pares, ternas, cuaternas .... etc (dependiendo del tamaño del subconjunto deseado) posibles a armar con los elementos del conjunto PADRE

2) del resultado de 1), excluir a aquellos que tengan elementos similares, es decir, si tenemos los pares ordenados (1,2) y (2,1) , hablando dentro del marco de pares ordenados, SERIAN DIFERENTES, pero si hablamos de conjuntos {1,2} y {2,1}, SON IGUALES!!!!!!

ya te e dicho todo lo que tenias que saber

SoloCodigo

Autor Tema: Generar Subconjuntos de tamaño m de un conjutno (Leído 6560 veces)

protoculo

Generar Subconjuntos de tamaño m de un conjutno

Geo

Re: Generar Subconjuntos de tamaño m de un conjutno

fachamix

Re: Generar Subconjuntos de tamaño m de un conjutno

protoculo

Re: Generar Subconjuntos de tamaño m de un conjutno

Geo

Re: Generar Subconjuntos de tamaño m de un conjutno

protoculo

Re: Generar Subconjuntos de tamaño m de un conjutno

Geo

Re: Generar Subconjuntos de tamaño m de un conjutno

fachamix

Re: Generar Subconjuntos de tamaño m de un conjutno

protoculo

Re: Generar Subconjuntos de tamaño m de un conjutno

fachamix

Re: Generar Subconjuntos de tamaño m de un conjutno

fachamix

Re: Generar Subconjuntos de tamaño m de un conjutno