全ての組み合わせ in Ruby DouKaku?

2個以上のリストlist1, list2, list3...が与えられたときに、その複数個のリストの中の要素を一つずつとりだして組にする方法の全通りのリストを返すコードを書いてください。

Pythonで表現すると下のようになります。

>>> c = CrossProduct([1,2,3,4], "abc")
>>> list(c.all())
[[1, 'a'], [1, 'b'], [1, 'c'], [2, 'a'],
 [2, 'b'], [2, 'c'], [3, 'a'], [3, 'b'],
 [3, 'c'], [4, 'a'], [4, 'b'], [4, 'c']]

>>> c = CrossProduct([0, 1], "ab", ["Foo", "Bar"])
>>> list(c.all())
[[0, 'a', 'Foo'], [0, 'a', 'Bar'], [0, 'b', 'Foo'], [0, 'b', 'Bar']
 [1, 'a', 'Foo'], [1, 'a', 'Bar'], [1, 'b', 'Foo'], [1, 'b', 'Bar']]

順番はこの通りでなくても構いません。返すものはリストと書きましたが、なんらかの「一度に全部をメモリ上に作成しないリスト状のモノ」がある言語ではそちらを使う方がおすすめです。数値や文字列を一つのリストに混在させるのがやっかいな言語では整数のリストに限定しても構いません。

このお題はZIGOROuさんとのやりとりにヒントを得て作りました。 (しまった、先にブログで公開されてしまった→Yet Another Hackadelic - 直積の導出と考えうる全ての値を網羅したハッシュの生成)

追記：サンプル出力が間違っていたのでoceanさんの解答を使って出力し直しました。

配列でお茶を濁すと…

def cross_product(*arrays)
  if arrays.length == 1
    arrays.first.map{|x| [x]}
  else
    cross_product(*arrays[1..-1]).inject([]) {|result, x|
      result.concat arrays.first.map{|a| [a, *x] }
    }
  end
end

cross_product [1,2,3,4], %w[a b c]  # => [[1, "a"], [2, "a"], [3, "a"], [4, "a"], [1, "b"], [2, "b"], [3, "b"], [4, "b"], [1, "c"], [2, "c"], [3, "c"], [4, "c"]]
cross_product [0,1], %w[a b], ["Foo", "Bar"] # => [[0, "a", "Foo"], [1, "a", "Foo"], [0, "b", "Foo"], [1, "b", "Foo"], [0, "a", "Bar"], [1, "a", "Bar"], [0, "b", "Bar"], [1, "b", "Bar"]]

文字列を1文字ずつ無理矢理取り出すにはこんな細工をする。

class Array
  alias :_by_element :to_a
end

class String
  def _by_element
    split(//)
  end
end

def cross_product(*sequences)
  if sequences.length == 1
    sequences.first._by_element.map{|x| [x]}
  else
    cross_product(*sequences[1..-1]).inject([]) {|result, x|
      result.concat sequences.first._by_element.map{|a| [a, *x] }
    }
  end
end

cross_product [1,2,3,4], %w[a b c]  # => [[1, "a"], [2, "a"], [3, "a"], [4, "a"], [1, "b"], [2, "b"], [3, "b"], [4, "b"], [1, "c"], [2, "c"], [3, "c"], [4, "c"]]
cross_product [0,1], "ab", ["Foo", "Bar"] # => [[0, "a", "Foo"], [1, "a", "Foo"], [0, "b", "Foo"], [1, "b", "Foo"], [0, "a", "Bar"], [1, "a", "Bar"], [0, "b", "Bar"], [1, "b", "Bar"]]

再帰的に

def cross_product(*args)
	raise ArgumentError if args.size <= 1

	if args.size == 2
		r = []
		args.first.each{ |v|
			args.last.each{ |vv|
				r << [v, vv]
			}
		}
		return r
	end

	cross_product(args.first, cross_product(*args[1..-1])).map{ |rr|
		[rr.first] + rr.last
	}
end

def cross_product_wrap(*args)
	args.map!{ |arg|
		case 
		when arg.kind_of?(String)
			arg.scan(/./)
		when arg.kind_of?(Array)
			arg
		else
			[arg]
		end
	} 
	cross_product(*args)
end

関数型でなくArrayクラスのクラスメソッドとして作成してみた (主体がはっきりしてないと落ち着かないので) . 渡したリストが配列でなくても動作するようにしたけど副作用がありそうな気がする.

class Array
  def self.cross(*argv)
    argv.map!{|x| x.class.to_s == new.class.to_s ? x : x.to_s.split(//)}
    ary = argv.shift.map{|x| [x]}
    argv.each{|x|
      ary = new(ary.size*x.size){|j|
        [x[j.modulo(x.size)], *ary[j.div(x.size)]]
      }
    }
    ary.map{|x| x.reverse}
  end
end
p Array.cross([0, 1], "ab", ["Foo", "Bar"])

DouKaku?

全ての組み合わせ

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq