Ejercicio: las posibles combinaciones de una lista [python]

[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.

[do-while]

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?

[ghastlyX]

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 (cpp) [Seleccionar] Expandir

#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

[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.

Código (python) [Seleccionar] Expandir

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:

Código (python) [Seleccionar] Expandir

def lattice(l):
  if l == []:
    return [[]]
  ll = lattice(l[1:])
  return [e+[l[0]] for e in ll] + ll

[do-while]

Aqui esta mi solucion.

Hay soluciones para hartarse... 

Código (c) [Seleccionar] Expandir


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]);
        printf("\n");

        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 */
    {
        free(listaCombinacion);
        listaCombinacion=NULL; /* poner a NULL para sucesivas llamas a la funcion*/
    }

    return;
}


[do-while]

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!!!