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

Question

Я хочу сделать перестановку в Perl. Например, у меня есть три массива: ["big", "tiny", "small"], а затем у меня есть ["red", "yellow", "green"], а также ["apple", "pear", "banana"].

Как мне получить:

["big", "red", "apple"]
["big", "red", "pear"]

..etc..

["small", "green", "banana"]

Я понимаю, что это называется перестановкой. Но я не уверен, как это сделать. Также я не знаю, сколько массивов я могу иметь. Может быть три или четыре, поэтому я не хочу делать вложенный цикл.

Answer 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

Answer 2

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

Answer 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 ]
  } [[]], @_
}

Answer 4

Я должен был решить эту проблему несколько лет назад. Я не смог придумать свое собственное решение, но вместо этого наткнулся на этот замечательный кусок кода, который включает в себя умное и разумное использование 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 с просьбой объяснить мне это.

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

Answer 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