Perl 6 Tips - 排列组合

Quick Tip #16: 探索组合

xx 是列表重复操作符, 用于将一个列表重复指定的次数。xx 不会展平列表中的元素。

1
2
3
4
5
6
$ perl6
> my @n = <1 2 3>;
[1 2 3]
> my $n = 4;
4
> my @c = @n xx $n

输出:

1
[[1 2 3] [1 2 3] [1 2 3] [1 2 3]]

现在我想要长度为 $n 的一堆列表的所有排列(combinations):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> ( [X] ( @n xx $n ) )
((1 1 1 1) (1 1 1 2) (1 1 1 3) (1 1 2 1) (1 1 2 2) (1 1 2 3)
(1 1 3 1) (1 1 3 2) (1 1 3 3) (1 2 1 1) (1 2 1 2) (1 2 1 3)
(1 2 2 1) (1 2 2 2) (1 2 2 3) (1 2 3 1) (1 2 3 2) (1 2 3 3)
(1 3 1 1) (1 3 1 2) (1 3 1 3) (1 3 2 1) (1 3 2 2) (1 3 2 3)
(1 3 3 1) (1 3 3 2) (1 3 3 3) (2 1 1 1) (2 1 1 2) (2 1 1 3)
(2 1 2 1) (2 1 2 2) (2 1 2 3) (2 1 3 1) (2 1 3 2) (2 1 3 3)
(2 2 1 1) (2 2 1 2) (2 2 1 3) (2 2 2 1) (2 2 2 2) (2 2 2 3)
(2 2 3 1) (2 2 3 2) (2 2 3 3) (2 3 1 1) (2 3 1 2) (2 3 1 3)
(2 3 2 1) (2 3 2 2) (2 3 2 3) (2 3 3 1) (2 3 3 2) (2 3 3 3)
(3 1 1 1) (3 1 1 2) (3 1 1 3) (3 1 2 1) (3 1 2 2) (3 1 2 3)
(3 1 3 1) (3 1 3 2) (3 1 3 3) (3 2 1 1) (3 2 1 2) (3 2 1 3)
(3 2 2 1) (3 2 2 2) (3 2 2 3) (3 2 3 1) (3 2 3 2) (3 2 3 3)
(3 3 1 1) (3 3 1 2) (3 3 1 3) (3 3 2 1) (3 3 2 2) (3 3 2 3)
(3 3 3 1) (3 3 3 2) (3 3 3 3))

注意,排列是不一样的,它更简单,因为有一个方法来生成排列:

1
2
> @n.permutations
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

我们来一步一步分解上面那个排列的例子:

首先,要有一个列表:

1
2
> (1, 2, 3)
( 1 2 3)

现在我想重复这个列表:

1
2
> (1, 2, 3) xx 2
((1 2 3) (1 2 3))

插一句, 如果你不喜欢这种格式,你可以使用 | 来“解容器化”这个小列表,以使它失去结构:

1
2
> |(1, 2, 3) xx 2
(1 2 3 1 2 3)

然而我想保留列表结构,以使我能组合两个列表的拷贝。下一步就是交叉:

1
2
> (1, 2, 3) X ( 1, 2, 3 )
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

现在使用两个列表来做 reduction, 得到同样的结果:

1
2
> [X] (1, 2, 3), (1, 2, 3)
((1 1) (1 2) (1 3) (2 1) (2 2) (2 3) (3 1) (3 2) (3 3))

记住: [OP] element1, element2, element3… 等价于:

1
element1 OP element2 OP element3 OP ...

我可以对这些列表应用工具函数,我可以grep过滤那些:

1
2
> ( [X] @n xx 5 ).grep( { .sum > 13 } )
((2 3 3 3 3) (3 2 3 3 3) (3 3 2 3 3) (3 3 3 2 3) (3 3 3 3 2) (3 3 3 3 3))

但是我还可以做的更好!我想分割那个大数据集。我能调用 categorize 方法。三元操作符返回的字符串就是对应项所属的散列键。我得到了一个散列,每个键拥有一个关联该键的数组:

1
2
> ( [X] @n xx 5 ).categorize( { .sum > 13 ?? 'pass' !! 'fail' } )
{fail => [(1 1 1 1 1) ... (3 3 3 3 1)], pass => [(2 3 3 3 3) (3 2 3 3 3) (3 3 2 3 3) (3 3 3 2 3) (3 3 3 3 2) (3 3 3 3 3)]}

categorize 的定义:

1
2
multi sub categorize(&mapper, *@values --> Hash:D)
multi method categorize(List:D: &mapper --> Hash:D)

根据映射器将值列表转换为表示这些「值的分类」的散列; 每个散列键表示一个可能的分类,并且相应的散列值包含由映射器分类到相关联的键的类别中的那些列表值的数组。

请注意,与classify假定 mapper 的返回值是单个值不同,classificationize 总是假定 mapper 的返回值是适合当前值的类别列表。

例子:

1
2
3
4
5
6
sub mapper(Int $i) returns List {
$i %% 2 ?? 'even' !! 'odd',
$i.is-prime ?? 'prime' !! 'not prime'
}
say categorize &mapper, (1, 7, 6, 3, 2); # {even => [6 2], not prime => [1 6],
# odd => [1 7 3], prime => [7 3 2]}
------ Young For Perl 6! ------