Cartesian product - 直積集合 - カルテシアン積 - デカルト積 (Kanasansoft Web Lab.)

まず、map。

map(
[1,2,3],
function(x){...}
);

これの発展系として、次のような処理が欲しくなった。

extendMap(
    [1,2,3],
    [4,5,6],
    function(x,y){...}
);

で、実装してみた。
引数の配列の個数はいくつでも構わない。
(実際の処理は最後に記す。)
そうしたら、それはmapとは言わないとnanki氏。
じゃあなんて言うんだろうと考えたがわからない。
順列(permutation)でもないし組合せ(combination)でもない。
そこへ、naoya_t氏の登場。
「cartesian product?」
日本語では「カルテシアン積」もしくは「デカルト積」。
なんかかっこいい。
でも、どこをどう読んだらデカルト積?
「直積集合」とも言うらしい。
Gaucheにはlibraryがあってもの凄く簡単に直積集合を求められる。
そうそう、いつもJavaScriptはそう。
ないものは自分で実装しなくてはならないけど、JSの場合はほとんど自分で作らなくてはならない。
まあ、最近じゃそんな状況も改善されてきてはいるけど。
その後、SchemeやHaskellでの直積集合について色々話があったのをnaoya_t氏がblogにまとめてくれた。
JavaScriptのやつはないので(最後にまとめて)晒す。
実際のコードは、直積集合を求める部分とfunctionに値を渡す部分とをわけた。
てか、なんですか?
Haskellで書くと1行で実装完了って。

Haskellによる直積集合取得

prod = foldr (\as bs -> [ a:b | a <- as, b <- bs ]) [[]]

prod = foldr (\as bs -> [ a:b | a <- as, b <- bs ]) [[]]

rubynekoより引用

直積集合取得(再帰呼出なし)

var getCartesianProduct
	=function(){

		var args=arguments;
		var argslen=args.length;
		var lens=[];
		var cur=[];
		for(var i=0;i<argslen;i++){
			lens.push(args[i].length);
			cur.push(0);
		}

		var flg=true;
		var arys=[];
		while(flg){
			var buf=[];
			for(var i=0;i<cur.length;i++){
				buf.push(args[i][cur[i]]);
			}
			arys.push(buf);
			for(var i=cur.length-1;i>=0;i--){
				cur[i]++;
				if(cur[i]<lens[i]){
					break;
				}else if(i!=0){
					cur[i]=0;
				}else{
					flg=false;
				}
			}
		}

		return arys;

	}

直積集合取得(再帰呼出あり)

var getCartesianProduct
	=function(){
		if(arguments.length==0){return [[]]}
		var args=[];
		for(var i=1;i<arguments.length;i++){
			args.push(arguments[i]);
		}
		var ary=arguments.callee.apply(this,args);
		var rtn=[];
		for(var i=0;i<arguments[0].length;i++){
			for(var j=0;j<ary.length;j++){
				rtn.push([arguments[0][i]].concat(ary[j]));
			}
		}
		return rtn;
	}