組合せ

1から　i番目まで、数字がランダムに並んでいます。（マイナス数値からプラス数値まで）。
これらの数値の組合せで、組合せの合計値が、ある目標値になる組合せのすべてを発見して、その組合せを1からiの番号で表示したいのです。
目標値は一個だけ定めます。
どのような論理を組めば可能でしょうか。（この論理をエクセルソフトに組み込み計算します）。

No.2 ベストアンサー 回答者： tintagel 回答日時： 2001/04/30 15:02

またまた「tintagel」です。

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

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

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

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

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

　テーブルの要素を３つとし、選択したことを１で表しますと
　　（０，０，０）、（０，０，１）、（０，１，０）、（０，１，１）、（１，０，０）、（１，０，１）、（１，１，０）、（１，１，１）の８通りです。

　　これって２進数ではありませんか？
　　組み合わせは２の３乗の８です。

　　これでｉの大きさから組み合わせは２のｉ乗です。これが繰り返し回数です。
　　（だだし、初期値を０なら、最終値は２のｉ乗より１小さくします。）

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

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

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

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

　　細かくは検証はしていませんがこの線に沿ってみてはいかがでしょうか？

No.8 回答者： stomachman 回答日時： 2001/05/10 00:33

数の列 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）

（まず、あと１個の要素を加えたら解になるかどうかを調べる。加える要素KはmaxX+1～Nのうちのひとつであるから、２分法を使って探索すると速い。解がない場合には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):
（あと１個の要素を追加すれば解があるのかどうかを２分法で調べる。）
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.

以上、テストはやってませんから間違ってたらごめんね。

No.7 回答者： nagata 回答日時： 2001/05/07 12:13

すいません、うそつきました。

偶数グループの選び方は偶数個限定ではありません。偶数個でも奇数個でもOKです。
よって計算量は偶数グループの方では削れません。しかし奇数グループの選び方
は目標値によって偶数個か奇数個か限定できますので一応計算量は削れます。
失礼しました。では。

No.6 回答者： nagata 回答日時： 2001/05/05 17:22

計算量を削る方法を考えてみました。

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

データ:(-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 回答者： tintagel 回答日時： 2001/05/02 11:19

またまたまた「tintagel」です。

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

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

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

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

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

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

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

後、数字が小数の場合など、エクセルの限界値にも気を付けて下さい。
（丸めがあると結果が正しく出力されません。）

この回答へのお礼

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

No.4 回答者： ARC 回答日時： 2001/04/30 16:46

手元のアルゴリズム辞典では、２進数を利用して解くやり方が紹介されています。

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

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

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.3 回答者： nagata 回答日時： 2001/04/30 15:46

ちなみにiの大きさはどれくらいでしょうか。

20程度ならば全ての組合せに対して合計値を計算し、条件に合うものを
表示させて行けばOKです。tintagelさんのおっしゃる通り。

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

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

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

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

というのを教えてもらえると、こちらも考えやすいです。

No.1 回答者： tintagel 回答日時： 2001/04/30 02:29

理論構築を行うためにモデルで考えると、

i＝２のときで考えてみましょう。

　目標値を５とします。

　　１つの数字を３とするともう１つは２になります。
　　１つの数字が－１ならもう１つは６になります。

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

　　　２数が正なら（１，４）、（２，３）です。
　　　１つの数が０なら（０，５）です。
　　　１つの数が負なら（－１，６）、（－２，７）、・・・となります。（無限に存在します。）
　　　２つの数が負はありません。（和が５のときです。間違えないでくださいね。）

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

　　＊例えば
　　　数字を正の数だけに限定する。
　　　数字の絶対値を決める。（－９９から＋９９の範囲にするとか）

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

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

　　　目標値を５
　　　数字は３つで範囲を－１０から＋１０とします。

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

　　　　数字に重複がないとき
　　　　　繰り返しは入れ子にしていきます。
　　　　　　１つ目の数字は－１０から＋８まで
　　　　　　２つ目の数字は１つ目の数字より１大きい数から＋９まで
　　　　　　３つ目の数字は２つ目の数字より１大きい数から＋１０まで
　　　　　３つの数字の和が５になるものを列挙します。

　　　　　構文はは省略しました。

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