順列の生成とList内包表記

この間のErlang勉強会で勉強した順列を生成する関数をいろいろと移植してみました。まず元のErlangの実装は以下。与えられたリストから要素を1つ取り出して、残りの要素から再帰的に順列を求めて、それらを結合するアルゴリズムです。ふむ、とてもシンプルです。

perms([]) -> [[]];
perms(L)  -> [[H|T] || H <- L, T <- perms(L--[H])].

まずHaskellの場合。Erlangと似たようなものです。でも型があると何か落ち着きます。ふつう遅延評価なので大きなリストを渡しても難しいこと考えなくてよさそうです。

module Main (main) where

import Data.List ((\\))

perms :: Eq a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ h : t | h <- xs, t <- perms (xs \\ [h]) ]

main :: IO ()
main = print $ perms [1, 2, 3]
-- => [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

次。Rubyの場合。んー、いまいちぐっとこないなー。

#!/usr/bin/env ruby

class Array
  def perms
    return [[]] if empty?
    inject([]) do |rs, h|
      rs + (self - [h]).perms.map {|t| [h] + t }
    end
  end
end

p [1, 2, 3].perms
# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

やっぱりリスト内包表記か？ということで、うじひさくんのアレを使ってみました。おお、いい感じです。実用じゃないけど…

#!/usr/bin/env ruby

# リスト内包表記
# 2007-06-01 Tatsuhiro Ujihisa
#
# List comprehension - Wikipedia, the free encyclopedia
# http://en.wikipedia.org/wiki/List_comprehension
class String
  def lisc
    /^\{\s*(.*?)\s*\|\s*(.*?)\s*\}$/ =~ self
    left, right = $1, $2
    comma = /,\s/ # セパレータとしてのコンマは、スペース必須
    rights = right.split(comma)

    vars, conds =
      rights.map {|right| right.split(/\s*<-\s*/) }.partition {|right| right.size == 2 }.
      map {|right| right.to_a}

    ["_list_comprehension_tmp = []",
     vars.map {|var| "#{var[1]}.each {|#{var[0]}| " }.join,
     "  _list_comprehension_tmp << #{left}" + (conds.empty? ? '' : " if " + conds.join(' && ')) +
     vars.map { "}" }.join,
     "_list_comprehension_tmp"].join "\n"
  end
end

class Array
  def perms
    return [[]] if empty?
    eval '{ [h] + t | h <- self, t <- (self - [h]).perms }'.lisc
  end
end

p [1, 2, 3].perms
# => [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

参照: ライブドアブログ（livedoor Blog）｜ 読みたいブログが見つかる