elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Ejercicio: las posibles combinaciones de una lista [python]
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ejercicio: las posibles combinaciones de una lista [python]  (Leído 16,375 veces)
Ragnarok
Colaborador
***
Desconectado Desconectado

Mensajes: 4.588


Shrödingerificado


Ver Perfil
Ejercicio: las posibles combinaciones de una lista [python]
« en: 3 Septiembre 2009, 15:46 pm »

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

No olvidéis leer las normas generales, además de las específicas de cada tablón.sgae, ladrones
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Ejercicio: las posibles combinaciones de una lista [python]
« Respuesta #1 en: 4 Septiembre 2009, 13:47 pm »

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 Desconectado

Mensajes: 1.900



Ver Perfil
Re: Ejercicio: las posibles combinaciones de una lista [python]
« Respuesta #2 en: 4 Septiembre 2009, 17:58 pm »

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:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef vector<int> VI;
  6. typedef vector<bool> VB;
  7.  
  8. void rec(VI& v, VB& usado, int cnt, int primero, int n) {
  9.    if (cnt == n) {
  10.        cout << "{";
  11.        bool first = true;
  12.        for (int i = 0; i < usado.size(); ++i) {
  13.            if (usado[i]) {
  14.                if (first) first = false;
  15.                else cout << ",";
  16.                cout << v[i];
  17.            }
  18.        }
  19.        cout << "}" << endl;
  20.        return;
  21.    }
  22.    for (int i = primero; i < v.size(); ++i) {
  23.        usado[i] = true;
  24.        rec(v, usado, cnt + 1, i + 1, n);
  25.        usado[i] = false;
  26.    }
  27. }
  28.  
  29. int main() {
  30.    int n;
  31.    cin >> n; //numero de elementos;
  32.    VI v(n);
  33.    for (int i = 0; i < n; ++i) cin >> v[i];
  34.    for (int i = 0; i <= n; ++i) {
  35.        cout << "Subconjuntos de " << i << " elementos:" << endl;
  36.        VB usado(n, false);
  37.        rec(v, usado, 0, 0, i); //genera los subconjuntos de v de i elementos (habra n sobre i)
  38.        cout << endl;
  39.    }
  40. }
  41.  

Un saludo de ghastlyX ;)
En línea

Ragnarok
Colaborador
***
Desconectado Desconectado

Mensajes: 4.588


Shrödingerificado


Ver Perfil
Re: Ejercicio: las posibles combinaciones de una lista [python]
« Respuesta #3 en: 6 Septiembre 2009, 02:35 am »

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.

Código
  1. def lattice(l):
  2.  s = [[]]
  3.  for e in l:
  4.    ns = []
  5.    for ps in s:
  6.      nps = ps[:]
  7.      nps.append(e)
  8.      ns.append(nps)
  9.    s = s + ns
  10.  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:
Código
  1. def lattice(l):
  2.  if l == []:
  3.    return [[]]
  4.  ll = lattice(l[1:])
  5.  return [e+[l[0]] for e in ll] + ll
« Última modificación: 6 Septiembre 2009, 03:01 am por Ragnarok » En línea

No olvidéis leer las normas generales, además de las específicas de cada tablón.sgae, ladrones
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Ejercicio: las posibles combinaciones de una lista [python]
« Respuesta #4 en: 9 Septiembre 2009, 18:52 pm »

Aqui esta mi solucion. :)

Hay soluciones para hartarse...  ;D
Código
  1. void combinaciones(int lista[],int numElementosLista,int numElementosCombinacion,int paso)
  2. {
  3.    int i;
  4.    static int *listaCombinacion=NULL;
  5.  
  6.    if(numElementosLista < numElementosCombinacion)
  7.        return;
  8.  
  9.    if(!listaCombinacion) /* si la lista esta sin inicializar -> reservar memoria */
  10.        listaCombinacion = (int*) malloc(numElementosCombinacion * sizeof(int));
  11.  
  12.    if(numElementosCombinacion == 0) /* si ya se ha llegado al numero de elementos deseado */
  13.    {
  14.        /* imprimir resultado */
  15.        for(i=0 ; i < paso ; i++)
  16.            printf("%d ",listaCombinacion[i]);
  17.        printf("\n");
  18.  
  19.        return;
  20.    }
  21.  
  22.    for(i=0 ; i <= numElementosLista - numElementosCombinacion ; i++)
  23.    {
  24.        listaCombinacion[paso] = lista[i]; /* poner el valor que corresponde en la combinacion */
  25.        combinaciones(lista + i + 1,numElementosLista - 1 - i,numElementosCombinacion - 1,paso+1);
  26.    }
  27.  
  28.    if(paso == 0) /* si se ha teminado con la primera llamada */
  29.    {
  30.        free(listaCombinacion);
  31.        listaCombinacion=NULL; /* poner a NULL para sucesivas llamas a la funcion*/
  32.    }
  33.  
  34.    return;
  35. }
  36.  
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Ejercicio: las posibles combinaciones de una lista [python]
« Respuesta #5 en: 9 Septiembre 2009, 22:16 pm »

En el siguuieinte post hay un enlace con codigo en C sobre este tema.

http://foro.elhacker.net/programacion_cc/combinatoria_code-t266973.0.html

Espero que sirva de algo. :)

Hasta pronto!!!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines