とあるタスクにおいて、重複を持たない組合せ（コンビネーション）を羅列する必要があったので、復習も兼ねてPerlでゼロから書いてみた。
（参考：Wikipedia:組合せ_(数学)）

異なる n 個のものから異なる m 個を選ぶ。高校の数学でやった「場合の数」。



数はどうでもいいので、実際の組み合わせを深さ優先と幅優先の両方の方式で羅列する。汎用性のため、リスト（配列）そのものから選ぶのではなく、インデックス（配列の添字）から選ぶ。

■コード(combination.pl)：

#!/usr/bin/perl
use strict;
use warnings;

my @chars = qw(A B C D E F G H I J K);
my $n = 5; # 全体の数
my $m = 3; # 選ぶ数

my @results = ();
df_combination($n, $m, []);
print join("", map {join(",", @$_)."\n"}  @results);
print join("", map {join("", map {$chars[$_]} @$_)."\n"}  @results);

@results = ();
bf_combination($n, $m, []);
print join("", map {join(",", @$_)."\n"}  @results);
print join("", map {join("", map {$chars[$_]} @$_)."\n"}  @results);

# 深さ優先探索 Depth first search
sub df_combination {
    my ($n, $m, $p_ref) = @_;
    if (@$p_ref == $m) {
        push @results, $p_ref;
        return;
    }
    my $lv = (not @$p_ref) ? 0 : $p_ref->[-1] + 1;
    for (my $i = $lv; $i < $n; $i++) {
        df_combination($n, $m, [@$p_ref, $i]);
    }
}

# 幅優先探索 Breadth first search
sub bf_combination {
    my ($n, $m) = @_;
    my @nodes = map {[$_]} (0..$n-1);
    while (@nodes) {
        my $v = shift @nodes;
        my @vs = @$v;
        if (@vs == $m) {
            push @results, $v;
            next;
        }
        my $lv = $vs[$#vs];
        foreach my $i ($lv+1..$n-1) {
            push @nodes, [@vs, $i];
        }
    }
}

■実行例：

./combination.pl
0,1,2
0,1,3
0,1,4
0,2,3
0,2,4
0,3,4
1,2,3
1,2,4
1,3,4
2,3,4
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
0,1,2
0,1,3
0,1,4
0,2,3
0,2,4
0,3,4
1,2,3
1,2,4
1,3,4
2,3,4
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE