Как я могу сгенерировать все подмножества списка в Perl?

Question

У меня есть математический набор в массиве Perl: (1, 2, 3). Я бы хотел найти все подмножества этого множества: (1), (2), (3), (1,2), (1,3), (2,3).

С 3 элементами это не слишком сложно, но если установлено 10 элементов, это становится сложным.

Мысли?

Answer 1

См Data::PowerSet, http://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.html и т.д.

Answer 2

Вы можете использовать Data::PowerSet как упоминалось Мэтью. Однако, если, как указано в вашем примере, вам нужны только правильные подмножества, а не все подмножества, вам нужно сделать немного больше работы.

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

Аналогично, если вы хотите, чтобы пропустить множество нулевой, просто добавьте min параметр:

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

В противном случае, чтобы получить все подмножества, просто опустить оба параметра:

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

Answer 3

Используйте Algorithm::ChooseSubsets.

Answer 4

Поскольку вы говорите «математический набор», я предполагаю, что вы имеете в виду, что нет дубликатов.

наивная реализация, которая работает до 32 элементов:

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

(Для полного спектра подмножеств, цикл от 0 до (1 < < @ $ набор) -1, за исключением 0 исключает нуль (1 < < @ $ set) -1 исключает исходный комплект.)

Обновление: Я не рекомендую это использовать модуль, просто предлагая его на случай, если вы хотите понять, как это сделать такая проблема. В общем, каждый элемент либо включен, либо исключен из любого данного подмножества. Вы хотите выбрать элемент и сгенерировать сначала все возможные подмножества других элементов, не включая выбранный вами элемент, а затем все возможные подмножества других элементов, включая выбранный вами элемент. Рекурсивно применяйте это к «генерации всех возможных подмножеств». Наконец, отбросьте нулевое подмножество и неправильное подмножество. В приведенном выше коде каждому элементу присваивается бит. Сначала все подмножества генерируются с высоким битом, а затем все с отключенным. Для каждой из этих альтернатив подмножества генерируются сначала с выключенным рядом с самым высоким, а затем. Продолжая это, пока вы просто не работаете над самым низким битом, все, что у вас получается, - это все возможные числа в порядке.

Answer 5

Если вы не хотите использовать существующий модуль или не можете, вы можете просто закодировать свой собственный алгоритм генерации подмножества, используя bit-mask and a binary counter. Пример кода следующим образом -

#!/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; 
} 

Примечание: Я не был в состоянии проверить код, некоторые ошибки, возможно, придется быть устранены.

Answer 6

Это проблема подсчета - для N элементов есть ровно 2^N подмножеств, и вам нужно подсчитать от 0 до 2^N - 1 в двоичном формате, чтобы перечислить их все.

Например, для 3 предметов имеется 8 возможных подмножеств: 000, 001, 010, 011, 100, 101, 110 и 111 - номера показывают, какие элементы присутствуют.