sintaxis - ¿Cómo puedo generar todos los subconjuntos de una lista en Perl?
sintaxis de perl (6)
Tengo un conjunto matemático en una matriz de 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, se vuelve complicado.
¿Pensamientos?
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 toda la gama de subconjuntos, bucle de 0 a (1 << @ $ establecer) -1; excluir 0 excluye el conjunto nulo, excluyendo (1 << @ $ set) -1 excluye el conjunto original.)
Actualización: No estoy abogando por el uso de un módulo, simplemente sugiriéndolo en caso de que esté buscando entender cómo solucionarlo. 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 desactivados. 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.
Es un problema de conteo: para N elementos hay exactamente 2 ^ N subconjuntos y debe contar de 0 a 2 ^ N - 1 en binario para enumerarlos a 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.
Puede usar Data :: PowerSet como mencionó Matthew. Sin embargo, si, como se indica en su ejemplo, solo desea los subconjuntos adecuados y no todos los subconjuntos, 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, simplemente agregue el parámetro min :
# 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, simplemente omita ambos parámetros:
# result: every subset.
my $values = Data::PowerSet->new(68, 22, 43);
Si no desea utilizar un módulo existente o no puede, simplemente puede codificar su propio algoritmo de generación de subconjuntos utilizando una máscara de bits y un contador binario . El código de muestra sigue -
#!/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, es posible que haya que corregir algunos errores.
Utilice Algorithm :: ChooseSubsets .