★ 全ての組み合わせ得る方法 ★

 288 全ての組み合わせ得る方法  SCD  2001/02/01 (木) 13:14
  291 Re: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 14:58
   296 Re^2: 全ての組み合わせ得る方法  管理者  2001/02/01 (木) 18:04
    297 Re^3: 全ての組み合わせ得る方法  管理者  2001/02/01 (木) 18:09
   292 Re^2: 全ての組み合わせ得る方法  SCD  2001/02/01 (木) 15:37
    295 Re^3: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 18:01
  290 Re: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 14:55
  289 Re: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 14:50


288. 全ての組み合わせ得る方法  SCD  2001/02/01 (木) 13:14
1,2,3,..,n までのr個を取り出す組み合わせはnCrで表わせますが,その組み合わせ全てを得るアルゴリズムを教えて下さい。
例えば 4C2 は 6 となりますが,
(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)
のように,全ての組み合わせを一般的に得る方法を知りたいのですが,よろしくお願いします。

     [このページのトップへ]


291. Re: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 14:58
ところで,行頭の空白が勝手に削除されてしまうここの仕様困り者ですね。プログラムのインデントが消えてしまって悲惨です。何とかなりませんか>管理者様。

     [このページのトップへ]


296. Re^2: 全ての組み合わせ得る方法  管理者  2001/02/01 (木) 18:04
> ところで,行頭の空白が勝手に削除されてしまうここの仕様困り者ですね。プログラムのインデントが消えてしまって悲惨です。何とかなりませんか>管理者様。

NIFTY の掲示板の仕様ですので,どうしようもありません。
<pre> </pre>タグが使えればいいのですが,それもできません。
いくつかの工夫はできますが,一長一短です。

ちなみに,タブや半角空白で整形した表なども同じようにみっともないことになりますのでご注意ください。

いずれも,「全角空白」で整形すれば整形は崩れません。
ただし,プログラムの場合などには全角空白は文法エラーになりますので,受信者(ダウンロード)側で,全角空白→半角空白の変換をやる必要があります。

     [このページのトップへ]


297. Re^3: 全ての組み合わせ得る方法  管理者  2001/02/01 (木) 18:09
つづき

プログラムの場合には,その発言が表示されたページを「Save as...」で「format=source」でダウンロードして,「<br>」を「\n」 に変換してやればいいです。

...って,これをみんなにいっても無理なときもありますね(^_^;)

     [このページのトップへ]


292. Re^2: 全ての組み合わせ得る方法  SCD  2001/02/01 (木) 15:37
Response が早いのでびっくりしました。ありがとうございます。
ところで,私はSASuserでした。C言語には不慣れなもので,これを解読する元気があるかどうかですが,とにかく工夫してみます。何か情報あればまたお願いします。

     [このページのトップへ]


295. Re^3: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 18:01
> ところで,私はSASuserでした。C言語には不慣れなもので,これを解読する元気があるかどうかですが,とにかく工夫してみます。何か情報あればまたお願いします。

参考文献にはCで書かれていますが,アップしたソースはObject Pascal (Delphi)で書いてあります。アルゴリスムについての解説は「組み合わせ数学」の方が詳しいと思います。

     [このページのトップへ]


290. Re: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 14:55
(*奥村晴彦「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;

     [このページのトップへ]


289. Re: 全ての組み合わせ得る方法  ひの  2001/02/01 (木) 14:50
(*---------------------------------------------------------------
組み合わせの生成(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;

     [このページのトップへ]


● 「統計学関連なんでもあり」の過去ログ--- 012 の目次へジャンプ
● 「統計学関連なんでもあり」の目次へジャンプ
● 直前のページへ戻る