JavaScriptでnext_permutation

JavaScript

JavaScriptでSTLのnext_permutationのようなものを実装してみました。

コード

// 昇順から降順へ順列を生成する
var next_permutation = function( d ) {
	var i = d.length - 1;
	while ( i > 0 ) {
		var k = i;
		i--;
		if ( d[i] < d[k] ) {
			var j = d.length-1;
			while ( d[i] >= d[j] ) {
				j--;
			}
			d[i] = d.splice( j, 1, d[i] )[0]; // d[i]とd[j]を入れ替える
			np_reverse( d, k, d.length-1 );
			return true;
		}
	}
	return false; // 次の順列が無いときはfalseを返す
}

// 配列dのa-b間を反転させる
var np_reverse = function( d, a, b ) {
	var sub = d.slice( a, b+1 ).reverse();
	for ( var i = a; i <= b; i++ ) {
		d[i] = sub[i-a];
	}
}

使用例

// テスト用
var test_next_permutation = function( d ) {
	document.write( 'source: ' );
	print_permutation(d);
	// 昇順に並べ替えておく
	d.sort( function(a,b) { return a > b } );
	var cnt = 0;
	// このような書き方で順番にアクセスできる
	do {
		document.write( ++cnt + ": " );
		print_permutation(d);
	} while ( next_permutation(d) );
}

// 順列を出力してみる
var print_permutation = function( d ) {
	var line = "";
	for ( var i = 0; i < d.length; i++ ) {
		line += d[i] + ", ";
	}
	line += "<br>";
	document.write(line);
}

実行結果その1: test_next_permutation( [1,2,3,4] )

普通の整数列

source: 1, 2, 3, 4, 
1: 1, 2, 3, 4, 
2: 1, 2, 4, 3, 
3: 1, 3, 2, 4, 
4: 1, 3, 4, 2, 
5: 1, 4, 2, 3, 
6: 1, 4, 3, 2, 
7: 2, 1, 3, 4, 
8: 2, 1, 4, 3, 
9: 2, 3, 1, 4, 
10: 2, 3, 4, 1, 
11: 2, 4, 1, 3, 
12: 2, 4, 3, 1, 
13: 3, 1, 2, 4, 
14: 3, 1, 4, 2, 
15: 3, 2, 1, 4, 
16: 3, 2, 4, 1, 
17: 3, 4, 1, 2, 
18: 3, 4, 2, 1, 
19: 4, 1, 2, 3, 
20: 4, 1, 3, 2, 
21: 4, 2, 1, 3, 
22: 4, 2, 3, 1, 
23: 4, 3, 1, 2, 
24: 4, 3, 2, 1,

実行結果その2: test_next_permutation( [1,1,3,4] )

同じものを含む場合

source: 1, 1, 3, 4, 
1: 1, 1, 3, 4, 
2: 1, 1, 4, 3, 
3: 1, 3, 1, 4, 
4: 1, 3, 4, 1, 
5: 1, 4, 1, 3, 
6: 1, 4, 3, 1, 
7: 3, 1, 1, 4, 
8: 3, 1, 4, 1, 
9: 3, 4, 1, 1, 
10: 4, 1, 1, 3, 
11: 4, 1, 3, 1, 
12: 4, 3, 1, 1,

実行結果その3: test_next_permutation( ['r','u','b','y'] )

文字もいける

source: r, u, b, y, 
1: b, r, u, y, 
2: b, r, y, u, 
3: b, u, r, y, 
4: b, u, y, r, 
5: b, y, r, u, 
6: b, y, u, r, 
7: r, b, u, y, 
8: r, b, y, u, 
9: r, u, b, y, 
10: r, u, y, b, 
11: r, y, b, u, 
12: r, y, u, b, 
13: u, b, r, y, 
14: u, b, y, r, 
15: u, r, b, y, 
16: u, r, y, b, 
17: u, y, b, r, 
18: u, y, r, b, 
19: y, b, r, u, 
20: y, b, u, r, 
21: y, r, b, u, 
22: y, r, u, b, 
23: y, u, b, r, 
24: y, u, r, b,