В Perl, как я могу получить Декартово пересечение нескольких множеств?
Я хочу сделать перестановку в Perl. Например, у меня есть три массива: ["big", "tiny", "small"] и затем я имею ["red", "yellow", "green"] и также ["apple", "pear", "banana"].
Как делают я добираюсь:
["big", "red", "apple"] ["big", "red", "pear"] ..etc.. ["small", "green", "banana"]
Я понимаю, что это называют перестановкой. Но я не уверен, как сделать это. Также я не знаю, сколько массивов я могу иметь. Может быть три или четыре, таким образом, я не хочу делать вложенный цикл.
4 ответа
На самом деле это не перестановка, а декартово произведение. See 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"];
Output:
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
Несколько лет назад мне пришлось решить именно эту проблему. Я не смог придумать собственное решение, но вместо этого наткнулся на этот замечательный фрагмент кода, который включает в себя умное и разумное использование 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, прося кого-нибудь объяснить мне это.
Вы можете легко адаптировать это решение к своей проблеме.
Теперь в твиттер-форме:
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 ]
} [[]], @_
}
Вы можете использовать мой Set :: CrossProduct модуль, если хотите. Вам не нужно перемещаться по всему пространству, поскольку он дает вам итератор, поэтому вы все контролируете.