#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);
}
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]];
}
}
