TSabc 発言

こんばんは。

kusunoki@...-inet.or.jp writes:

> 組み合わせ、ダブりがなく、全てを探すというのは良くある問題とお
> もいますが、どのようなスクリプトをかかれるのか？

順列生成関数を作ってみますた...アルゴリズム辞典パクって(;^^ゞ
-----
# 配列S[]を順列生成順に入れ換える
function setSeq(s,n,  tmp,j){
  if(n>1){
    for(j=n; j>=1; --j){
      swapArray(s, n, j);
      setSeq(s, n-1);
      swapArray(s, n, j);
    }
  }else{
    # ここで何らかの処理 (例、生成順に文字列を表示する)
    printSeq(s);
  }
}
function swapArray(s,x,y,  t){ t=s[x]; s[x]=s[y]; s[y]=t; }

# 生成順に文字列を表示する
function printSeq(s,  str, j){
  for(j=1; j<=MAX; ++j)
    str = str s[j];
  print str;
}


BEGIN {
  # 配列s[]に、使う文字を指定する。
  MAX = split("a . a h v i y . r", s);
  setSeq(s, MAX);
}
-----

この順列生成アルゴリズムを解説すると、例えば 1,2,3,4 といった4個の順列は、
 1,2,3 と 4
 1,2,4 と 3
 1,3,4 と 2
 2,3,4 と 1
というように 4〜1 を末尾にした 3個の順列の問題に分解できます。
さらに3個の順列についても同じことの繰り返しで求めることができます。

ここで、末尾に4〜1を持ってくるのは、単純に列中の第4項と第3項〜第1項
までを交換する事で処理できます。
具体的には、元の列 1,2,3,4 において、
・4と4を交換して出来る 1,2,3 と 4 のうちの、1,2,3 についての問題を解く
・4と3を交換して出来る 1,2,4 と 3 のうちの、1,2,4 についての問題を解く
・4と2を交換して出来る 1,4,3 と 2 のうちの、1,4,3 についての問題を解く
・4と1を交換して出来る 4,2,3 と 1 のうちの、4,2,3 についての問題を解く
となって、これは再帰呼び出しで表現できます。
再帰呼び出しの前に第4項と第3項〜第1項の交換を行い、再帰呼び出しの後で
元に戻す処理を行います。

なお、このアルゴリズムでは辞書順には生成されません。
(例えば 4,3,2,1 が最後ではなく途中で出力されます)


...そもそも今回の問題で、順列組み合わせを調べるのが良い方法なのかどうかは
置いておくとして(^^;)過去ログで例えば"言語の比較の参考4(電車の切符で昔
やりました)"なんかを探すと、色んな言語での順列生成方法が見つかりますよ。