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

Question

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

Как насчет GetReferencedAssemblies для обработки записей метаданных AssemblyRef? «Решение» - это не то, что CLR знает или заботится о нем… оно имеет дело с Ассамблеями.

private static List GetListOfEntryAssemblyWithReferences()
{
  List listOfAssemblies = new List();
  var mainAsm = Assembly.GetEntryAssembly();
  listOfAssemblies.Add(mainAsm);

  foreach (var refAsmName in mainAsm.GetReferencedAssemblies())
  {
    listOfAssemblies.Add(Assembly.Load(refAsmName));
  }
  return listOfAssemblies;
}

Предостережения:
1. Вам все еще нужно отфильтровать сборки ядра System. * 2. Это всего лишь один уровень в цепочке ссылок ... но это можно сделать рекурсивно - с помощью большего количества кода.

5

perl set subset

задан Ether 11 October 2009 в 04:05

6 ответов

Другие вопросы по тегам:

perl set subset

Похожие вопросы:

score 12 · 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);

score 4 · Answer 2

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

4

ответ дан 18 December 2019 в 07:10

score 3 · 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 исключает исходный набор.)

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

score 1 · Answer 4

If you don't want to use an existing module or can't then you can simply code your own subset generation algorithm using a bit-mask and a binary counter. Sample code follows -

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

Note: I haven't been able to test the code, some bugs might need to be ironed out.

score 1 · Answer 5

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

1

ответ дан 18 December 2019 в 07:10

score 1 · Answer 6

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

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