"N個の異なる要素から構成される集合{0,1,...,N-1}をK個のグループに分割したい"

README.md

http://twitter.com/ken5a/status/338877331106050048 "N個の異なる要素から構成される集合{0,1,...,N-1}をK個のグループに分割したい。 注:グループ内での順序やグループ同士の順序はない(つまり{{0,1}, {2, 3}} == {{3,2}, {1, 0}})" "N=3なら [((0, 1, 2),), ((0,), (1, 2)), ((0, 2), (1,)), ((0, 1), (2,)), ((0,), (1,), (2,))]"

• [[0,2],[1],[3]]という分割結果に対し，0→[0,2],1→[1],2→[3]という添字を付け，元の数字の順に添字を並べた0102を添字列と呼ぶ．
• 再帰的に添字列を作る．
• 先頭を0とし，振れる数字を0から(今まで振った数+1)までとすれば，結果の重複は除ける．
  • (例えば添字列0201([[0,2],[3],[1]])は生成されない)
• これは，重複した分割結果[[0,2],[1],[3]]や[[3],[1],[0,2]]などの中で，それぞれの最小の数字が昇順になっている結果だけを生成していることになる．

以下にHaskellとJS実装を添付する． HaskellにてN=12(結果が400万件)の場合でも実行時間13秒となった．

hoge.hs

import Data.List
-- hdを先頭に持つlen桁の列，ただし次にくる数字の最大はmx+1
bunkatsu 1   hd _  = [[hd]]
bunkatsu len hd mx = [hd:xs|next<-[0..mx+1],xs<-bunkatsu (len-1) next (max mx next)]

-- [0,1,2,2,0] を [[0,4],[1],[2,3]] へmap
soeji2group :: [Int]->[[Int]]
soeji2group = map (map fst). groupBy (\a b->snd a==snd b). sortBy (\a b->snd a `compare` snd b). zip[0..]

main=putStrLn$show$map soeji2group $bunkatsu 4 0 0

hoge.js

//Haskellからの直訳なので関数の意味はHaskellのコメントを参照

function bunkatsu(len, hd, mx){
	if(len==1) return [[hd]];
	var ret=[];
	for(var next=0; next<=mx+1; next++){
		bunkatsu(len-1, next, Math.max(mx, next)).forEach(function(xs){
			ret.push([hd].concat(xs));
		});
	}
	return ret;
}

function soeji2group(arr){
	var obj={};
	for(var i=0; i<arr.length; i++){
		var ii=arr[i];
		if(!obj[ii]) obj[ii]=[];
		obj[ii].push(i)
	}
	var ret=[];
	for(var i in obj){
		ret.push(obj[i])
	}
	return ret;
}

console.log(bunkatsu(3,0,0).map(soeji2group));