В Perl, как я могу перебирать декартово произведение нескольких множеств?

Question

Дано x Количество массивов, каждый с возможно различным количеством элементов, как я могу перебирать все комбинации, где я выбираю один элемент из каждого массива?

Пример:

[ ] [ ] [ ] 
foo  cat  1 
bar  dog  2 
baz    3 
        4 

Возвращает

[foo] [cat] [ 1 ] 
[foo] [cat] [ 2 ] 
    ... 
[baz] [dog] [ 4 ] 

я делаю это в Perl, кстати.

Answer 1

Рекурсивные и более-текучие примеры Perl (с комментариями и документацией) для ведения декартово произведение можно найти на http://www.perlmonks.org/?node_id=7366

Пример:

sub cartesian { 
    my @C = map { [ $_ ] } @{ shift @_ }; 

    foreach (@_) { 
     my @A = @$_; 

     @C = map { my $n = $_; map { [ $n, @$_ ] } @C } @A; 
    } 

    return @C; 
} 

Answer 2

Простое рекурсивное решения для произвольного числа списков:

sub permute { 
    my ($first_list, @remain) = @_; 

    unless (defined($first_list)) { 
    return []; # only possibility is the null set 
    } 

    my @accum; 
    for my $elem (@$first_list) { 
    push @accum, (map { [$elem, @$_] } permute(@remain)); 
    } 

    return @accum; 
} 

А, не столь простым нерекурсивно решением для произвольного числа списков:

sub make_generator { 
    my @lists = reverse @_; 

    my @state = map { 0 } @lists; 

    return sub { 
    my $i = 0; 

    return undef unless defined $state[0]; 

    while ($i < @lists) { 
     $state[$i]++; 
     last if $state[$i] < scalar @{$lists[$i]}; 
     $state[$i] = 0; 
     $i++; 
    } 

    if ($i >= @state) { 
     ## Sabotage things so we don't produce any more values 
     $state[0] = undef; 
     return undef; 
    } 

    my @out; 
    for (0..$#state) { 
     push @out, $lists[$_][$state[$_]]; 
    } 

    return [reverse @out]; 
    }; 
} 

my $gen = make_generator([qw/foo bar baz/], [qw/cat dog/], [1..4]); 
while ($_ = $gen->()) { 
    print join(", ", @$_), "\n"; 
} 

Answer 3

Там один метод, который я думал о первом, который использует пару для циклов и никакой рекурсии.

1. найти общее число перестановок
2. цикл от 0 до total_permutations-1
3. заметить, что, принимая индекс цикла MODULUS число элементов в массиве, вы можете получить все перестановки

Пример:

Учитывая А [3], В [2], С [3],

for (index = 0..totalpermutations) { 
    print A[index % 3]; 
    print B[(index/3) % 2]; 
    print C[(index/6) % 3]; 
} 

где, конечно, цикл for может быть заменен на цикл над [A B C ...], а небольшая часть может быть замечена. Конечно, рекурсия более аккуратная, но это может быть полезно для языков, в которых рекурсия сильно ограничена размером стека.

Answer 4

Модуль Set::CrossProduct делает именно то, что вы хотите. Обратите внимание, что вы действительно не ищете перестановки, которые являются упорядочением элементов в наборе. Вы ищете кросс-продукт, который представляет собой комбинацию элементов из разных наборов.

Мой модуль дает вам итератор, поэтому вы не создаете его все в памяти. Вы создаете новый кортеж только тогда, когда вам это нужно.