-PR-
解決済み

組合せ 

  • 困ってます
  • 質問No.69736
  • 閲覧数280
  • ありがとう数11
  • 気になる数0
  • 回答数8
  • コメント数0

1から i番目まで、数字がランダムに並んでいます。(マイナス数値からプラス数値まで)。
これらの数値の組合せで、組合せの合計値が、ある目標値になる組合せのすべてを発見して、その組合せを1からiの番号で表示したいのです。
目標値は一個だけ定めます。
どのような論理を組めば可能でしょうか。(この論理をエクセルソフトに組み込み計算します)。
通報する
  • 回答数8
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル11

ベストアンサー率 77% (214/277)

またまた「tintagel」です。

まことに申し訳ありません。回答No.1は無視して下さい。
質問を間違えていました。

エクセルに組み込むとの前提で回答します。

数学ですと理論構築が必要となりますが、コンピュータを使用するなら結果を求めることが優先されるのではないでしょうか?

そこで、問題はiの大きさと繰り返しロジックをなんとかすればできるのではないでしょうか?

そこで、数字はテーブルに入っていて、その要素を選択して合計の結果を検査することを考えてみました。

 テーブルの要素を3つとし、選択したことを1で表しますと
  (0,0,0)、(0,0,1)、(0,1,0)、(0,1,1)、(1,0,0)、(1,0,1)、(1,1,0)、(1,1,1)の8通りです。

  これって2進数ではありませんか?
  組み合わせは2の3乗の8です。

  これでiの大きさから組み合わせは2のi乗です。これが繰り返し回数です。
  (だだし、初期値を0なら、最終値は2のi乗より1小さくします。)

  後は、組み合わせは選択されているテーブルの値を加え、目標値と一致すれば出力します。

  そのテーブルの要素が選択されているかどうかは添え字を10進数→2進数変換してビット検査すれば良いでしょう。

  これで「組み合わせパターン」と「ビット検査」の繰り返しの2回で実現できるのではないでしょうか?

  後は変数のクリア(テーブル合計値の変数は注意)、全然選択なしを含むかで初期値が違います。それにテーブルの開始も注意して下さい。(0か1にするかによってコーディングは違います、気を付けて下さい。)

  細かくは検証はしていませんがこの線に沿ってみてはいかがでしょうか?
関連するQ&A
-PR-
-PR-

その他の回答 (全7件)

  • 回答No.1
レベル11

ベストアンサー率 77% (214/277)

理論構築を行うためにモデルで考えると、 i=2のときで考えてみましょう。  目標値を5とします。   1つの数字を3とするともう1つは2になります。   1つの数字が-1ならもう1つは6になります。   すなわち2数の和が5になる組み合わせですから    2数が正なら(1,4)、(2,3)です。    1つの数が0なら(0,5)です。    1つの数が負なら(-1,6) ...続きを読む
理論構築を行うためにモデルで考えると、

i=2のときで考えてみましょう。

 目標値を5とします。

  1つの数字を3とするともう1つは2になります。
  1つの数字が-1ならもう1つは6になります。

  すなわち2数の和が5になる組み合わせですから

   2数が正なら(1,4)、(2,3)です。
   1つの数が0なら(0,5)です。
   1つの数が負なら(-1,6)、(-2,7)、・・・となります。(無限に存在します。)
   2つの数が負はありません。(和が5のときです。間違えないでくださいね。)

 理論を成立させるには何か、制限を加える必要があります。

  *例えば
   数字を正の数だけに限定する。
   数字の絶対値を決める。(-99から+99の範囲にするとか)

  しかし、エクセルで作成されるとのことですから、数に限度があります。ヘルプで確認できると思います。

  遅くてもいいなら無理やり解く方法もあります。

   目標値を5
   数字は3つで範囲を-10から+10とします。

    数字の重複ありのとき
     繰り返しは入れ子にしていきます。
      1つ目の数字は-10から+10まで
      2つ目の数字は1つ目の数字と同じ数から+10まで
      3つ目の数字は2つ目の数字と同じ数から+10まで
     ロジックの構文は
      FOR I=-10,10,1  10から10まで1増加のつもり
       FOR J=I,10,1  Iから10まで1増加のつもり
        FOR K=J,10,1 Jから10まで1増加のつもり
          IF I+J+K = 5 THEN
            出力モジュール
          ENDIF
        NEXT K
       NEXT J
      NEXT I
    こんな感じで(細かいとこは違うかなぁ?)
    繰り返しがiの数に影響されるため
    iが入力だとこの方法は辛いですけど・・・

    数字に重複がないとき
     繰り返しは入れ子にしていきます。
      1つ目の数字は-10から+8まで
      2つ目の数字は1つ目の数字より1大きい数から+9まで
      3つ目の数字は2つ目の数字より1大きい数から+10まで
     3つの数字の和が5になるものを列挙します。

     構文はは省略しました。

参考になりますでしょうか?


  • 回答No.6
レベル8

ベストアンサー率 33% (10/30)

計算量を削る方法を考えてみました。 まずデータを最大公約数でわる。目標値もその公約数で割る。 データ:(-200,5月)(100,2月)(122,3月)(200,1月)(200,7月)(300、6月),(550、4月) 目標値:850 が データ:(-100、5月),(50、2月),(61、3月),(100,1月)(100,7月)(150,6月)(275、4月) 目標値:425 ...続きを読む
計算量を削る方法を考えてみました。

まずデータを最大公約数でわる。目標値もその公約数で割る。

データ:(-200,5月)(100,2月)(122,3月)(200,1月)(200,7月)(300、6月),(550、4月)
目標値:850



データ:(-100、5月),(50、2月),(61、3月),(100,1月)(100,7月)(150,6月)(275、4月)
目標値:425
になります。

2、データを偶数のグループと奇数のグループに分ける。
偶数グループ:(-100,5月)(50,2月)(100,1月)(100,7月)(150,6月)
奇数グループ:(61、3月)(275、4月)
目標値:425

ここで目標値が奇数なので偶数グループからは偶数個、奇数グループからは奇数個
選ぶことが分かります。
この時点で調べるべき組合せが
奇数グループの選び方=2通り
偶数グループの選び方=15通り
で合計30通りにまで減っています。

ここで奇数グループの選び方の方が少ないことに注目して奇数グループの選び方を
シラミ潰しに調べます。
(61,3月)を選んだときと(275,4月)を選んだときの場合分けを行います。

(61,3月)を選んだときは新しい目標値は425-61=364、また残り
のデータは偶数グループの中から選ぶので

データ:(-100,5月)(50,2月)(100,1月)(100,7月)(150,6月)
目標値:364

と言う問題に帰着できます。ここでデータの最大公約数は50、しかし
目標値は50で割り切れないので解無しとなります。

(225,4月)を選んだときは新しい目標値は425ー275=150、残りのデータは
偶数グループの方から選ぶので

データ:(-100,5月)(50,2月)(100,1月)(100,7月)(150,6月)
目標値:150

と言う問題に帰着できます。データの最大公約数50で割ると

データ:(ー2、5月)(1、2月)(2、1月)(2、7月)(3、6月)
目標値:3

となります。偶数グループ、奇数グループに分けると

偶数グループ:(ー2、5月)(2、1月)(2、7月)
奇数グループ:(1、2月)(3、6月)
目標値:3

となります。目標値が奇数なので、偶数グループからは偶数個、奇数グループからは奇数個
データを選ぶことになります。

偶数グループの選び方=3通り
奇数グループの選び方=2通り

となりのこり6通り調べれば良いことになります。
奇数グループの選び方の方が少ないのでこちらをシラミ潰しに調べると、

(1,2月)を選んだとき
データ:(ー2、5月)(2、1月)(2、7月)
目標値:2
となります。ここらではしょりますが答えは
{(2,1月)}
{(2,7月)}
{(-2,5月)(2,1月)(2,7月)}
の3つです。
よって全体の答えとして
{1月,2月,4月}
{7月,2月,4月}
{5月,1月,7月,2月,4月}
が得られます。

(3、6月)を選んだとき
データ:(ー2、5月)(2、1月)(2、7月)
目標値:0
この問題の答えは{(ー2、5月)(2,1月)}{(-2,5月)(2,7月)}{選ばない}となります。
よって答え全体の答えとして
{5月,2月、6月、4月}
{5月,7月、6月、4月}
{6月、4月}


以上より
{1月,2月,4月}
{7月,2月,4月}
{1月,2月,4月,5月,7月}
{5月,2月、6月、4月}
{5月,7月、6月、4月}
{6月、4月}
という答えが得られます。
どうでしょうか、データによってはかなりの計算時間が削れるはずです。
  • 回答No.5
レベル11

ベストアンサー率 77% (214/277)

またまたまた「tintagel」です。 組み合わせ回数が問題になっているようですね。 打ち切り方法と新しい方法を考えました。 紹介してある方法のロジック改良です。   ランダムテーブルを昇順に並ます。   組み合わせの合計値が目標値を超過すれば打ち切りです。   (以上ではありません。ランダム数字に0がある可能性を考慮して下さい。)   (降順なら未満で打ち切りです。) 新た ...続きを読む
またまたまた「tintagel」です。

組み合わせ回数が問題になっているようですね。
打ち切り方法と新しい方法を考えました。

紹介してある方法のロジック改良です。
  ランダムテーブルを昇順に並ます。
  組み合わせの合計値が目標値を超過すれば打ち切りです。
  (以上ではありません。ランダム数字に0がある可能性を考慮して下さい。)
  (降順なら未満で打ち切りです。)

新たに考えた方法です。
  ランダムテーブルを3つに分解します。
  負のテーブル、0のテーブル、正のテーブルを絶対値の昇順で並べます。
  目標値が負の場合、負のテーブルから検査します。
  組み合わせの合計値の絶対値が目標値の絶対値を超過した場合、正のテーブルの方に切り替えます。
  組み合わせの合計値が目標値を超過した場合、負のテーブルに切り替えます。
  後は同様に処理を繰り返します。
  (目標値との比較結果を超過で合わせるため、負の場合絶対値にしています。ロジックを一本化できるでしょう。)

  目標値が正の場合も同様に処理をします。

  0の扱いは正解があれば正解に0テーブルの組み合わせです。
  (ランダムの中には0は1つとは限りません。)

  目標値が0の場合は正、負のどちらかのテーブルで始めれば良いでしょう。
  (ただし、0テーブルの組み合わせを忘れずにして下さい。)

ランダムの数字を順番を変更した場合は並べる前と後の対応テーブルを作成し、出力の時は前の番号で出力して下さい。

後、数字が小数の場合など、エクセルの限界値にも気を付けて下さい。
(丸めがあると結果が正しく出力されません。)
お礼コメント
noname#6140

tintagelさん、nagataさん、ARCさん、皆様のご教示 ありがとうございます。
当方の質問内容に不備があり、皆様にご迷惑おかけして恐縮です。
今回の質問趣旨は、下記のとおりです。
当方の売掛債権に対する支払いが債務者からあります。
この支払い額の割り当て月を検索、特定して、
その債務者の支払い該当月分を売掛帳から消去する目的です。
各債務者が支払いするごとに、その債務者の過去、数ヶ月の月ごとの売掛債権のどれを消去するべきかを特定する目的です。各債務者は1ヶ月だけ、あるいは数か月分まとめて支払います。月をまたいでランダムに支払います。
支払い金額、すなわち目標値は1000円から5億円、小数、ゼロ、マイナスはありません。未払い残月数、すなわち"i"は1から最大で20程度で債務者ごとにバラケます。
実際の処理は、支払いの都度、その債務者の未払い残月数(i)を与えて、未払い月毎の金額をすべて組合せ、合計して書き出し、その中から、支払額に一致する組合せのものを選択します。
例:債務者Aさんが850万円を支払いした。
Aさんの残高:
2000年1月--200万
2000年2月--100万
2000年3月--122万
2000年4月--550万
2000年5月--マイナス200万(返品があった)
2000年6月--300万
2000年7月--200万
答え:A-(1,2,4月) B-(1,2,4,5,7月) C-(4,6月)

当初の質問で条件の記入不足があり、お詫び申し上げます。
投稿日時 - 2001-05-04 03:41:21
  • 回答No.7
レベル8

ベストアンサー率 33% (10/30)

すいません、うそつきました。 偶数グループの選び方は偶数個限定ではありません。偶数個でも奇数個でもOKです。 よって計算量は偶数グループの方では削れません。しかし奇数グループの選び方 は目標値によって偶数個か奇数個か限定できますので一応計算量は削れます。 失礼しました。では。
すいません、うそつきました。
偶数グループの選び方は偶数個限定ではありません。偶数個でも奇数個でもOKです。
よって計算量は偶数グループの方では削れません。しかし奇数グループの選び方
は目標値によって偶数個か奇数個か限定できますので一応計算量は削れます。
失礼しました。では。
  • 回答No.3
レベル8

ベストアンサー率 33% (10/30)

ちなみにiの大きさはどれくらいでしょうか。 20程度ならば全ての組合せに対して合計値を計算し、条件に合うものを 表示させて行けばOKです。tintagelさんのおっしゃる通り。 しかしiが40程度になるとこの方法ではかなり 計算時間的にきついので何らかの工夫をする必要があります。 例えばランダムに並んでいると言う数字はどの様な特徴があるのかに注目します。 -100から100の範囲に収まって ...続きを読む
ちなみにiの大きさはどれくらいでしょうか。
20程度ならば全ての組合せに対して合計値を計算し、条件に合うものを
表示させて行けばOKです。tintagelさんのおっしゃる通り。

しかしiが40程度になるとこの方法ではかなり
計算時間的にきついので何らかの工夫をする必要があります。
例えばランダムに並んでいると言う数字はどの様な特徴があるのかに注目します。
-100から100の範囲に収まっているとか、もっと広い範囲にばらついて
いるとか、負の数より正の数が圧倒的に多いとか。
そういうところから計算量を削れるかもしれません。

また出力のサイズにも注意しなければいけないでしょう。
例えば極端な話、i=40でランダムに並んでいる数字はすべて1、合計値=20
になる組合せは?と言う問題を解こうとしたとき出力するべき組合せの数は
およそ10^11個になります。表示させるだけでも何日も掛かってしまいそうな
数字です。出力サイズがめちゃくちゃに大きくなりそうなら出力の形式にも
なにか工夫が必要でしょう。

と、いうことで計算時間を気にする必要があるなら

1、データの数はどれくらいか
2、データの値のばらつき具合はどんな感じか
3、出力サイズはどれくらいになりそうか

というのを教えてもらえると、こちらも考えやすいです。
  • 回答No.4
レベル13

ベストアンサー率 46% (643/1383)

手元のアルゴリズム辞典では、2進数を利用して解くやり方が紹介されています。 例えば、データの個数が8個だとすると、8ビットの2進数を用意してやって、00000001, 00000010, 00000011, …, 11111111 と、順に1ずつ足していきます。そしてそれぞれの過程で1の位置と対応するデータを取り出せば、8個のデータの全ての組み合わせが判定できるわけです。 面白そうなのでちゃち ...続きを読む
手元のアルゴリズム辞典では、2進数を利用して解くやり方が紹介されています。

例えば、データの個数が8個だとすると、8ビットの2進数を用意してやって、00000001, 00000010, 00000011, …, 11111111 と、順に1ずつ足していきます。そしてそれぞれの過程で1の位置と対応するデータを取り出せば、8個のデータの全ての組み合わせが判定できるわけです。

面白そうなのでちゃちゃっと作ってみました。長整数型を使って最大31個の数値の組み合わせを得ます。
ちなみにデータ数を31と指定する(N=30)と、40億以上の組み合わせを走査しなくてはならなくなる為、開始したら最後、待てど暮らせど終了しない事態に陥ると思います。

Sub test()
  Const MOKUHYO As Long = 10 '目標値
  Const N As Long = 13 '(データの個数 - 1)を設定する。1~30を設定。
  Dim p() As Long 'データ
  
  Dim i As Long, j As Long
  Dim Tag As Long
  Dim Goukei As Long
  Dim Table(30) As Long ' 1,2,4,8,16…を格納する
  Dim Counter As Long
  
  
'データを乱数で初期化する
  ReDim p(N) As Long
  For i = 0 To N
    p(i) = Int(Rnd() * 11) - 5 '-5~5の乱数をセット
  Next i

'処理開始
  'テーブルの初期化
  For i = 0 To 30
    Table(i) = 2 ^ i
  Next i
  '主処理
  For i = 1 To 2 ^ N
    Goukei = 0
    For j = 0 To N
      If (i And Table(j)) <> 0 Then Goukei = Goukei + p(j)
    Next j
    '合計の判定
    If Goukei = MOKUHYO Then
      Counter = Counter + 1
      For j = 0 To N
        If (i And Table(j)) <> 0 Then Debug.Print p(j) & " ";
      Next j
      Debug.Print
    End If
  Next
  
'けっかほおこく
  Debug.Print
  For i = 0 To N - 1
    Debug.Print p(i) & ", ";
  Next i
  Debug.Print p(i)
  Debug.Print Counter & "個の組み合わせがあります。"
End Sub
  • 回答No.8
レベル14

ベストアンサー率 57% (1014/1775)

数の列 list[i] (i=1,2,.....,L)が与えられている。この中から任意の個数の要素を選んで、その総和が目標値Tになるようにしたい。そのような選び方を全部示せ。 結局の所総当たりで調べるしかなさそう(NP問題)ですが、無駄な探索を省くと少しは速くなります。そのためには ・値をsortしておく ことによって、見込みのない探索を早く打ち切ることができます。それから、 ・値が0である要 ...続きを読む
数の列 list[i] (i=1,2,.....,L)が与えられている。この中から任意の個数の要素を選んで、その総和が目標値Tになるようにしたい。そのような選び方を全部示せ。

結局の所総当たりで調べるしかなさそう(NP問題)ですが、無駄な探索を省くと少しは速くなります。そのためには
・値をsortしておく
ことによって、見込みのない探索を早く打ち切ることができます。それから、
・値が0である要素は、加えても加えなくても合計値は変わらない。
・同じ値が複数個入っている場合も、その取捨選択の組み合わせを変えたところで合計値は変わらない。しかし幾つ選択できるかは、個数による。
これらを考慮しないと無駄な探索をやってしまうことになります。なお
・正の値と負の値は区別して扱う必要がある。これが問題を難しくしている。(もしlistに正の値しか現れないというのだと、だいぶすっきりしたものになる。)
というのも重要な点です。
これらを盛り込んでみると、以下の通り。

あらかじめlistを値が小さい順にsortする。ただし、値が0の要素は除外する。その結果をV[j](j=1,...,N)とする。(N≦L。L-Nはlistに含まれていた0の個数である。)すると、以下の性質が成り立つ。
∀j∀k(1≦j<k≦N → V[j]≦V[k])
∀j(1≦j≦N →V[j] ≠0)
目標値Tを与えたとき、解は(もしあれば)自然数の集合Xで表され、
T= Σ{x∈X} V[x] (Σ{x∈X}V[x]とは、Xに含まれる全ての要素xについてV[x]の総和を取ることを示す。)
を満たす。
この準備をした上で、Solve(T)を走らせればOK。

Solve(T):
T:目標値
if T=0 then
 makeAllAnswer(φ) (空集合φは一つの解である。この解に随伴する全ての答を生成する。詳細は後述。)
else
 wp := Σ{j=1~N} max(0,V[j])   (max(a,b)はa,bの内の大きい方)
 wn := Σ{j=1~N} min(0,V[j])   (min(a,b)はa,bの内の小さい方)
 if T>wp then (Tが大きすぎて解がない)
  exit
 fi
 if T<wn then (Tが小さすぎて解がない)
  exit
 fi
 search(φ,T,wp,wn,0) (φは空集合。)
fi
end.


search(X,T,wp,wn,maxX):
(数の列Vの中から、既にいくつかの数が合計に入れる物として選択されている。その番号の集合がXである。Tは、元々の目標値からこれらの「すでに選択されている要素」の合計値 Σ{x∈X} V[x] を差し引いた物である。wpはXに幾つか要素を追加して作ることが可能な最大値、wnはXに幾つか要素を追加して作ることが可能な最小値を表す。Xは解ではなく、しかも、Xに(maxXより大きい)要素を幾つか追加すれば解になる可能性がある。searchは実際にXに要素を追加して、解を探す。)
X: 自然数の集合。Vのうち、すでに選択されている要素の番号を表す
T: 目標値(ただし、すでに選択されている要素の合計は差し引かれている)
wp: Xの最大値より大きい数nについてV[n]のうち、正の値のものの合計
wn: Xの最大値より大きい数nについてV[n]のうち、負の値のものの合計
maxX :集合Xの要素の内の最大のもの(ただしX=φのときはmaxX=0)

(まず、あと1個の要素を加えたら解になるかどうかを調べる。加える要素KはmaxX+1~Nのうちのひとつであるから、2分法を使って探索すると速い。解がない場合にはk=0を返すものとする。)
binarySearch(T,maxX+1,N,k)
if k>0 then (X∪{k}は解である。)
 makeAllAnswer(X∪{k})(解X∪{k}に随伴する全ての解を生成する。)
 more := false (解が見つかったので、同じXについてこれ以上探しても見込みはない)
else
 oldVk:=V[maxX+1]-1(右辺はV[maxX+1]と等しくない値なら何でも良い。)
 k:=maxX
 more:= true (ループを制御するフラッグ)
 repeat
  repeat
   k:=k+1(Xに追加する要素をkとする。kを増やしながら探す)
  until (k>N) or (V(k)≠oldVk) (V[k]が前回のループと同じであるkは調べても無駄なので飛ばす)
  more := (k≦N)
  if more then (Xについてまだ調べ尽くしていない。)
   possible:= true (Xに要素を追加して調べるかどうかを制御するフラッグ)
   if V[k]<0 then
    if T>wp+V[k] then(X∪{k}に対してTは大きすぎるが、kを増やせばまだ可能性はある。)
     possible = false
    elseif T<wn then(X∪{k}に対してTは小さすぎる。つまり、X∪{k}に追加できる全ての負の値を合わせてもまだTの方が小さい。これ以上探しても見込みはない)
     possible = false
     more := false
    fi
    wn:=wn-V[k]
   else (V[k]>0の時)
    if T>wp then(X∪{k}に対してTは大きすぎる。つまり、X∪{k}に追加できる全ての正の値を合わせてもまだTの方が大きい。これ以上探しても見込みはない)
     possible := false
     more := false
    elseif T<V[k] then(X∪{k}に対してTは小さすぎる。X∪{k}だけでTを越えてしまった。このうえkを増やせばV[k]も増えるから、これ以上探しても見込みはない)
     possible := false
     more := false
    fi
    wp:=wp-V[k]
   fi
   if possible then(X∪{k}は解ではないが、これに対してTは大き過ぎも小さ過ぎもしない。要素を追加して探してみる必要あり。)
    search(X∪{k},T-V[k],wp,wn,k) (kを、「既に選択されている要素」に加えて調べる。)
   fi
  fi
 until not more (Xについて調べ尽くすまで繰り返す。)
fi
end.

binarySearch(L,U,T,k):
(あと1個の要素を追加すれば解があるのかどうかを2分法で調べる。)
if L>U then
 k:=0
 exit
else
 k:= round((L+U)/2)(LとUの真ん中ぐらいの値を作る。)
 if T=V[k] then(解が見つかった)
  exit
 elseif T>V[k] then
  binarySearch(k+1,U,T,j)
  k:=j
  exit
 else (T<V[k])
  binarySearch(L,k-1,T,j)
  k:=j
  exit
 fi
fi
end.


makeAllAnswer(X):
(解Xに随伴する全ての答を作り出す。
 実際に欲しいのは解X(列Vの番号の集合)ではなく、それに対応する答(列listの番号の集合)である。
 もしlistの中に0がなく、しかも同じ値が複数個入っていることもないのであれば、単にXの各要素に対応するlistの要素の番号を書き出せば良いだけのことである。しかしそうなっているとは限らない。
 「解Xに随伴する答」とは、Xに含まれない自然数1≦y≦Nで、Xのどれかの要素xと値が同じであるもの(V[y]=V[x])が存在する場合、これをxと入れ替えた物を別の解として、それに対応する答のことを言う。さらに値が0であるようなlistの要素を何個か加えたものも、解Xに随伴する答である。
 要領よく計算するためには、あらかじめlistから重複を除いた列 ulist[m] (m=0,1,2,....,M.ただしulist[0]=0とする。)を作り、Q[m]={i| list[i]=ulist[m]}, nQ[m]=(Q[m]の要素の数)という表を作っておく。さらに列Vの番号xと列ulistの番号mとの対応表emを作っておく。すなわちulist[em[x]]=V[x]となるようにem[x]を用意しておく。すると、具体的に解Xが得られたとき、)
X:解
for m=1~M
 nP[m]:=0
rof
for each x∈X
 nP[em[x]]:=nP[em[x]]+1
rof
によって、nP[m]は、V[x]=ulist[m]であるようなx(∈X)の個数を表すことになる。勿論0≦nP[m]≦nQ[m]である。
nP[m]=0の場合、Q[m]の要素は解には含まれない。従ってQ[m]について選択の余地はない。
nP[m]=nQ[m]の場合、Q[m]の要素は全部解に含まれ、従ってQ[m]について選択の余地はない。
0<nP[m]<nQ[m]の場合、Q[m]について選択ができ、Q[m]の要素の内からnP[m]個の要素を選ぶ選び方は (nQ[m])! / ((nP[m])!(nQ[m]-nP[m])!)通りある。
0<nP[m]<nQ[m]であるような全てのmについて、それぞれ独立に (nQ[m])! / ((nP[m])!(nQ[m]-nP[m])!)通りの選び方ができ、さらに、nQ[0]個以下の0をこれに加えるやり方は2^(nQ[0])通りある。だから全部で
(2^(nQ[0]))(Π{m=1~M) ((nQ[m])! / ((nP[m])!(nQ[m]-nP[m])!)))通りの「随伴する答」を作ることになる。(Π{m=1~M) f(m)はf(1)×f(2)×...×f(M)を表す。)
どうやってやるかは自明だしめんどくさいので書かない。
end.

以上、テストはやってませんから間違ってたらごめんね。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


新大学生・新社会人のパソコンの悩みを解決!

いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ