ayuda con algoritmo de combinatoria c++

Archivado
hola, escribo esto ya desesperado despues de 4 dias intentandolo a ver si algun alma caritativa se le ocurre algo...
resulta que tengo que programar una función en c++ para una practica de la universidad en la cual tengo como parametros N y K, la funcion consiste en crear todos los subconjuntos posibles de 1...N cogiendolos de K elementos, sin repetición... es decir si tenemos K=3 y N=5
{1,2,3,4,5}

subconjuntos: 123, 124, 125, 134, 135, 145, 234, 235, 245, 345

decir que tengo una funcion privada que me calcula el numero de subconjuntos que deberan salirme en funcion de K y N, así que eso no es problema podemos suponer que tengo el numero de subconjuntos almacenado en una variable.

si a alguien se le enciende la bombilla que no dude en postear, muchas gracias! ;)
Lo puedes entender pensando en la combinatoria como un árbol que se ramifica. En tu ejemplo K=3 y N=5:

        / 3   
1 - 2 - 4
   \   \ 5
     \     
       3   -4
               \ 5


Faltarían el resto de ramas pero espero que más o menos se entienda la idea.

Para programarlo pues tienes tantos "troncos" como K {1,2,3}, y de cada tronco surgen (N-indiceDelTronco) ramas. A su vez de estas ramas surgen otras nuevas con la misma regla, y los niveles de ramas serán tantos como K.

En tu ejemplo:

Del "tronco" 2 saldrían (5-2) ramas, las que corresponden a {3,4,5}
De la rama 3 saldrían (5-3) ramas, {4,5}
De la rama 4 saldrían (5-4) ramas, {5}

Espero que te sirva de ayuda para programar tu algoritmo.
Sólo te puedo decir que la solución mas clara se basa en la recursividad. No se C++... de todas formas he estado 15 min haciendo un pseudocódigo, pero me temo que no lo entenderías... siento no poder ayudarte.
he estudiado funciones recursivas, lo que pasa que sigo sin ser muy ducho en la materia... la verdad es que el problema se las trae..

si no te importa, podrias poner unas pinceladas de tu pseudocódigo

un saludo amigo
Haciendo caso al ejemplo publicado, aqui tienes un codigo en c que genera la secuencia indicada, ( que realmente me ha picado la curiosidad y lo he hecho para ver si realmente era tan dificil como para llevar 4 dias... y visto lo visto..se hace en 5-10 minutos...

#include <stdio.h>

int N=5;
int K=3;


void frecursiva(int numero, int indice, int longitud){
  int i;
  if (longitud==K) {
    printf("%d\n",numero);
  }
  else {
    for (i=indice; i<=N; i++){
      frecursiva(numero*10+i,i+1,longitud+1);
    }
  }
}
main(int argc, char *argv[])
{
  int i;
  for (i=1; i<N;i++){
    frecursiva(i,i+1,1);
  }
}



pd: para la proxima vez esfuerzate mas.

pd2: si tiene algun fallo no me responsabilizo, ya que me he guiado mas por el ejemplo que por el enunciado... y ahora a seguir con bison/yacc
nu_kru escribió:Haciendo caso al ejemplo publicado, aqui tienes un codigo en c que genera la secuencia indicada, ( que realmente me ha picado la curiosidad y lo he hecho para ver si realmente era tan dificil como para llevar 4 dias... y visto lo visto..se hace en 5-10 minutos...

#include <stdio.h>

int N=5;
int K=3;


void frecursiva(int numero, int indice, int longitud){
  int i;
  if (longitud==K) {
    printf("%d\n",numero);
  }
  else {
    for (i=indice; i<=N; i++){
      frecursiva(numero*10+i,i+1,longitud+1);
    }
  }
}
main(int argc, char *argv[])
{
  int i;
  for (i=1; i<N;i++){
    frecursiva(i,i+1,1);
  }
}



pd: para la proxima vez esfuerzate mas.

pd2: si tiene algun fallo no me responsabilizo, ya que me he guiado mas por el ejemplo que por el enunciado... y ahora a seguir con bison/yacc


Primero de todo muchisimas gracias, no esperaba que nadie me pusiera el código y he de decir que lo he probado y funciona a la perfeccion para todos los casos y evidentemente nadie que postee aqui es responsable de que el código funcione o no, pero tambien te quiero decir que no deberias entrar a valorar mi esfuerzo (que no ha sido poco) a la hora de programar, cada uno tenemos más o menos facilidad para programar, ademas como he mencionado no domino demasiado la recursividad, si he recurrido a postear aqui ha sido porque realmente necesitaba agotar ese recurso.

un saludo

PD: gracias también a los demás foreros por perder algo de su tiempo en echar un cable
5 respuestas
Archivado
Volver a General