Autor
|
Tema: Ejercicio: las posibles combinaciones de una lista [python] (Leído 18,507 veces)
|
Ragnarok
|
Tengo que hacer todas las posibles combinaciones de una lista (cuidado, he dicho combinaciones, no permutaciones), esto significa las combinaciones tomadas de uno en uno de todos los elementos de la lista (es decir, sus elementos), de dos en dos, y así hasta las combinaciones de n en n elementos siendo n la longitud de la lista, es decir, sólo habrá una combinación de ese tamaño.
Lo estoy programando en python, así que si no me distraen mucho pondré la solución en ese lenguaje dentro de poco, pero puede ser un ejercicio interesante también para otros lenguajes.
|
|
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
Hola,
Me he puesto a trabajar en el problema. Al no saber cuantos elementos tiene la lista, yo lo haria de forma recursiva.
Un cosilla, ¿en las combinaciones el orden importaba o no?
|
|
|
En línea
|
- Doctor, confundo los números y los colores. - Vaya marrón. - ¿Marrón? ¡Por el culo te la hinco!
|
|
|
ghastlyX
Ex-Staff
Desconectado
Mensajes: 1.900
|
Supongo que os referís a mostrar los subconjuntos de k elementos dada una lista de n elementos. He hecho un código en C++ que hace eso: #include <iostream> #include <vector> using namespace std; typedef vector<int> VI; typedef vector<bool> VB; void rec(VI& v, VB& usado, int cnt, int primero, int n) { if (cnt == n) { cout << "{"; bool first = true; for (int i = 0; i < usado.size(); ++i) { if (usado[i]) { if (first) first = false; else cout << ","; cout << v[i]; } } cout << "}" << endl; return; } for (int i = primero; i < v.size(); ++i) { usado[i] = true; rec(v, usado, cnt + 1, i + 1, n); usado[i] = false; } } int main() { int n; cin >> n; //numero de elementos; VI v(n); for (int i = 0; i < n; ++i) cin >> v[i]; for (int i = 0; i <= n; ++i) { cout << "Subconjuntos de " << i << " elementos:" << endl; VB usado(n, false); rec(v, usado, 0, 0, i); //genera los subconjuntos de v de i elementos (habra n sobre i) cout << endl; } }
Un saludo de ghastlyX
|
|
|
En línea
|
|
|
|
Ragnarok
|
Bueno, el problema que quería resolver era más complicado, porque además quería generarlos de uno en uno sin guardar los resultados parciales, cosa que ya he hecho, pero como es una restricción que no había contemplado y el código queda un poco más complicado he decidido hacer también la versión normal, es decir, almacenando resultados parciales hasta que se devuelven todos. def lattice(l): s = [[]] for e in l: ns = [] for ps in s: nps = ps[:] nps.append(e) ns.append(nps) s = s + ns return s
PD: do-while en las combnaciones no importa el orden, importa en las variaciones. ghastlyX sí, también lo puedes ver como la unión de las particiones de un conjunto. PD2: no se me había ocurrido hacerlo recursivo, no queda del todo mal: def lattice(l): if l == []: return [[]] ll = lattice(l[1:]) return [e+[l[0]] for e in ll] + ll
|
|
« Última modificación: 6 Septiembre 2009, 03:01 am por Ragnarok »
|
En línea
|
|
|
|
do-while
Desconectado
Mensajes: 1.276
¿Habra que sacarla de paseo?
|
Aqui esta mi solucion. Hay soluciones para hartarse... void combinaciones(int lista[],int numElementosLista,int numElementosCombinacion,int paso) { int i; static int *listaCombinacion=NULL; if(numElementosLista < numElementosCombinacion) return; if(!listaCombinacion) /* si la lista esta sin inicializar -> reservar memoria */ listaCombinacion = (int*) malloc(numElementosCombinacion * sizeof(int)); if(numElementosCombinacion == 0) /* si ya se ha llegado al numero de elementos deseado */ { /* imprimir resultado */ for(i=0 ; i < paso ; i++) printf("%d ",listaCombinacion [i ]); return; } for(i=0 ; i <= numElementosLista - numElementosCombinacion ; i++) { listaCombinacion[paso] = lista[i]; /* poner el valor que corresponde en la combinacion */ combinaciones(lista + i + 1,numElementosLista - 1 - i,numElementosCombinacion - 1,paso+1); } if(paso == 0) /* si se ha teminado con la primera llamada */ { listaCombinacion=NULL; /* poner a NULL para sucesivas llamas a la funcion*/ } return; }
|
|
|
En línea
|
- Doctor, confundo los números y los colores. - Vaya marrón. - ¿Marrón? ¡Por el culo te la hinco!
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Programa que entretege todas las combinaciones posibles de letras de una palabra
Programación C/C++
|
freakx
|
0
|
5,374
|
23 Enero 2012, 04:55 am
por freakx
|
|
|
posibles combinaciones de sumas de campos
PHP
|
romanjr
|
0
|
1,934
|
15 Febrero 2012, 20:11 pm
por romanjr
|
|
|
Como saber todas las combinaciones posibles de letras y numeros?
Programación C/C++
|
peterfly
|
8
|
28,694
|
15 Julio 2012, 18:26 pm
por DickGumshoe
|
|
|
Crear un programa que genere todas las combinaciones posibles?
Programación General
|
Moffer
|
1
|
4,875
|
30 Diciembre 2013, 05:11 am
por drvalium
|
|
|
Posibles combinaciones de una palabra
Programación C/C++
|
giraffe
|
2
|
3,266
|
7 Abril 2015, 09:05 am
por eferion
|
|