組合せ生成プログラム JavaScript

JS

　組合せ生成プログラムをJavaScriptで作ってみました。(^_^;
　順列は同じものを含んでいても計算してくれますが、組合せの場合は駄目みたいです。(^_^;
　それから、ソートは文字列ソートになっているので要注意。つまり、数字の場合、10以上を扱う時要注意。(^_^;
　同じものを含む組合せ生成JavaScriptプログラムについては、こちらを参照して下さい。

●GenComb.html

<html>
<head>
<title>GenComb.html</title>
<script type="text/javascript">
// 順列生成
function next_perm(p, n, r)
{
  var i, j, k, tmp;
  if(r <= 0 || n < r) return(false);
  for(i = r + 1; i <= n-1; i++)
    for(j = i; j >= r + 1 && p[j-1] < p[j]; j--)
      tmp = p[j], p[j] = p[j-1], p[j-1] = tmp;
  for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
  if(!i) return(false);
  for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
  tmp = p[i-1], p[i-1] = p[j], p[j] = tmp;
  for(k = 0; k <= (n-i-1)/2; k++)
    tmp = p[i+k], p[i+k] = p[n-k-1], p[n-k-1] = tmp;
  return(true);
}

// xがaの何番目にあるか調べる関数
function get_pos(a, x)
{
  var i;
  for(var i=0; i< a.length; i++)
    if(a[i]==x) return(i);  // あるときは、0〜a.length-1を返す
  return(-1);               // ないときは、-1を返す 
}

// 組合せ生成
function next_comb(c, n, r)
{
  var i,j,k;
  if(r <= 0 || n < r) return(false);
  var o=new Array(n+1);
  var p=new Array(n+1);
  o=c.slice(0).sort();
  for(i=0; i< n; i++) p[i]='1';
  for(i=0; i< r; i++)
    p[get_pos(o,c[i])]='0';
  var res=next_perm(p, n, n);
  if(!res) n=0;
  for(i=j=0,k=r; i< n; i++)
    if(p[i]=='0') c[j++]=o[i]; else c[k++]=o[i];
  delete o,p;
  return(res);
}
</script>
</head>
<body>
<script type="text/javascript">
var cnt=0
var N=5;
var R=3;
var P=["A","B","C","D","E","F","G","H","I","J"];
var p =new Array(N);
p=P.slice(0,N).sort();

var tm=(new Date()).getTime();  // Timer start
do{
  document.write(++cnt,":",p.slice(0,R),"<br>");
}while(next_comb(p,N,R));

tm=(new Date()).getTime()-tm;  // Timer stop
document.write("Runtime : ",tm/1000.0, "[sec]<br>");
</script>
</body>
</html>

●実行結果

1:A,B,C
2:A,B,D
3:A,B,E
4:A,C,D
5:A,C,E
6:A,D,E
7:B,C,D
8:B,C,E
9:B,D,E
10:C,D,E
Runtime : 0[sec]

※参考URL
よしいずの雑記帳　 再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (2)
よしいずの雑記帳　 再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (3)

●組合せ生成プログラム JavaScript (2) - rscの日記
●組合せ生成プログラム JavaScript (3) - rscの日記

マンガでわかるJavaScript

マンガでわかるJavaScript

JavaScript 第5版

JavaScript 第5版

JavaScript: The Good Parts ―「良いパーツ」によるベストプラクティス

JavaScript: The Good Parts ―「良いパーツ」によるベストプラクティス

パーフェクトJavaScript (PERFECT SERIES 4)

パーフェクトJavaScript (PERFECT SERIES 4)

詳解HTML&CSS&JavaScript辞典 第4版

詳解HTML&CSS&JavaScript辞典 第4版