Ruby で配列の直積を得る

配列の直積とは何か，から始めて，任意個数の配列の直積を得る方法や，その応用を書く。

（投稿直後にバグに気づいて訂正した）

配列の直積とは

配列の直積とは何か。

以下のような二つの配列を考える。

a = ["佐藤", "鈴木"]
b = ["はるか", "ゆう", "ひろみ"]

そして，a の要素一つと b の要素を一つをこの順に並べた配列，たとえば

["佐藤", "ゆう"]

とか

["鈴木", "はるか"]

といったものを考える。
a と b の直積（direct product）とは，これのあらゆるパターンを集めた配列だ。
Array には直積を得る product という専用メソッドが用意されており，以下のように使う：

a.product(b)
# => 
# [["佐藤", "はるか"],
#  ["佐藤", "ゆう"],
#  ["佐藤", "ひろみ"],
#  ["鈴木", "はるか"],
#  ["鈴木", "ゆう"],
#  ["鈴木", "ひろみ"]]

返される配列の要素は，見てのとおり

• a の最初の要素に対して b の全要素を組み合わせ
• a の次の要素に対して b の全要素を組み合わせ

といった順に並んでいる。

数学の集合論の初歩を学んだ方は，直積集合 の考え方に似ていると気づくだろう。

用途

組合せを網羅的に取り扱うべきあらゆる場面で直積が役にたつ。

姓名の全ての組合せを表示したいとき，二重ループを使って

family_names = ["佐藤", "鈴木"]
given_names = ["はるか", "ゆう", "ひろみ"]

family_names.each do |family_name|
  given_names.each do |given_name|
    puts "#{ family_name } #{ given_name }"
  end
end

と書いてもいいのだが，直積を使って

family_names = ["佐藤", "鈴木"]
given_names = ["はるか", "ゆう", "ひろみ"]

family_names.product(given_names).each do |family_name, given_name|
  puts "#{ family_name } #{ given_name }"
end

と一重のループで済ますこともできる。

いや，実は Array#product にはブロック付き用法があるので，上記コードの .each を省いて

family_names = ["佐藤", "鈴木"]
given_names = ["はるか", "ゆう", "ひろみ"]

family_names.product(given_names) do |family_name, given_name|
  puts "#{ family_name } #{ given_name }"
end

とも書ける。こちらのほうが望ましい。

三つ以上の配列の直積

三つ以上の配列の直積というものも考えることができる。

これは，

a = ["A", "B"]
b = ["x", "y"]
c = [1, 2]

という配列があったら，

• a から要素を一つ
• b から要素を一つ
• c から要素を一つ

取り出して，それらを順に並べた配列の配列だ。
つまり，この例だと

[["A", "x", 1],
 ["A", "x", 2],
 ["A", "y", 1],
 ["A", "y", 2],
 ["B", "x", 1],
 ["B", "x", 2],
 ["B", "y", 1],
 ["B", "y", 2]]

となる。

Array#product には，引数として複数の配列を与えることができ，a, b, c の直積は

a.product(b, c)

で得られる。

だから，任意個数の配列の直積を得たければ，それを 配列の配列 として表現しておき，「最初の要素」と「残り」に分けて以下のように書くことができる。

arrays = [
  ["A", "B"],
  ["x", "y"],
  [1, 2]
]

arrays.first.product(*arrays[1..])

しかし気持ち悪い

さきほどのコードは少し気持ち悪い。
arrays の要素は対等なはずだ。なのに，最初とそれ以外に分けなければならない。

それに，上記のコードの場合，配列の配列が変数 arrays に入っていたからよかったが，もし式の返り値だったら，めんどくさい。
たとえば m というメソッドの返り値だったら，

arrays = m
product = arrays.first.product(*arrays[1..])

のようにいったん変数に代入するか，

product = m.then{ _1.first.product(*_1[1..]) }

のように then を使うことになる。
どちらも地味に嫌だ。

もう一つ考えておきたいのは，直積を取りたい配列が 2 個未満のときにどうなる（どうする）ということだ。
「ええっ？　1 個や 0 個の配列の直積なんて意味無いだろ？！」と思うかもしれないが，実はある。
これはあとで述べる。

提案：Array.product

前節で述べた問題は，直積を取りたい配列を引数に受け取る product というメソッドを作れば解決しそうだ。

そのメソッドをここで設計してみよう。

Array のクラスメソッドにする

汎用性が高そうなので，トップレベルに定義するのではなく，Array のクラスメソッド Array.product にしたい。

もちろん，グローバルに Array を改変するのは避けるべきなので，refinement を使って Array.product が使えるスコープを限定できるようにする。

refinement を使ってクラスメソッドを定義する方法は，以下の拙記事に。
【Ruby】refinement でクラスメソッドを定義するには - Qiita

メソッド名

メソッド名は，product だと，「商品」と紛らわしいとか，数学的にはいろんな「積」が考えられるよなあ，と思った。

だから direct_product にしようかと思ったけど，Array#product との整合性を考えると，やはり product がよさそうだ。

それに，Array のクラスメソッドとして定義するなら「product」だけで「配列の直積」と分かるだろう。

引数

引数は

• 配列の配列を与える
• 任意個の配列を与える

のどちらがよいだろうか。
つまり，配列 a, b, c の直積を得るのに

Array.product([a, b, c])

と書くのか

Array.product(a, b, c)

と書くのか。

当初，前者にしようと思った。
というのは，Array#product でなく Array.prodct を使いたい場面なら，配列の個数が不定であって「配列の配列」の形に既になっていることが多いだろうと思ったから。

しかし，Array#product の引数の与え方に合わせるなら後者になる。

ううむ，悩ましい。

とりあえず後者にしてみよう。

ブロック付き用法

Array#product と同様に，Array.product にもブロック付き用法を認めるべきだろう。

つまり，

Array.product array1, array2 do |elem1, elem2|
  # なんとかかんとか
end

のように使える，と。

ブロックを与えたときの返り値はどうあるべきか。
Array#product の場合，ブロックを与えたとき返り値は self である。
しかし，Array.product の場合は何を返してよいか分からない。
返り値を要する使い方は思いつかないので nil を返すことにしよう。

引数が 0 個，1 個のとき

引数が 0 個や 1 個のときはどういう動作になるべきだろうか。
言い換えれば，0 個や 1 個の配列の直積とは何だろうか（何であるべきだろうか）。

まず，配列が 2 個以上のとき，直積がどういう性質を持っているかを検討する。
いま，$A_1$, $A_2$, ..., $A_N$ という $N$ 個の配列があって，それの直積を $P$ としよう。
以下のことが言える。

• $P$ の要素はいずれも $A_1$, $A_2$, ..., $A_N$ の要素を一つずつ取り出し，この順に並べた配列である
• $P$ の要素は長さ $N$ の配列である
• $P$ の長さ（＝要素数）は，$A_1$, $A_2$, ..., $A_N$ の長さの積である

一番目は直積の定義そのものだ。二番目，三番目はそこから直ちに導かれる性質である。

引数が 1 個のとき

さきほどの「性質」を $N=1$ の場合に当てはめると，

• 配列 $A$ の直積 $P$ の要素はいずれも $A$ の要素一つを要素とする配列である
• 配列 $A$ の直積 $P$ の要素は長さ 1 の配列である
• 配列 $A$ の直積 $P$ の長さは $A$ の長さに等しい

となる。
つまり，配列 [1, 2, 3] の直積は [[1], [2], [3]] ということになる。

ここでちょっと，arrays が配列を一つだけ含んだ配列のときに

arrays.first.product(*arrays[1..])

がどうなるかを調べてみよう：

arrays = [[1, 2, 3]]
arrays.first.product(*arrays[1..])
# => [[1], [2], [3]]

ん？　うまくいったぞ（ちょっと意外）。
さきほど調べたとおりの結果になった。

どういうことだ？
まず，arrays が長さ 1 のとき，arrays[1..] は空配列 [] を返す。
すると，product メソッドの呼び出しは product(*[]) となるわけだが，これはスプラット展開のルールによれば引数なしで product を呼び出すことに等しい。
Array#product を引数なしで呼び出すと，self の要素を [ ] で包んだものの配列を返す。
なぜそういう仕様になっているかといえば，直積とはそういうものだからだ。

引数が 0 個のとき

引数無しの Array.product は何を返すべきだろうか。
以下，返り値を $P$ とする。

引数が 1 個以上の場合に倣えば，やはり $P$ は「配列の配列」であるべきだろう。

また，直積を取るべき配列が 0 個なので，$P$ の要素は「長さ 0 の配列」つまり空配列であるべきだろう。

では，$P$ の長さは何だろうか（何であるべきだろうか）。

$P$ が配列 $A_1$, $A_2$, ..., $A_N$ の直積であるとき，$A_i$ の長さを $L_i$ と書けば $P$ の長さは

L_1 \times L_2 \times \cdots \times L_N

であった。つまり $L_i$ の総積だ。
$N=0$ の場合，これは掛け算の単位元である 1 と考えるのが自然である（0 ではない）。

以上をまとめると，引数無しの Array.product の返り値は「長さ 1 の『空配列の配列』」つまり [[]] ということになる。

実装

仕様が完全に決まったので，実装に移ろう。
引数のチェック（引数が配列であるか）は省く。

module ArrayProduct
  refine Array.singleton_class do
    def product(*arrays, &)
      if block_given?
        if arrays.empty?
          yield []
        else
          arrays.first.product(*arrays[1..], &)
        end
        nil
      else
        if arrays.empty?
          [[]]
        else
          arrays.first.product(*arrays[1..])
        end
      end
    end
  end
end

これで，

using ArrayProduct

とすると，Array.product が使えるようになる。
モジュール名はもうちょっと良いのがないかな……と思うが。

無駄に複雑じゃね？

「arrays が空かどうか」と「ブロックが与えられているかどうか」で計 4 パターンに場合分けされていて，「もうちょっと簡潔に書けないの？」と首をひねるよね。
しかし，思いつかなかった。

もし，
「ブロック付き用法での返り値なんてどうせ使わないんだから，無理に nil を返すことにしなくてもいいんじゃね？」
ということであれば，もう少し簡単になるだろう。

それから
「とりあえず直積を得ておいて，ブロック付きのときはそれを each してやればいいんじゃね？」
と思うかもしれないが，長さ 1 万の配列同士の直積は長さ 1 億になっちゃうので，そういう巨大配列を作らずにループを回したいこともあるだろうから却下。

使ってみる：全約数を得る

1 以上の整数について，そのすべての約数を昇順に並べた配列を返すメソッド Integer#divisors を定義してみよう。

大きな整数について効率よくやるには，素因数分解を使うとよい。

なお，6 の約数は 1, 2, 3, 6 の四つ。1 の約数は 1 のみだ。

以下，ArrayProduct モジュールのコードは略す。

require "prime"

module IntegerDivisors
  refine Integer do
    using ArrayProduct

    def divisors
      prime_powers = prime_division.map{ |p, e| (0..e).map{ p ** _1 } }
      Array.product(*prime_powers).map{ _1.inject(1, :*) }.sort
    end
  end
end

using IntegerDivisors

p 12.divisors
# => [1, 2, 3, 4, 6, 12]

p 65536.divisors
# => [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536]

p 65537.divisors
# => [1, 65537]

解説

divisors メソッドの中身をちょっと解説しておこう。

Integer#prime_division は，prime ライブラリーが提供する素因数分解のメソッドだ。

たとえば 63 を素因数分解すると $3^2\cdot 7$ となるが，これを以下のように返す：

require "prime"

p 63.prime_division # => [[3, 2], [7, 1]]

要するに，「[素因数, 指数] の配列」を返すわけだ。
63 の約数は，

3^n \cdot 7^m \quad (n \in \{0, 1, 2\},\; m \in \{0, 1\})

という形をしている。
ここで直積の出番となる。
つまり $3^0, 3^1, 3^2$ の配列と $7^0, 7^1$ の配列を用意し，それらの直積を作る。
その各要素について，積をとれば 63 の約数となる。
素因数分解の定義からして，重複は無く，漏れも無い。

[3, 2] という配列（素因数と指数を並べたもの）から [1, 3, 9] を得るのは，

(0..2).map{ 3 ** _1 }

と書ける。
divisors メソッドの定義内では，素因数（prime factor）を p，指数（exponent）を e として，

(0..e).map{ p ** _1 }

と書いている。
（指数が大きい場合にはちょっと効率が悪いかもしれないが，簡素に書いてみた）

あとは直積をとって，その各要素について総積を計算すればよい。
63 の場合，

Array.product([1, 3, 9], [1, 7])
# => [[1, 1], [1, 7], [3, 1], [3, 7], [9, 1], [9, 7]]

という直積を得て，その各要素について，総積（全部掛け合わせたもの）を計算する。

総積は

inject(1, :*)

で得られる。
あとで述べるが，レシーバーが空配列の場合があるので 1 は省けない。
（[].inject(1, :*) は 1 を返すが，[].inject(:*) は nil を返す）

素因数が一つしかない場合

素因数が一つしかない数，たとえば 8（＝2³）の場合を検討しよう。
8.prime_division は [[2, 3]] を返す。
素因数 2 の冪べきの配列は [1, 2, 4, 8] となる。
冪の配列はこれ一つだけなので，直積を取るときも，この一つの配列の直積を取ることになる。
Array.product の仕様を検討したとき，引数が一つの場合を考慮したのは，こういうことだったのだ。

Array.product([1, 2, 4, 8])
# => [[1], [2], [4], [8]]

であるから，

p Array.product([1, 2, 4, 8]).map{ _1.inject(1, :*) }
# => [1, 2, 4, 8]

と期待どおりに動作する。

素因数が一つもない場合

さて，素因数分解は，「素因数が一つもない」という事態が起こりうる。
その唯一のケースは 1 の素因数分解だ。
これは $2^3\cdot 7$ みたいな形の式では書けないが，「素因数分解できない」のではなく，「素因数分解したら素因数がありませんでした」ということなのである¹。

したがって，当然こうなる：

require "prime"
1.prime_division # => []

われらが Integer#divisors が，1 の場合にも正しい結果

1.divisors # => [1]

を返すのは，頭をひねって検討した Array.product の仕様

Array.product() # => [[]]

が妥当だったことを意味している。

テスト

こういうメソッドを定義したときは，テストが必須だ。

Array.product を定義したファイルが array_product.rb であるとして，以下のようにテストを記述する。

require "minitest/autorun"
require_relative "array_product"

class ArrayProductTest < Minitest::Test
  using ArrayProduct

  def test_2arrays
    assert_equal [[1, 3], [2, 3]], Array.product([1, 2], [3])
    assert_equal [[1, 3], [1, 4], [2, 3], [2, 4]], Array.product([1, 2], [3, 4])
  end

  def test_3arrays
    assert_equal [[1, 3, 4], [1, 3, 5], [2, 3, 4], [2, 3, 5]],
      Array.product([1, 2], [3], [4, 5])
  end

  def test_1array
    assert_equal [[1], [2], [3]], Array.product([1, 2, 3])
  end

  def test_no_arrays
    assert_equal [[]], Array.product
  end

  def test_2arrays_with_block
    result = []
    assert_nil Array.product([1, 2], [3, 4]){ result << _1 }
    assert_equal [[1, 3], [1, 4], [2, 3], [2, 4]], result
  end

  def test_1array_with_block
    result = []
    Array.product([1, 2, 3]){ result << _1 }
    assert_equal [[1], [2], [3]], result
  end

  def test_no_arrays_with_block
    result = []
    Array.product{ result << _1 }
    assert_equal [[]], result
  end
end

1. 学参サイトなどでは「1 は素因数分解できない」と書いてあるものが散見される。これは $2^3\cdot 7$ みたいな形で書けないからだろうが，素因数分解を $\{(2, 3), (7, 1)\}$ みたいな形式で書くことにすれば 1 は空集合 $\{\}$ で表せる。 ↩