Author Topic: Todas las combinaciones de un vector  (Read 5061 times)

zaius

  • Full Member
  • ***
  • Posts: 133
  • Karma: 0
    • View Profile
Todas las combinaciones de un vector
« on: Diciembre 31, 2013, 12:54:39 am »
Existe alguna función que te genere todas las combinaciones posibles de un vector (dentro de unos limites) en c++??

chuidiang

  • Administrator
  • Hero Member
  • *****
  • Posts: 5472
  • Karma: 12
    • View Profile
    • Apuntes de programación
Re: Todas las combinaciones de un vector
« Reply #1 on: Enero 02, 2014, 02:35:19 am »
Hola.

No que yo sepa. Tendras que implementarla o buscar alguna libreria en internet que lo haga.

Se bueno

yoel

  • Newbie
  • *
  • Posts: 7
  • Karma: 0
    • View Profile
Re: Todas las combinaciones de un vector
« Reply #2 on: Febrero 03, 2014, 09:15:53 am »
Hola, saludos a todos, soy nuevo en el foro. Quiero corresponder esta loable iniciativa de chuidiang de compartir el conocimiento con los demás ( :) ;) ) así que estaré aquí ayudando a responder las cosas que yo sepa, y aprendiendo de las respuestas de los demás en las cosas que no sepa.

Zaious, ¿Cómo que "todas las combinaciones" de un vector?

¿Te refieres a todos los vectores de una longitud dada, cuyos elementos sean enteros y comprendidos entre ciertos límites? Pues, hay que codificarla como dice chuidian, pero ten en cuenta que el número de combinaciones aumenta exponencialmente por tanto puede llegar a ser enorme, salvo para vectores pequeños con "pocas" posibilidades para sus elementos.

Vamos a poner un ejemplo: un vector de 4 elementos, cuyos valores son enteros entre 1 y 4. Vamos a analizar el problema, los números serían:
1 - 1 - 1 - 1
1 - 1 - 1 - 2
1 - 1 - 1 - 3
1 - 1 - 1 - 4

es decir, manteniendo fijos los tres primeros y variando el cuarto. Luego vienen.

1 - 1 - 2 - 1
1 - 1 - 2 - 2
1 - 1 - 2 - 3
1 - 1 - 2 - 4

donde se cambia el tercero, y se repite el procedimiento con el cuarto. Y así sucesivamente hasta la última serie:

4 - 4 - 4 - 1
4 - 4 - 4 - 2
4 - 4 - 4 - 3
4 - 4 - 4 - 4

Te advierto de antemano que son 4 x 4 x 4 x 4 = 256 combinaciones.
Bueno, estuve pensando un raaaaato como generar esta secuencia  ???, y al final resolví lo siguiente. Vamos a definir un vector llamado 'v' de cuatro elementos enteros. Y conjuntamente una función step cuya finalidad es calcular el siguiente número de la secuencia. Devuelve 0 si tuvo éxito y -1 si no tuvo éxito, esto es, si ya alcanzó el máximo valor posible 4-4-4-4. Pues bien, incrementar esta secuencia es como trabajar con números decimales. Imagínate un número de tres cifras al que deseas sumar unidad. ¿Qué haces? Miras la cifra de las unidades. Si es menor a 9, incrementas uno y listo. Si es 9, buscas la cifra de las decenas. Si esta es menor a 9, la incrementas y pones las unidades a cero. Si tanto las decenas como las unidades son iguales a 9, pues miras las centenas. Esto es con números decimales de base 10, pero lo puedes extender a base 4 como en este ejemplo, y empezando los números en el 1 y no en el 0. Sin más preámbulo aquí el código:

Code: [Select]
#include <stdlib.h>
#include <stdio.h>

int step( int *v );

int main( ) {
   
int v[4];

/* inicializando */
v[0] = 1;
v[1] = 1;
v[2] = 1;
v[3] = 1;

do {
printf( "%d - %d - %d - %d\n", v[0], v[1], v[2], v[3]);
} while ( !step( v ) );
}

int step( int *v ) {

int i, j;
   
/* determinamos en forma regresiva la última posición donde
* puede incrementarse la cifra */
i = 3;
while ( i >= 0 && v[i] >= 4 )
i--;

/* si obtuvo i == -1, es porque todos los elementos llegaron al máximo,
* luego no puede incrementarse */
if ( i < 0 )
return -1;

/* de otro modo, incrementa la cifra i-ésima, y pone al valor mínimo todas
* las cifras que le siguen */
v[i]++ ;
for ( j = i + 1; j < 4; j++ )
v[j] = 1;

/* sale con éxito */
return 0;
}

Al compilar y ejecutar verás como te muestra por la salida estándar (pantalla) todas las combinaciones con cuatro números comprendidos entre 1 y 4. Claro, puedes modificarlo para cambiar la base numérica o longitud del vector.

Espero te sirva, y para poder orientarte mejor hace falta que expliques bien qué es lo que quieres lograr.

Saludos a todos, especialmente chuidiang  :D

 

ey