直積の導出と考えうる全ての値を網羅したハッシュの生成

昨日から激しく悩んでいた内容で、id:kazuhookuさんとnishioさんに色々教わったので、その内容のまとめ。

やりたい事

my $entries = {
  A => [0..5],
  B => ["A".."D"],
  C => ["a".."c"]
};

みたいな集合A, B, Cってのがあるとして、A, B, Cから一個ずつ値を抽出してくる組合せを列挙すると言うお話。

ちなみに場合の数として、6 * 4 * 3 = 72 通り存在するハズです。

List::Utilのreduceを使う

id:kazuhookuさん案を適当に整形。

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dump qw(dump);
use List::Util qw(reduce);

my $entries = {
    A => [0..5],
    B => ["A".."D"],
    C => ["a".."c"]
};

{
    no warnings;
    my $j = reduce { [map { my $x = $_; map { (ref $x eq "ARRAY") ? [@$x, $_] : [$x, $_] } @$b; } @$a] } values %$entries;
    print dump(@$j);
}

Set::CrossProductを使う。

CrossProductは数学では「直積」と言うとnishioさんに教えて貰いました。

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dump qw(dump);
use Set::CrossProduct;

my $entries = {
    A => [0..5],
    B => ["A".."D"],
    C => ["a".."c"]
};

my $cp = Set::CrossProduct->new([values %$entries]);

print dump($cp->combinations);

これで列挙されるです。

で、何に使うのか

テスト用のデータの組合せをゴリゴリ作りたいとかって時に便利だったりします。
例えばこんな感じ。

#!/usr/bin/perl

use strict;
use warnings;

use Data::Dump qw(dump);

use DateTime;
use DateTime::Duration;
use DateTime::Format::HTTP;
use Set::CrossProduct;
use Text::SimpleTable;

my $date = DateTime::Format::HTTP->format_datetime(DateTime->now - DateTime::Duration->new(minutes => 30));

my $entries = {
    'Cache-Control' => [q|max-age=0|, q|max-age=300|, undef],
    'If-None-Match' => [q|"1111"|, q|"2222"|, undef],
    'If-Modified-Since' => [$date, undef]
};

my $cp = Set::CrossProduct->new([values %$entries]);
my @headers = ();

for my $header_vals ($cp->combinations) {
    my %header;

    @header{keys %$entries} = @$header_vals;
    push(@headers, \%header);
}

my $table = Text::SimpleTable->new([20, "Cache-Control"], [20, "If-None-Match"], [20, "If-Modified-Since"]);

for (@headers) {
    $table->row(values %$_);
}

print $table->draw;

で、実行結果。

.----------------------+----------------------+----------------------.
| Cache-Control        | If-None-Match        | If-Modified-Since    |
+----------------------+----------------------+----------------------+
| max-age=0            | "1111"               | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
| max-age=0            | "2222"               | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
| max-age=0            |                      | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
| max-age=0            | "1111"               |                      |
| max-age=0            | "2222"               |                      |
| max-age=0            |                      |                      |
| max-age=300          | "1111"               | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
| max-age=300          | "2222"               | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
| max-age=300          |                      | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
| max-age=300          | "1111"               |                      |
| max-age=300          | "2222"               |                      |
| max-age=300          |                      |                      |
|                      | "1111"               | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
|                      | "2222"               | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
|                      |                      | Tue, 14 Aug 2007 07- |
|                      |                      | :01:57 GMT           |
|                      | "1111"               |                      |
|                      | "2222"               |                      |
'----------------------+----------------------+----------------------'

その他

この過程でだいぶ寄り道して見つけて面白かったモジュール。

Math::Combinatorics

順列、組合せ、重複組合せなど使いたい場合はこちらを使うと良いです。

あとソースと結果はちょっと直しました。