お知らせ

電子会議

ライブラリ

パレット

Delphi FAQ検索

Delphi FAQ一覧

サンプル蔵





FDelphi FAQ
16番会議室「玉石混淆みんなで作るSample蔵」に寄せられたサンプル

"組み合わせの生成"





 組み合せを生成する関数です。この関数自体は汎用の部品として使える形式
になっていませんが、出力処理を行っている部分を適当に書きかえれば各種の
処理に応用できると思います。再起処理を使った例とビット演算による例を挙
げておきます。アルゴリズムの詳細は引用文献を参照してください。

(*---------------------------------------------------------------
組み合わせの生成(1)
仙波一郎(1999)「組み合わせ数学」コロナ社 pp163-164
プログラム3.5 のリストを元にした。
-----------------------------------------------------------------*)
function ListCombination(n,r:integer):string;
const
  CRLF = #13#10;
var
  T     : array[0..99] of integer;
  Count : integer;
    procedure perm(k : integer);
    var
      i, w :integer;
    begin
      if k = r then begin
        Inc(Count);
        Result := Result + Format('[%3d]',[Count]);
        for i := 1 to k do Result := Result + Format('%2d',[T[i]]);
        if Count mod 5 = 0 then Result := Result + CRLF;
      end else begin
        w := T[k+1];
        for i := k + 1 to n do begin
          T[k+1] := T[i];
          T[i] := w;
          if T[k]<T[k+1] then perm(k+1);
          T[i] := T[k+1];
        end;
        t[k+1] := w;
      end;
    end;
var
  i : integer;
begin
  for i := 1 to n do T[i] := i;
  Count := 0;
  perm(0);
end;

(*---------------------------------------------------------------
組み合わせの生成(2)
奥村晴彦(1991)「Cによる最新アルゴリズム事典」技術評論社 p60-61
に紹介されているビット演算による方法
-----------------------------------------------------------------*)
function ListCombinationBit(n, k : integer) : string;
const
  CRLF = #13#10;
var
  FirstV,LastV,
  V,V2,V3       : Cardinal;

  (* 値 n のビットパターンを len 桁だけ出力 *)
  procedure PrintBit(n : Cardinal; len : integer);
  var
    S : string;
    i : integer;
  begin
    S := '';
    for i := 1 to len do begin
      if Odd(n) then S := '1' + S else S := '0' + S;
      n := n shr 1;
    end;
    Result := Result + S + CRLF;
  end;

begin
  if (n > 32) or (n < k) then Raise Exception.Create('illegal value');
  (* 最初のビットパターン *)
  FirstV := not ((not Cardinal(0)) shl k);
  (* 最後のビットパターン *)
  LastV := (((not Cardinal(0)) shl (32 - n)) shr (32 - k)) shl (n -
k);
  V := FirstV;
  PrintBit(V,n);
  if V < LastV then
    repeat
      (* 次のビットパターンの生成 *)
      V2 := (not(V) + 1) and V;
      V3 := V + V2;
      V  := ((((not(V3) + 1) and V3) div V2) shr 1) - 1 + V3;
      PrintBit(V,n);
    until V = LastV;
end;


使用(出力)例

  Memo1.Lines.Add(ListCombination(5,3));

とすると、

[  1] 1 2 3[  2] 1 2 4[  3] 1 2 5[  4] 1 3 4[  5] 1 3 5
[  6] 1 4 5[  7] 2 3 4[  8] 2 3 5[  9] 2 4 5[ 10] 3 4 5

  Memo1.Lines.Add(ListCombinationBit(5,3));

とすると、

00111
01011
01101
01110
10011
10101
10110
11001
11010
11100

 
- FDELPHI  MES(16):玉石混淆みんなで作るSample蔵【見本蓄積】 00/07/02 -

Original document by ひの            氏 ID:(GFD03044)


ここにあるドキュメントは NIFTY SERVEの Delphi Users' Forum の16番会議室「玉石混淆みんなで作るSample蔵」に投稿されたサンプルです。これらのサンプルはボーランド株式会社がサポートする公式のものではありません。また、必ずしも動作が検証されているものではありません。これらのサンプルを使用したことに起因するいかなる損害も投稿者、およびフォーラムスタッフはその責めを負いません。使用者のリスクの範疇でご使用下さい。

Copyright 1996-2002 Delphi Users' Forum