[SOLUCIONADO] recursividad c++ hallar todas las posibles soluciones de la suma de un vecto

[Karpenito]

Buenas noches comunidad , tengo un problema con este ejercicio de recursividad , la vdd no se me da muy bien este temam el ejercicio consiste en hallar todas las posibles soluciones de la suma de un vector que tengan como resultado un numero n ejemplo
Ejm: Si V: 8, 2, 3, 3, 6, 4. y X=13
Soluciones:
3+6+4 = 13
8+2+3=13

este es el codigo que eh hecho hasta ahora pero solo estoy tirando flechas :/

Código:

#include<iostream>

using namespace std;


int sumar(int V[6]){
    int acumulado = 0;
    int longitud_vector = 6;
    for( int i=0; i<longitud_vector; i++){  
        acumulado += V[i];
    }    
    return acumulado;
}

void imprimir(int sol[6]){
    cout<<"Solucion"<<endl;
    int longitud_vector = 6;
    for( int i=0; i<longitud_vector; i++){  
        if(sol[i] != 0){
            cout<<sol[i]<<" + ";
        }
    }
    
}

void imprimir_disp(bool disp[6]){
    
    int longitud_vector = 6;
    for( int i=0; i<longitud_vector; i++){  
        if(disp[i] == true){
            cout<<1<<" ";
        }else{
            cout<<0<<" ";    
        }
    }
    cout<<endl;
        
}

void imprimir_sol(int sol[6]){
    
    int longitud_vector = 6;
    for( int i=0; i<longitud_vector; i++){  

        cout<<sol[i]<<" ";
    }
    cout<<endl;
        
}

void vaciar_vector_sol(int sol[6]){
    int longitud_vector = 6;
    for( int i=0; i<longitud_vector; i++){  
        sol[i] = 0;
    }    
}

void reiniciar_disp(bool disp[6]){
    int longitud_vector = 6;
    for( int i=0; i<longitud_vector; i++){  
        disp[i] = true;
    }    
}

void suma2 (int V[6], int obj, bool disp[6] , int sol[6] ,int etapa) {

    
    int longitud_vector = 6;

    
    for( int i=0; i<longitud_vector; i++){  

        if( (disp[i]==true) && ( (sumar(sol)+V[i]) <= obj) ) {
            disp[i] = false;
            sol[i] = V[i];
        
        
            /*Si la suma de los elementos del vector de 
              solucion es igual a el resultado buscado */     
            if (sumar(sol) == obj ){
                cout<<"\n=>";
                imprimir(sol);
           
            }else{ //si no, se hace un llamado recursivo de la funcion para buscar esa solucion

                suma2(V,obj,disp,sol,etapa+1);

            }
      
        }

         
    }

}

void suma(int Vector[6], int x)
{
    bool Disponibles[6];
    int Solucion[6] ,i;
    int longitud_vector = 6;
    
    //cambio todas las pocisiones del vector ah verdadero

    for(i=0; i<longitud_vector; i++){
        Disponibles[i] = true;
        Solucion[i] = 0;
    }
        
    suma2(Vector,x,Disponibles, Solucion, 0);
}




int main(){
    int Vector[6] = {8,2,3,3,6,4}; //vector
    //int Vector[6] = {6,4,3,3,5,3}; //vector
    int longitud_vector = 6;
    //cout<<"hola "<<longitud_vector<<endl;
    suma(Vector,13);
    system("pause");
    return 0;    
}

de verdad muchas gracias de antemano y espero puedan ayudarme

[eferion]

¿Seguro que este problema tienes que resolverlo con recursividad?

Yo sinceramente creo que con bucles la solución es mucho más sencilla.

[Karpenito]

en realidad con bucles es muy facil de resolver , pero una de las condiciones es que debe ser recursivo , hay esta el rollo del asunto

[Malenko]

una vez que lo tienes con bucles, pasarlo a recursivo es sencillo. Lo mismo al revés. Es meramente un proceso mecánico.

[eferion]

Yo este problema lo solucionaría un poco con ayuda de contenedores, ya que una secuencia de elementos puede tener un número indeterminado de posibles soluciones, cada una de ellas con un número indeterminado de elementos (eso sí, num de elementos de la solucion <= num de elementos del vector).

La desventaja de usar, como es tu caso, un vector de bool es que el reinicio de los valores has de realizarlo con sumo cuidado si no quieres acabar mal parado.

El caso es que si cada llamada recursiva recibe un vector de elementos (la combinación que se está comprobando actualmente) es sencillo realizar todas las combinatorias.

Entonces, la función recursiva podría tener esta firma:

Código C++:

typedef std::vector<int> Items;
typedef std::vector<Items> Resultado;
 
Resultado suma( int* ptr, int totalBuscado, int contadorValoresRestantes, Items parcial);
 

Donde:

• ptr apunta al elemento actual del vector
• totalBuscado indica la suma que debemos localizar
• contadorValoresRestantes indica cuántos elementos quedan por procesar del vector
• parcial almacena la secuencia que estamos comprobando actualmente

Dado que lo que estamos pasando de forma recursiva es una combinación de elementos, parece buena idea usar una función de ayuda que sume los elementos de dicha combinación. Aunque sea una chorrada de función, mejor separar las cosas por claridad:

Código C++:

int suma(const Items& items)
{
  return std::accumulate(items.begin(),items.end(),0);
}
 

Volviendo a la función recursiva, lo que hay que hacer es probar todas las combinaciones posibles, luego cada iteración tiene que probar las combinaciones con el número actual y sin el (en el ejemplo que has puesto, los resultados válidos pueden o no incorporar el primer elemento del vector, el 8). En el caso de que añada el número a la combinación basta con actualizar parcial.

Además, sabemos que si el parcial es superior al número buscado hay que abortar esa combinación puesto que sumar más valores no va a ayudar a encontrar un resultado bueno.

Con esto la función podría quedar así:

Código C++:

Resultado suma( int* ptr, int totalBuscado, int contadorValoresRestantes, Items parcial)
{
    Resultado resultado;
 
    contadorValoresRestantes--;
    if( contadorValoresRestantes >= 0 )
    {
        // Probamos sin añadir el elemento actual
        resultado = suma((ptr+1),totalBuscado,contadorValoresRestantes,parcial);
    }
 
    // Probamos añadiendo el elemento actual
    parcial.push_back(*ptr);
    int total = suma(parcial);
    if( (total < totalBuscado) && (contadorValoresRestantes >= 0) )
    {
        Resultado resultado2 = suma(++ptr,totalBuscado,contadorValoresRestantes,parcial);
 
        // Hay que fusionar ambos resultados
        // Esta línea básicamente copia el contenido de resultado2 al final de resultado
        resultado.insert(resultado.end(),resultado2.begin(),resultado2.end());
    }
    else if( total == totalBuscado )
    {
        // Si hemos encontrado una solución, la añadimos al resultado
        resultado.push_back(parcial);
    }
 
    return resultado;
}
 

Ya está la función recursiva terminada.

Para simplificar su uso se puede hacer una función que haga las veces de entrada al algoritmo... quizás algo así:

Código C++:

Resultado suma( int* ptr, int numeroValores, int totalBuscado)
{
    return suma(ptr,totalBuscado,numeroValores-1,std::vector<int>());
}
 

Y bueno, vamos a probar el código:

Código C++:

int main()
{
  const int SIZE = 6;
  int Vector[SIZE] = {8,2,3,3,6,4}; //vector
  Resultado resultados = suma(Vector,SIZE,13);
  
  std::cout << "Resultados: " << std::endl;
  if( !resultados.empty() )
  {
    auto lambda = [&](const std::vector<int>& items)
    {
      std::string separador;
      std::for_each(items.begin(),items.end(),[&](int v){ std::cout << separador << v; separador = ","; });
      std::cout << std::endl;
    };
    
    std::for_each(resultados.begin(),resultados.end(),lambda);
  }
  else
    std::cout << "No hay resultados!!!" << std::endl;
}
 

Lo que ofrece el siguiente resultado:

Código:

Resultados:
3,6,4
3,6,4
8,2,3
8,2,3

Vaya, los resultados aparecen duplicados. ¿Es un error? En absoluto. Lo que pasa es que hay dos elementos con valor 3, lo que arroja dos resultados distintos. Si quieres eliminar esos duplicados puedes optar por soluciones un poco más sofisticadas, una posibilidad es usar el contenedor set, pero eso tendrás que investigarlo un poco antes de que te ponga una respuesta :)

Un saludo.

[enrieto]

Hola; tengo otra versión, casi tan espantosa como la de arriba :)

Código C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
using sstype = std::set<std::set<int>>;
 
sstype& permutar(std::vector<int> p, std::vector<int> f, int suma)
{
    static sstype ss;
 
    if(suma == std::accumulate(p.begin(), p.end(), 0)) {
        ss.emplace(std::set<int>(p.begin(), p.end()));
        return ss;
    }
 
    for(size_t i = 0; i < f.size(); ++i) {
        auto ppio = p;
        ppio.push_back(f[i]);
        auto fin = f;
        fin.erase(fin.begin() + i);
 
        permutar(ppio, fin, suma);
    }
 
    return ss;
}
 
int main()
{
    std::vector<int> v{8, 2, 3, 3, 6, 4};
    const int suma = 13;
 
    auto ss = permutar(std::vector<int>{}, v, suma);
 
    for(auto& i : ss) {
        for(auto& j : i)
            std::cout << j << ' ';
        std::cout << '\n';
    }
}
 

[eferion]

Iniciado por enrieto

Hola; tengo otra versión, casi tan espantosa como la de arriba :)

En lo referente a la respuesta de arriba... hay una opción para que los mensajes más recientes aparezcan los primeros (yo la tengo activada) luego en ese caso tu respuesta estará encima de la mía :P

Y por cierto, tu respuesta no la calificaría como espantosa. Más bien sería original.

La única pega es que va a dar resultados incorrectos si la secuencia tiene números repetidos (efecto secundario del set):

Entrada:

Código C++:

std::vector<int> v{8, 2, 3, 3, 6, 4};
    const int suma = 6;
 

Salida:

Código:

2 4 
3 
6

Un saludo.

[enrieto]

[Edito], y si queda algo pasa para la versión beta.

Código C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
 
struct cmp {
    bool operator() (std::vector<int> a, std::vector<int> b)
    {
        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());
        return a < b;
    }
};
 
typedef std::set<std::vector<int>, cmp> sstype;
 
sstype& permutar(std::vector<int> p, std::vector<int> f, int suma)
{
    static sstype ss;
 
    if(suma == std::accumulate(p.begin(), p.end(), 0)) {
        ss.emplace(p.begin(), p.end());
        return ss;
    }
 
    for(size_t i = 0; i < f.size(); ++i) {
        auto ppio = p;
        ppio.push_back(f[i]);
        auto fin = f;
        fin.erase(fin.begin() + i);
 
        permutar(ppio, fin, suma);
    }
 
    return ss;
}
 
int main()
{
    std::vector<int> v{8, 2, 3, 3, 6, 4};
    const int suma = 6;
 
    auto ss = permutar(std::vector<int>{}, v, suma);
 
    for(auto& i : ss) {
        for(auto& j : i)
            std::cout << j << ' ';
        std::cout << '\n';
    }
}
 

[eferion]

Iniciado por enrieto

[Edito], y si queda algo pasa para la versión beta.

Yo creo que así ya cumple perfectamente con su cometido

[Karpenito]

Buenas noches eh tenido problemas para compilar sus codigos la verdad me enrede bastante con unas cosas que no entiendo , voy a documentarme mejor ya que se ven interesante , de todas formas estoy escribiendo para que no crean que me fugue con la solucion xD , si siquiera decir gracias , muchas gracias de antemano y cuando logre correr el codigo les comento ,(soy nuevo en esto de los foros asi que paciencia por favor)

Saludos!!!

[aguml]

Se me ocurre algo y no se si seria una locura. Pide que encuentre todas las combinaciones posibles donde se de una condición y se me ocurre que se podría obtener todas las permutaciones posibles y en cada una usa dos bucles donde se va probando si la suma sirve, o sea que sumas el primero con el siguiente y el siguiente... hasta que de él número buscado o hasta que te pases y después haces lo mismo pero empezando desde el segundo y así hasta el final y luego haces una permuta y repites y así hasta realizar todas las permutaciones posibles. Por supuesto habría que desechar las combinaciones que se repitan. ¿Seria buena idea o seria complicarse la vida?
En este código se usa recursividad para permutaciones:

Código C:

#include <stdio.h>
#include <stdlib.h>
 
/* print a list of ints */
int show(int *x, int len)
{
    int i;
    for (i = 0; i < len; i++)
        printf("%d%c", x[i], i == len - 1 ? '\n' : ' ');
    return 1;
}
 
/* next lexicographical permutation */
int next_lex_perm(int *a, int n) {
#   define swap(i, j) {t = a[i]; a[i] = a[j]; a[j] = t;}
    int k, l, t;
 
    /* 1. Find the largest index k such that a[k] < a[k + 1]. If no such
          index exists, the permutation is the last permutation. */
    for (k = n - 1; k && a[k - 1] >= a[k]; k--);
    if (!k--) return 0;
 
    /* 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is
       such an index, l is well defined */
    for (l = n - 1; a[l] <= a[k]; l--);
 
    /* 3. Swap a[k] with a[l] */
    swap(k, l);
 
    /* 4. Reverse the sequence from a[k + 1] to the end */
    for (k++, l = n - 1; l > k; l--, k++)
        swap(k, l);
    return 1;
#   undef swap
}
 
void perm1(int *x, int n, int callback(int *, int))
{
    do {
        if (callback) callback(x, n);
    } while (next_lex_perm(x, n));
}
 
/* Boothroyd method; exactly N! swaps, about as fast as it gets */
void boothroyd(int *x, int n, int nn, int callback(int *, int))
{
    int c = 0, i, t;
    while (1) {
        if (n > 2) boothroyd(x, n - 1, nn, callback);
        if (c >= n - 1) return;
 
        i = (n & 1) ? 0 : c;
        c++;
        t = x[n - 1], x[n - 1] = x[i], x[i] = t;
        if (callback) callback(x, nn);
    }
}
 
/* entry for Boothroyd method */
void perm2(int *x, int n, int callback(int*, int))
{
    if (callback) callback(x, n);
    boothroyd(x, n, n, callback);
}
 
/* same as perm2, but flattened recursions into iterations */
void perm3(int *x, int n, int callback(int*, int))
{
    /* calloc isn't strictly necessary, int c[32] would suffice
       for most practical purposes */
    int d, i, t, *c = calloc(n, sizeof(int));
 
    /* curiously, with GCC 4.6.1 -O3, removing next line makes
       it ~25% slower */
    if (callback) callback(x, n);
    for (d = 1; ; c[d]++) {
        while (d > 1) c[--d] = 0;
        while (c[d] >= d)
            if (++d >= n) goto done;
 
        t = x[ i = (d & 1) ? c[d] : 0 ], x[i] = x[d], x[d] = t;
        if (callback) callback(x, n);
    }
done:   free(c);
}
 
#define N 4
 
int main()
{
    int i, x[N];
    for (i = 0; i < N; i++) x[i] = i + 1;
 
    /* three different methods */
    perm1(x, N, show);
    perm2(x, N, show);
    perm3(x, N, show);
 
    return 0;
}
 

Lo saqué de esta página donde lo hay en otros lenguajes: http://rosettacode.org/wiki/Permutations#C.2B.2B