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

Ответ 1

Это на самом деле не перестановка, а декартово произведение. См. Math :: Cartesian :: Product.

#!/usr/bin/perl

use strict; use warnings;

use Math::Cartesian::Product;

cartesian { print "@_\n" }
    ["big", "tiny", "small"],
    ["red", "yellow", "green"],
    ["apple", "pear", "banana"];

Выход:

C:\Temp> uu
big red apple
big red pear
big red banana
big yellow apple
big yellow pear
big yellow banana
big green apple
big green pear
big green banana
tiny red apple
tiny red pear
tiny red banana
tiny yellow apple
tiny yellow pear
tiny yellow banana
tiny green apple
tiny green pear
tiny green banana
small red apple
small red pear
small red banana
small yellow apple
small yellow pear
small yellow banana
small green apple
small green pear
small green banana

Ответ 2

Мне пришлось решить эту точную проблему несколько лет назад. Я не смог придумать свое решение, но вместо этого столкнулся с этим замечательным фрагментом кода, который включает умное и разумное использование map наряду с рекурсией:

#!/usr/bin/perl

print "permute:\n";
print "[", join(", ", @$_), "]\n" for permute([1,2,3], [4,5,6], [7,8,9]);

sub permute {

    my $last = pop @_;

    unless(@_) {
           return map([$_], @$last);
    }

    return map { 
                 my $left = $_; 
                 map([@$left, $_], @$last)
               } 
               permute(@_);
}

Да, это выглядит сумасшедшим, но позвольте мне объяснить! Функция будет возвращаться до тех пор, пока @_ не будет пуст, и в этот момент она вернет ([1], [2], [3]) (список из трех элементов массива) к предыдущему уровню рекурсии. На этом уровне $last есть ссылка на массив, содержащий [4, 5, 6].

Затем тело внешнего отображения выполняется три раза с $_, установленным на [1], затем [2] и, наконец, [3]. Затем внутренняя карта выполняется над (4, 5, 6) для каждой итерации внешнего отображения, и это возвращает ([1, 4], [1, 5], [1, 6]), ([2, 4], [2, 5], [2, 6]) и, наконец, ([3, 4], [3, 5], [3, 6]).

Последний, но один рекурсивный вызов возвращает ([1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]).

Затем он запускает этот результат против [7,8,9], который дает вам [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 7], [1, 6, 8], [1, 6, 9], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 7], [2, 6, 8], [2, 6, 9], [3, 4, 7], [3, 4, 8], [3, 4, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 7], [3, 6, 8], [3, 6, 9]

Я помню, как публиковал вопрос о perlmonks.org, прося кого-нибудь объяснить это мне.

Вы можете легко адаптировать это решение к своей проблеме.

Ответ 3

Теперь в твиттер-форме:

sub prod { reduce { [ map { my $i = $_; map [ @$_, $i ], @$a } @$b ] } [[]], @_ }

use strict;
use warnings;
use List::Util qw(reduce);

sub cartesian_product {
  reduce {
    [ map {
      my $item = $_;
      map [ @$_, $item ], @$a
    } @$b ]
  } [[]], @_
}

Ответ 4

Вы можете использовать мой Set:: CrossProduct, если хотите. Вам не нужно проходить через все пространство, так как оно дает вам итератор, поэтому вы контролируете.

Ответ 5

IF

• вы не хотите включать зависимости
• у вас небольшое количество массивов
• ваши массивы не очень большие

, затем вы можете просто сделать это:

Для двух массивов @xs и @ys:

map{ my $x = $_; map { [$x, $_] } @ys } @xs

Для трех массивов @xs, @ys, @zs

map{ my $x = $_; map { my $y = $_; map { [$x, $y, $_] } @zs } @ys } @xs