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

Question

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

С 3 элементами это не так уж сложно, но если в наборе 10 элементов, это будет сложно.

Мысли

Answer 1

Вы можете использовать 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 2

См. Данные :: PowerSet , http://coding.derkeiler.com/Archive/Perl/comp.lang.perl/2004-01/0076.html и т. Д.

Answer 3

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

Наивная реализация, которая работает до 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 << @ $ set) -1; исключение 0 исключает нулевой набор, исключая (1 << @ $ set) -1 исключает исходный набор.) </p>

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

Answer 4

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

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

Answer 5

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

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

Использование Алгоритм :: ChooseSubsets .