¿Cómo puedo generar todos los subconjuntos de una lista en Perl?

Question

Tengo un conjunto matemático en una matriz Perl: (1, 2, 3). Me gustaría encontrar todos los subconjuntos de ese conjunto: (1), (2), (3), (1,2), (1,3), (2,3).

Con 3 elementos, esto no es demasiado difícil, pero si tiene 10 elementos, esto se pone complicado.

¿Pensamientos?

Answer 1

Ver Data::PowerSet, http://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.html, etc.

Answer 2

Puede utilizar Data::PowerSet como Mateo menciona. Sin embargo, si, como se indica en su ejemplo, solo desea los subconjuntos adecuados y no cada subconjunto, debe hacer un poco más de trabajo.

# result: all subsets, except {68, 22, 43}. 
    my $values = Data::PowerSet->new({max => 2}, 68, 22, 43); 

Del mismo modo, si desea omitir el conjunto nulo, sólo tiene que añadir el min parámetro:

# result: all subsets, except {} and {68, 22, 43}. 
    my $values = Data::PowerSet->new({min => 1, max => 2}, 68, 22, 43); 

De lo contrario, para obtener todos los subconjuntos, basta con omitir ambos parámetros:

# result: every subset. 
    my $values = Data::PowerSet->new(68, 22, 43); 

Answer 3

Use Algorithm::ChooseSubsets.

Answer 4

Como dice "conjunto matemático", supongo que quiere decir que no hay duplicados.

Una implementación ingenua que funciona para hasta 32 elementos:

my $set = [1,2,3]; 
my @subsets; 
for my $count (1..(1<<@$set)-2) { 
    push @subsets, [ map $count & (1<<$_) ? $set->[$_] :(), 0..$#$set ]; 
} 

(Para la gama completa de subconjuntos, bucle de 0 a (1 < < @ $ set) -1; excluyendo 0 excluye la hipótesis nula set, excluyendo (1 < < @ $ set) -1 excluye el conjunto original.)

Actualización: No estoy defendiendo esto sobre el uso de un módulo, solo lo sugiero en caso de que esté buscando entender cómo hacerlo Qué problema. En general, cada elemento está incluido o excluido de cualquier subconjunto dado. Desea elegir un elemento y generar primero todos los subconjuntos posibles de los otros elementos sin incluir su elemento elegido y luego todos los subconjuntos posibles de los otros elementos, incluido su elemento elegido. Aplique recursivamente esto a "generar todos los subconjuntos posibles". Finalmente, descarte el subconjunto nulo y el subconjunto no apropiado. En el código anterior, a cada elemento se le asigna un bit. En primer lugar, todos los subconjuntos se generan con el bit alto activado y luego con todos los que están apagados. Para cada una de esas alternativas, los subconjuntos se generan primero con el bit más próximo al más alto desactivado y luego activo. Continuando con esto hasta que estés trabajando en la parte más baja, con lo que terminas es con todos los números posibles, en orden.

Answer 5

Si no desea utilizar un módulo existente o no puede, simplemente puede codificar su propio algoritmo de generación de subconjuntos utilizando un bit-mask and a binary counter. El código de ejemplo siguiente -

#!/usr/bin/perl 
use strict; 
use warnings; 

my @set  = (1, 2, 3); 
my @bitMask = (0, 0, 0); #Same size as @set, initially filled with zeroes 

printSubset(\@bitMask, \@set) while (genMask(\@bitMask, \@set)); 

sub printSubset { 
    my ($bitMask, $set) = @_; 

    for (0 .. @$bitMask-1) { 
    print "$set->[$_]" if $bitMask->[$_] == 1; 
    } 
    print"\n"; 

} 

sub genMask { 
    my ($bitMask, $set) = @_; 

    my $i; 
    for ($i = 0; $i < @$set && $bitMask->[$i]; $i++) { 
    $bitMask->[$i] = 0; 
    } 

    if ($i < @$set) { 
    $bitMask->[$i] = 1; 
    return 1; 
    } 

    return 0; 
} 

Nota: No he podido probar el código, algunos errores pueden necesitar ser subsanadas.

Answer 6

Es un problema de conteo - para N elementos hay exactamente 2^N subconjuntos y tiene que contar de 0 a 2^N - 1 en binario para listarlos todos.

Por ejemplo, 3 elementos hay 8 posibles subconjuntos: 000, 001, 010, 011, 100, 101, 110 y 111 - los números muestran qué miembros están presentes.