tagCANDY CGI VBレスキュー(花ちゃん) の Visual Basic 2010 用 掲示板(VB.NET 掲示板) [ツリー表示へ]   [Home]
一括表示(VB.NET VB2005)
タイトル組み合わせ合計探索
記事No12091
投稿日: 2023/02/07(Tue) 20:51
投稿者たけし
お世話になります。

Windows10
vb.net 2010使用しています。


以下の[設定値] に対して [個数]よりランダムに選んだ合計値が
最も近い組み合わせを獲得したいと思っています。
(同じ値であれば最も良いです)

vb.netで次のサイトのような算出できるものでしょうか?
hhttps://hatenachips.blog.fc2.com/blog-entry-430.html

宜しくお願いいたします。


設定値:88792


個数
-----
5988
2994
1245
3296
19777
1497
14823
13177
37885
5988
6290
6038
22653
28474
29564
26871
23844
4366
4101
14116
7037
17500
24062
23644
17717
25162
9461
19788
29762
25099
28935
1011
4655
22234
9589
30377
10081
2887
24336
3517
16020
6494
16745
24100
28340
24825
13382
6801
19893
28700

[ツリー表示へ]
タイトルRe: 組み合わせ合計探索
記事No12092
投稿日: 2023/02/08(Wed) 12:00
投稿者魔界の仮面弁士
> 以下の[設定値] に対して [個数]よりランダムに選んだ合計値が
> 最も近い組み合わせを獲得したいと思っています。
> (同じ値であれば最も良いです)
やりたいことは分かりましたが、肝心の質問内容が読み取れませんでした。
何が分からないのかを書いてもらわないと、解説のしようがありません。


> vb.netで次のサイトのような算出できるものでしょうか?
その問いは「紙と絵の具があれば、風景画を描けるものでしょうか」と
聞いているようなものであり、質問にはなっていません。

Yes/No という答えを聞きたいわけではありませんよね?


> hhttps://hatenachips.blog.fc2.com/blog-entry-430.html
上記では『値リストがあって、そのすべての組み合わせの中から選ぶ』ものでしたが、
今回のは「個数リストがあって、その個数だけ(何かを)ランダムに選ぶ」…ということですか?


ランダムに、どこから、何個の値の組み合わせを、何回取り出して比較するのでしょうか。
そして個数リストというのは、どの部分に関わってくるのでしょうか。前提条件が曖昧です。


個数リストから 2994 という値がランダムで選ばれたときに、
「2994 個の任意の非重複整数の組み合わせ」の合計値を求める、という意味にも取れます。

あるいは「個数」という言葉は無視して、与えられたリストのなかから、
ランダムかつ重複許可で、値を N 個選び出して合計する…という意味にも取れます。

2 つの値の組み合わせを乱数回抽出して、その合計が最も[設定値]に近かったペアを選ぶ、
という意味にも取れます。


そして何よりも、質問内容は何でしょうか。

値の一覧を管理する方法がわからない?
一覧からランダムに取り出す方法がわからない?
複数値の合計値を求める方法が分からない?
総当たり的に求めることはできているが、効率の良い方法を相談したい?

[ツリー表示へ]
タイトルRe^2: 組み合わせ合計探索
記事No12093
投稿日: 2023/02/08(Wed) 22:31
投稿者たけし
お世話になります。

> > 以下の[設定値] に対して [個数]よりランダムに選んだ合計値が
> > 最も近い組み合わせを獲得したいと思っています。
> > (同じ値であれば最も良いです)
> やりたいことは分かりましたが、肝心の質問内容が読み取れませんでした。
> 何が分からないのかを書いてもらわないと、解説のしようがありません。
どういったプログラム記述をすればよいか
今のところ全く分からない状態です。
ネット検索していると python でもできるようですが・・・
vb.netからの呼び出し方法も分からない状況なので
できればvb.netで値を求めたいと思っています。
(python についても学んで見たいとは思っているのですが)



> > hhttps://hatenachips.blog.fc2.com/blog-entry-430.html
> 上記では『値リストがあって、そのすべての組み合わせの中から選ぶ』ものでしたが、
> 今回のは「個数リストがあって、その個数だけ(何かを)ランダムに選ぶ」…ということですか?
個数は意識していなくて、リストの中から合計した値が、[設定値]と同じか、または[設定値]-20以内の範囲の
値を求めたいと思っています。合計した全ての値と合計値を表示したいです。
[設定値]より大きい場合はNGです。
リストにある最大桁数は4桁になります。最小桁数は2桁です。


> ランダムに、どこから、何個の値の組み合わせを、何回取り出して比較するのでしょうか。
リストにある総データ数は多くても50以内です。


> 個数リストから 2994 という値がランダムで選ばれたときに、
> 「2994 個の任意の非重複整数の組み合わせ」の合計値を求める、という意味にも取れます。
この意味は分かりません。


>
> あるいは「個数」という言葉は無視して、与えられたリストのなかから、
> ランダムかつ重複許可で、値を N 個選び出して合計する…という意味にも取れます。
>
> 2 つの値の組み合わせを乱数回抽出して、その合計が最も[設定値]に近かったペアを選ぶ、
> という意味にも取れます。
ペアとは限りませんし、ひとつだけのデータで完了することもありません。
[設定値]は変化しますが、
[設定値]が1000の時、リストに1000以上は存在しません。

>
>
> そして何よりも、質問内容は何でしょうか。
>
> 値の一覧を管理する方法がわからない?
大丈夫だと思います。
> 一覧からランダムに取り出す方法がわからない?
乱数を使うことはできると思います。
> 複数値の合計値を求める方法が分からない?
loopで素人なプログラム記述はできると思います。
> 総当たり的に求めることはできているが、効率の良い方法を相談したい?
はい。効率の良い方法がわかりません。

以上になりますが、よろしくお願いします。

[ツリー表示へ]
タイトルRe^3: 組み合わせ合計探索
記事No12094
投稿日: 2023/02/09(Thu) 09:53
投稿者魔界の仮面弁士
> > > hhttps://hatenachips.blog.fc2.com/blog-entry-430.html
> > 上記では『値リストがあって、そのすべての組み合わせの中から選ぶ』ものでしたが、
> > 今回のは「個数リストがあって、その個数だけ(何かを)ランダムに選ぶ」…ということですか?
> 個数は意識していなくて、

元の設問は、『[個数]よりランダムに選んだ合計値』と書かれていましたが、
実際には『個数は意識していない』と…?

となると、個数 = 12 が選ばれたからと言って、12 個の値を合計していく…といった課題では無さそうですね。


どうやら、当初の質問の [個数] という言葉のままだと、意味が混乱してしまいそうなので、
参考サイトの VBA 版にあるように、[数値] のリストと読み替えさせてもらいますが、不都合はありますか?


> リストの中から合計した値が、[設定値]と同じか、または[設定値]-20以内の範囲の
> 値を求めたいと思っています。合計した全ての値と合計値を表示したいです。
> [設定値]より大きい場合はNGです。
参考サイトにあるものは、すべての組み合わせの中から、最適解(合計値が一致する組み合わせ)を
選ぶという問題でしたが、今回はそうではなく、「ランダムに選んだ合計値」が前提なのですよね?

ランダムに選ぶという点について、もう少し具体的に説明していただけないでしょうか。


また、日本語で「以内」という言葉を使った場合、文脈によっては
以上/以下の意味なのか、超過/未満の意味なのかがブレることがあるので、
この点ももう少し事前確認しておきたいところ。例えば設定値が 3000 だった場合、
「2980 以上 3000 以下」とするのか「2980 超過 3000 以下」とするのか…。

ひとまず、以上/以下という意味で良いでしょうか? (以内は、基準点を含むことが多いので)


> リストにある最大桁数は4桁になります。
当初の質問とは異なる課題を提示されているように聞こえるのですが…何の冗談でしょう?

>> 設定値:88792
>>
>> 個数
>> -----
>> 19777
>> 14823
>> 13177
>> 37885
>> 22653
>> 28474
>> 29564
>> 26871
>> 23844
>> 14116
>> 17500
>> 24062
>> 23644
>> 17717
>> 25162
>> 19788
>> 29762
>> 25099
>> 28935
>> 22234
>> 30377
>> 10081
>> 24336
>> 16020
>> 16745
>> 24100
>> 28340
>> 24825
>> 13382
>> 19893
>> 28700


> 最小桁数は2桁です。
値はすべて自然数ですか? それとも負の整数なども含まれますか?


> > ランダムに、どこから、何個の値の組み合わせを、何回取り出して比較するのでしょうか。
> リストにある総データ数は多くても50以内です。
> ペアとは限りませんし、ひとつだけのデータで完了することもありません。

・数値リストの総データ数が、最大50個というのは分かりました。
・数値リストの総データ数は、最小何個でしょうか。
 0個 や 1個 ではなさそうなので… 最低 2 個以上? あるいは 10個ぐらい?
・リスト内から値を選んで合計する際に、何個のデータを選べるのでしょうか。
 1 個しか選択しない、というのは駄目らしいですが…
 たとえば最大20個などといった上限あり? あるいは全部選択されることもある?
・リスト内から、同じ項目が複数回、重複して選ばれても良いのでしょうか?
・リスト内の値は「A:同一値が含まれている可能性もある」もしくは
 「B:すべて異なる数値であることが保証される」のいずれでしょうか?


> [設定値]は変化しますが、
> [設定値]が1000の時、リストに1000以上は存在しません。
ここまでの条件を鑑みると、「該当する組み合わせがひとつも存在しない」
というパターンも少なからず発生してしまいそうです。それでも問題ないのでしょうか?
あるいは常に何かしらの組み合わせが存在するような、他の条件があるのでしょうか?


たとえば設定値が 1000 だった場合、数値リストの中身は
『最大桁数は4桁になります。最小桁数は2桁です。』
『[設定値]が1000の時、リストに1000以上は存在しません。』
の条件により、リスト内は 10 以上 999 以下の値に限られるわけですよね。

仮に、その数値リストの中身に 500 以下の値が存在していなかった場合、
2 つ以上の値の合計は、設定値である 1000 を必ず超えてしまいます。

『[設定値]より大きい場合はNG』
『ひとつだけのデータで完了することもありません』
のいずれかの条件を緩めるか、あるいは
数値リストに「2〜4桁の負の整数」なども許容するとか、
数値リストと設定値の関係性をもう少し見直すとかすれば別ですが…。


> > 一覧からランダムに取り出す方法がわからない?
> 乱数を使うことはできると思います。
最初の質問のからそもそも謎ではあるのですが、そもそも、
乱数を何のために使おうとしているのでしょうか?
ランダムで選ぶ、という点が引っかかっています。

もしかして組み合わせを求めるために乱数を使うのではなく、
設問文となる設定値を決めるために、数値リストと乱数を使う…とか?


> > 複数値の合計値を求める方法が分からない?
> loopで素人なプログラム記述はできると思います。
> > 総当たり的に求めることはできているが、効率の良い方法を相談したい?
> はい。効率の良い方法がわかりません。
ではプログラムというよりは、ロジックに関する質問ということでしょうか。

それでは現状のロジックはどのようなもので、
それだとどの程度の時間がかかっていて、
それをどこまで縮めたいのでしょうか。

比較対象となる現状の制作物(あるいは具体的な不明点の提示)が無いと、
質問ではなく、単なる制作依頼になってしまうので…。

[ツリー表示へ]
タイトルRe^4: 組み合わせ合計探索
記事No12095
投稿日: 2023/02/09(Thu) 21:31
投稿者たけし
お世話になります。

> > > > hhttps://hatenachips.blog.fc2.com/blog-entry-430.html
> > > 上記では『値リストがあって、そのすべての組み合わせの中から選ぶ』ものでしたが、
> > > 今回のは「個数リストがあって、その個数だけ(何かを)ランダムに選ぶ」…ということですか?
> > 個数は意識していなくて、
>
> 元の設問は、『[個数]よりランダムに選んだ合計値』と書かれていましたが、
> 実際には『個数は意識していない』と…?
>
> となると、個数 = 12 が選ばれたからと言って、12 個の値を合計していく…といった課題では無さそうですね。
はい。



> どうやら、当初の質問の [個数] という言葉のままだと、意味が混乱してしまいそうなので、
> 参考サイトの VBA 版にあるように、[数値] のリストと読み替えさせてもらいますが、不都合はありますか?
ありません。



> > リストの中から合計した値が、[設定値]と同じか、または[設定値]-20以内の範囲の
> > 値を求めたいと思っています。合計した全ての値と合計値を表示したいです。
> > [設定値]より大きい場合はNGです。
> 参考サイトにあるものは、すべての組み合わせの中から、最適解(合計値が一致する組み合わせ)を
> 選ぶという問題でしたが、今回はそうではなく、「ランダムに選んだ合計値」が前提なのですよね?
>
> ランダムに選ぶという点について、もう少し具体的に説明していただけないでしょうか。
リストの中から[設定値]と同じか、または[設定値]-20以内の範囲を
短時間で選べれば問題ないです。


> また、日本語で「以内」という言葉を使った場合、文脈によっては
> 以上/以下の意味なのか、超過/未満の意味なのかがブレることがあるので、
> この点ももう少し事前確認しておきたいところ。例えば設定値が 3000 だった場合、
> 「2980 以上 3000 以下」とするのか「2980 超過 3000 以下」とするのか…。
>
> ひとまず、以上/以下という意味で良いでしょうか? (以内は、基準点を含むことが多いので)
はい。そこまで細かくなくても問題はないです。
設定値 または 設定値 -20以内(1ザックリ20以内としています)
>
>
> > リストにある最大桁数は4桁になります。
> 当初の質問とは異なる課題を提示されているように聞こえるのですが…何の冗談でしょう?
すみません。
このようなイメージでといった解釈でお願いいたします。

> > 最小桁数は2桁です。
> 値はすべて自然数ですか? それとも負の整数なども含まれますか?
自然数のみです。


> > > ランダムに、どこから、何個の値の組み合わせを、何回取り出して比較するのでしょうか。
> > リストにある総データ数は多くても50以内です。
> > ペアとは限りませんし、ひとつだけのデータで完了することもありません。
>
> ・数値リストの総データ数が、最大50個というのは分かりました。
> ・数値リストの総データ数は、最小何個でしょうか。
1の時もあります。答えが出ない場合は「抽出できませんでした」のメッセージ表示考えています。


>  0個 や 1個 ではなさそうなので… 最低 2 個以上? あるいは 10個ぐらい?
ダメなものはダメなので、メッセージ表示して伝えます。

> ・リスト内から値を選んで合計する際に、何個のデータを選べるのでしょうか。
答えが出るまで求めます。ダメなときはメッセージで伝えます。

>  1 個しか選択しない、というのは駄目らしいですが…
そういう場合もあるので、メッセージで伝えます。

>  たとえば最大20個などといった上限あり? あるいは全部選択されることもある?
答えが出る限りリストをすべて検索します。
ダメなものはダメで伝えます。

> ・リスト内から、同じ項目が複数回、重複して選ばれても良いのでしょうか?
リスト内に同じ値は重複することもあります。
個々に分けて算出し最善の結果を求めます。

> ・リスト内の値は「A:同一値が含まれている可能性もある」もしくは
>  「B:すべて異なる数値であることが保証される」のいずれでしょうか?
同一値あります。すべて異なる場合もあります。


> > [設定値]は変化しますが、
> > [設定値]が1000の時、リストに1000以上は存在しません。
> ここまでの条件を鑑みると、「該当する組み合わせがひとつも存在しない」
> というパターンも少なからず発生してしまいそうです。それでも問題ないのでしょうか?
メッセージで該当するデータありません。などで伝えます。

> あるいは常に何かしらの組み合わせが存在するような、他の条件があるのでしょうか?
無いものは無いです。


> たとえば設定値が 1000 だった場合、数値リストの中身は
> 『最大桁数は4桁になります。最小桁数は2桁です。』
> 『[設定値]が1000の時、リストに1000以上は存在しません。』
> の条件により、リスト内は 10 以上 999 以下の値に限られるわけですよね。
最大で1500くらいです。最小は10です。


> 仮に、その数値リストの中身に 500 以下の値が存在していなかった場合、
> 2 つ以上の値の合計は、設定値である 1000 を必ず超えてしまいます。
その場合はNG処理します。


> > > 一覧からランダムに取り出す方法がわからない?
> > 乱数を使うことはできると思います。
> 最初の質問のからそもそも謎ではあるのですが、そもそも、
> 乱数を何のために使おうとしているのでしょうか?
> ランダムで選ぶ、という点が引っかかっています。
ランダムに拘らなくても問題ありません。
結果だけが欲しいです。


> もしかして組み合わせを求めるために乱数を使うのではなく、
> 設問文となる設定値を決めるために、数値リストと乱数を使う…とか?
乱数も特に必要ありません。
結果が全てです。(できれば検索に掛かるスピードあったほうが良いレベルです)


> > > 複数値の合計値を求める方法が分からない?
> > loopで素人なプログラム記述はできると思います。
> > > 総当たり的に求めることはできているが、効率の良い方法を相談したい?
> > はい。効率の良い方法がわかりません。
> ではプログラムというよりは、ロジックに関する質問ということでしょうか。
>
> それでは現状のロジックはどのようなもので、
> それだとどの程度の時間がかかっていて、
> それをどこまで縮めたいのでしょうか。
以前vb.net以外のソフトで同じような処理を作りました。
効率の良いものではなかったので
相談させていただいています。


> 比較対象となる現状の制作物(あるいは具体的な不明点の提示)が無いと、
> 質問ではなく、単なる制作依頼になってしまうので…。
はい。前回失敗しているので、模索していたところです。

[ツリー表示へ]
タイトルRe^5: 組み合わせ合計探索
記事No12096
投稿日: 2023/02/10(Fri) 10:34
投稿者魔界の仮面弁士
> そこまで細かくなくても問題はないです。
条件を曖昧にする方が、プログラムとして大変になることも多いので、認識合わせをしています。
該当する組み合わせをすべて見つけるという設問なのであれば猶の事。

たとえば重複値を許可するかどうか、という点ひとつとってみてもそうです。

重複値を許可しない場合は、SortedSet や HashSet を使えたけれど、
重複値があったので List 管理に変更した…といった違いが生じるかもしれないわけで。


> > > ペアとは限りませんし、ひとつだけのデータで完了することもありません。
> > ・数値リストの総データ数が、最大50個というのは分かりました。
> > ・数値リストの総データ数は、最小何個でしょうか。
> 1の時もあります。
そうすると、『ひとつだけのデータで完了することもありません』とは、どういう意味でしょうか。
ここでいう「ひとつだけのデータ」とは、何を指しているのでしょうか。


> > ・リスト内から、同じ項目が複数回、重複して選ばれても良いのでしょうか?
> リスト内に同じ値は重複することもあります。
> 個々に分けて算出し最善の結果を求めます。
いえ、リスト内の値について聞いているのではなく、リストから何を選ぶかという話です。

「同じ項目が複数回、重複して選ばれる」というのは、
たとえば値リストに a, b, c という 3 つの値があったときに、
a + c や a + b + c だけでなく、
a + a や、a + b + c + c を認めるか、という意味です。


だからこそ、
> > ・リスト内から値を選んで合計する際に、何個のデータを選べるのでしょうか。
> 答えが出るまで求めます。ダメなときはメッセージで伝えます。
このやりとりで、最大回数を聞いてみた次第です。

たとえば重複選択を許可した場合、値リストに 10 個の数値があり、
その最小値を 25 回抽出しら設定値に合致した…というケースも許容されます。

一方、リスト内の値は重複するが、重複選択は許可しない、となれば、
抽出回数は「1 以上、リスト内容の要素数以下」となるわけで。

要素数以下ではなく『答えが出るまで求める』ということは、重複選択ありということでしょうか?


> 結果だけが欲しいです。
その結果は、どのように表示するのでしょうか?

たとえば参考元の Excel にあるように、何番目の項目が選択されたのかを
表示することを想定しておられますか?
(重複選択するなら、「○」の代わりに「選択回数」を併記するなど)

それとも、合計値の一覧さえ得られれば、どれを選択したのかという情報は不要ですか?
これは、値リストの管理に添字情報が必要になるのか否か、という点で重要です。


もしも「どれを選択したのか」まで情報として必要となる場合、
それを保持するためのデータ管理の仕方も当然変わってきます。


話を単純化するため、条件値を少し小さくして、
値リストの中身が 3 項目(A, B, C)しかない場合を考えてみましょう。
ここでは同一値を含むリストで (A, B, C) = (15, 27, 27) だったとします。

ここで、[設定値] を 60 とすると、求めるべき範囲は 40以上60以下と定まります。
リストからの重複選択を許す場合、得られる組み合わせとしては
 60 = 15 を4回
 57 = 15 を2回と 27 を1回
 54 = 27 を2回
 45 = 15 を3回
 42 = 15 を1回と 27 を1回
の 5 パターンですね。ここまでは良いでしょうか。


さて、ここでさらに「どれを選択したのか」まで情報が必要だったとしましょう。
その場合、27 という値が、B のことなのか C のことなのかまで区別せねばなりません。
この場合、重複抽出許可な設定であれば
 60 = A + A + A + A
 57 = A + A + B
 57 = A + A + C
 54 = B + B
 54 = B + C
 54 = C + C
 45 = A + A + A
 42 = A + B
 42 = A + C
という選択肢が生じて、合計値としては 5 種類のままですが、
その組み合わせとしては 9 パターンへと増加します。

ここに「選択順」の管理まで必要になるとすれば、さらに情報量が増えます。
仮に、リスト内の重複値は許可するが、同じ項目を重複選択することは禁止するという制限を加えても、
選択順まで考えねばならない場合、それだけで
 54 = B + C
 54 = C + B
 42 = A + B
 42 = A + C
 42 = B + A
 42 = C + A
の組み合わせが発生します。合計値としては 2 種類しかないのに、組み合わせとしては 6 パターンです。

さらに厄介なことに、リスト内の重複値は許容されたままなので、
 54 = B + C
 54 = C + B
はいずれも、「27 + 27」となってしまい、見た目が変わりません。
ラベルやメッセージボックスで「27 + 27」あるいは「54」を書くような方法では、
見た目上区別できないので、こうなると
  ┃54│54│42│42│42│42│
 ━╋━┿━┿━┿━┿━┿━┿
 15┃ │ │ 1│ 2│ 1│ 1│
 27┃ 1│ 2│ 2│ 1│ │ 2│
 27┃ 2│ 1│ │ │ 2│ │
などの形式で表示する必要があるかもしれません。
(参考元 URL では項目横に○印をつける表記だったので、それを真似ています)


このように、条件や情報量がちょっと変わっただけで、考え方も管理方法も
まるで変わってしまう事があります。結果をどのように表示するかは重要ではないものの、
最終結果に何を求めているのかによっては、データの持ち方や探索手続きを
調整する必要が生じるかもしれません。ですから、条件が後出しで変えられてしまったり、
『そこまで細かくなくても問題はない』などと言われると、ちょっと困る…。



> 以前vb.net以外のソフトで同じような処理を作りました。
今回選択しているのは、VB2010 という、結構古めの言語なんですよね。
(Iterator Function で列挙させようとしたら、2010 には反復子の糖衣構文が無くて複雑化したので保留中)

とはいえ世代的には一応、Parallel.For による並列演算をサポートする最低バージョンではあるので、
並列処理することを検討してみては如何でしょうか。分割の仕方が適切でないと、実行コストが
逆に高くつくこともありますので、実際に早くなるかどうかは試さないと分かりませんが…。
https://atmarkit.itmedia.co.jp/fdotnet/chushin/vb2010features_01/vb2010features_01_04.html

> 効率の良いものではなかったので
> 相談させていただいています。
効率はさておき、解は導き出せたわけですよね。それはどんな処理でしたか?
具体的なコードの提示が難しければ、ロジックの説明だけでもお願いします。

その時のロジックよりも効率の悪いものを提示しても意味が無い(徒労になる)ので。

また、「メモリ効率」「速度効率」「保守効率(汎用性/移植性/理解の容易度)」などを
すべて満たすことはできませんから、この逆質問によって、どのあたりを落としどころに
したいと考えているのかを探るという目的もあります。

[ツリー表示へ]
タイトルRe^6: 組み合わせ合計探索
記事No12097
投稿日: 2023/02/10(Fri) 16:38
投稿者たけし
>
> > > > ペアとは限りませんし、ひとつだけのデータで完了することもありません。
> > > ・数値リストの総データ数が、最大50個というのは分かりました。
> > > ・数値リストの総データ数は、最小何個でしょうか。
> > 1の時もあります。
> そうすると、『ひとつだけのデータで完了することもありません』とは、どういう意味でしょうか。
> ここでいう「ひとつだけのデータ」とは、何を指しているのでしょうか。

次のように検索した結果が1件の場合もあります。

リスト
------
 57


> > > ・リスト内から、同じ項目が複数回、重複して選ばれても良いのでしょうか?
> > リスト内に同じ値は重複することもあります。
> > 個々に分けて算出し最善の結果を求めます。
> いえ、リスト内の値について聞いているのではなく、リストから何を選ぶかという話です。
>
> 「同じ項目が複数回、重複して選ばれる」というのは、
> たとえば値リストに a, b, c という 3 つの値があったときに、
> a + c や a + b + c だけでなく、
> a + a や、a + b + c + c を認めるか、という意味です。
>
>
> だからこそ、
> > > ・リスト内から値を選んで合計する際に、何個のデータを選べるのでしょうか。
> > 答えが出るまで求めます。ダメなときはメッセージで伝えます。
> このやりとりで、最大回数を聞いてみた次第です。
>
> たとえば重複選択を許可した場合、値リストに 10 個の数値があり、
> その最小値を 25 回抽出しら設定値に合致した…というケースも許容されます。
>
> 一方、リスト内の値は重複するが、重複選択は許可しない、となれば、
> 抽出回数は「1 以上、リスト内容の要素数以下」となるわけで。
>
> 要素数以下ではなく『答えが出るまで求める』ということは、重複選択ありということでしょうか?
>
>
> > 結果だけが欲しいです。
> その結果は、どのように表示するのでしょうか?
>
> たとえば参考元の Excel にあるように、何番目の項目が選択されたのかを
> 表示することを想定しておられますか?
> (重複選択するなら、「○」の代わりに「選択回数」を併記するなど)
>
> それとも、合計値の一覧さえ得られれば、どれを選択したのかという情報は不要ですか?
> これは、値リストの管理に添字情報が必要になるのか否か、という点で重要です。
>
>
> もしも「どれを選択したのか」まで情報として必要となる場合、
> それを保持するためのデータ管理の仕方も当然変わってきます。
>
>
> 話を単純化するため、条件値を少し小さくして、
> 値リストの中身が 3 項目(A, B, C)しかない場合を考えてみましょう。
> ここでは同一値を含むリストで (A, B, C) = (15, 27, 27) だったとします。
>
> ここで、[設定値] を 60 とすると、求めるべき範囲は 40以上60以下と定まります。
> リストからの重複選択を許す場合、得られる組み合わせとしては
>  60 = 15 を4回
>  57 = 15 を2回と 27 を1回
>  54 = 27 を2回
>  45 = 15 を3回
>  42 = 15 を1回と 27 を1回
> の 5 パターンですね。ここまでは良いでしょうか。

説明不足で大変申し訳ありません。

寸法に重複データはありますが
番号を重複して合計値を求めることはありません。
※番号001を数回選択することはできません。
※番号001と005の寸法60(合計:120)を同時に選択できます。

例えば設定値を590とした場合 検索結果は次のようになります。
詳細値:60, 500, 25  合計値:585


◆リスト

番号     寸法
-------- -----
001      60
002   57
003      54
004      45
005      42
006      500
007      1000
005      60
006      25
-中略-      
050      57

> > 以前vb.net以外のソフトで同じような処理を作りました。
> 今回選択しているのは、VB2010 という、結構古めの言語なんですよね。
vb関係でこのような処理を作成するのは初めてでして
前回行った方法は必要なデータをいったんデータベースへ登録して
データをselect文でloopさせる方法でした

番号     寸法
-------- -----
001      60
002   57
003      54
004      45
005      42
006      500
007      1000
005      60
006      25
-中略-      
050      57

番号の001と002〜050までを加算して設定値と比較
答えが出ない場合は
番号の002と001〜050(002除く)までを加算して設定値と比較
答えが出ない場合は
番号の003と001〜050(003除く)までを加算して設定値と比較
のようなイメージです。

説明不足なところがありますが
把握できましたでしょうか。

[ツリー表示へ]
タイトルRe^7: 組み合わせ合計探索
記事No12098
投稿日: 2023/02/10(Fri) 17:12
投稿者魔界の仮面弁士
> > > > > ペアとは限りませんし、ひとつだけのデータで完了することもありません。
> 次のように検索した結果が1件の場合もあります。
ごめんなさい、まだ良くわかりません。

「ひとつだけのデータで完了することもあります」ではなく
「ひとつだけのデータで完了することもありません」なのですよね?


> 寸法に重複データはありますが
No12093 でいうところの『[数値] のリスト』が
[番号]と[寸法]のリストに置き換わった形ですね。

[番号]というのは、抜けの無い連番であり、
配列でいうところのインデックス(添字)のことですかね?
(下限値が 1 から始まる点は注意が必要ですが)


> 番号を重複して合計値を求めることはありません。
了解です。


であれば参考元 URL にあった手順と同様に、データを
寸法の昇順または降順に並び替えてから処理してみてはいかがですか?

たとえば降順とした場合、設定値 590 (つまり 570 以上 590 以下)ということは、
007:1000 などは絶対に使われないことが分かるので、探索回数を削ぎ落せますよね。

また、1 つ目の値として 006:500 が選択された場合、91 以上の値は
設定値を超えてしまうため、 2 つ目の値は 90 以下の値に限定することができます。


> 前回行った方法は必要なデータをいったんデータベースへ登録して
> データをselect文でloopさせる方法でした
データベースでループ処理は、確かに効率が悪いですね…。
再帰クエリが使えないデータベースだったのでしょうか。

[ツリー表示へ]
タイトルRe^8: 組み合わせ合計探索
記事No12099
投稿日: 2023/02/10(Fri) 17:39
投稿者たけし
> > > > > > ペアとは限りませんし、ひとつだけのデータで完了することもありません。
> > 次のように検索した結果が1件の場合もあります。
> ごめんなさい、まだ良くわかりません。
>
> 「ひとつだけのデータで完了することもあります」ではなく
> 「ひとつだけのデータで完了することもありません」なのですよね?
すみません。条件を満たす場合は完了になり、そうでない場合は完了しないになります。


>
>
> > 寸法に重複データはありますが
> No12093 でいうところの『[数値] のリスト』が
> [番号]と[寸法]のリストに置き換わった形ですね。
>
> [番号]というのは、抜けの無い連番であり、
> 配列でいうところのインデックス(添字)のことですかね?
> (下限値が 1 から始まる点は注意が必要ですが)
説明用に「番号」を追加していますが
実際使われるデータは「寸法」だけです。
Oracleへ登録して「寸法」を order by での検索もできます。

> > 前回行った方法は必要なデータをいったんデータベースへ登録して
> > データをselect文でloopさせる方法でした
> データベースでループ処理は、確かに効率が悪いですね…。
> 再帰クエリが使えないデータベースだったのでしょうか。
再起クエリの言葉を初めて知りました。
効率よい使用方法わかりますか?

[ツリー表示へ]
タイトルRe^9: 組み合わせ合計探索
記事No12100
投稿日: 2023/02/10(Fri) 18:48
投稿者魔界の仮面弁士
> > > > > > > ペアとは限りませんし、ひとつだけのデータで完了することもありません。
> > > 次のように検索した結果が1件の場合もあります。
> > ごめんなさい、まだ良くわかりません。
> >
> > 「ひとつだけのデータで完了することもあります」ではなく
> > 「ひとつだけのデータで完了することもありません」なのですよね?
> すみません。条件を満たす場合は完了になり、そうでない場合は完了しないになります。

まだ曖昧です。一言で『条件を満たす場合』と書かれていますが、
ここでいう『条件』とは何のことでしょうか。『完了』というのは、何を終えるのでしょうか。
(何をもって「条件を満たす場合は完了」としたいのか不明瞭だということです)



設定値に完全一致する組み合わせが、まったく見つからない場合もあれば、複数見つかる場合もあります。
完全一致する組み合わせは無いが、「設定値-1」な値が複数見つかる場合もあります。


たとえば完全一致する組み合わせとして、a + b + c と x + y の 2 パターンがある場合、
 ・抽出順も含めて、すべての組み合わせを列挙すべき
 ・すべての組み合わせを列挙すべきだが、抽出順序は気にしない
 ・一つ見つけた時点で探索を打ち切って良い(最終結果には、どういう組み合わせだったのかは示さない)
 ・組み合わせはひとつ挙げれば良いが、寸法の個数が少なく組み合わせを優先したい
 ・リスト内に同じ寸法が複数ある場合、番号の小さい値を優先して使うものとしたい
などなど、色々と検討すべきことはあります。
それによって『条件』も『完了』の定義も変化することでしょう。


また、完全一致する組み合わせが存在しない状況で、
「設定値 - 20 以上 設定値以下」という近似値を満たす組み合わせを探るなら、
手続きはさらに増えることになりますよね。

たとえば、a+b+c が「設定値 - 20」という値だった場合、それは回答候補となりえますが、
残りのリスト内にある x という値が 10 以上 20 以下という値であった場合、
a+b+c+x の方が、より設定値に近い値となりえます。そうすると、a+b+c という候補を
見つけただけでは、『条件を満たす場合は完了』とは呼べません。

こうした色々な状況をひとつひとつ考えていかないと、仕様が曖昧になりますし、
曖昧なままでは、それを伝えるためのプログラムを書くこともままなりません。



> Oracleへ登録して「寸法」を order by での検索もできます。
VB2008 以降なら、データベースを経由せずとも
LINQ を使ってオンメモリで Order By できますよ。


> > 再帰クエリが使えないデータベースだったのでしょうか。
> 再起クエリの言葉を初めて知りました。
> 効率よい使用方法わかりますか?

再起(comeback)ではなく
再帰(recursion)です。

標準 SQL でいうところの WITH 句のことです。
https://atmarkit.itmedia.co.jp/fnetwork/tokusyuu/01sql99/sql99_1b.html


再帰 SQL で連続した日付範囲を用意する例
https://blog.itparadise.jp/?p=732


再帰 SQL で数独を解く例
https://garapon.hatenablog.com/entry/20100817/1282050137

[ツリー表示へ]
タイトルRe^10: 組み合わせ合計探索
記事No12122
投稿日: 2023/03/04(Sat) 00:16
投稿者たけし
> 標準 SQL でいうところの WITH 句のことです。
> https://atmarkit.itmedia.co.jp/fnetwork/tokusyuu/01sql99/sql99_1b.html
>
>
> 再帰 SQL で連続した日付範囲を用意する例
> https://blog.itparadise.jp/?p=732
>
>
> 再帰 SQL で数独を解く例
> https://garapon.hatenablog.com/entry/20100817/1282050137



御世話になります。

サンプルのようなことをSQLでも実現できるものでしょうか?

[ツリー表示へ]
タイトルRe^7: 組み合わせ合計探索
記事No12101
投稿日: 2023/02/10(Fri) 23:51
投稿者魔界の仮面弁士
> 例えば設定値を590とした場合 検索結果は次のようになります。
> 詳細値:60, 500, 25  合計値:585

「詳細値」に表示している寸法値のうち、60 という値は

> 番号     寸法
> -------- -----
> 001      60
> 005      60

の 2 つがありますが、どちらの番号の寸法なのかは、区別されないということでしょうか?

また、結果を表示する際の「60, 500, 25」という表記は、
他の並び順…たとえば「500, 60, 25」などと表示しても良いのでしょうか。
それとも、番号順に表示せねばならないのでしょうか。
(番号順に表示するルールだとすると、001番の 60 と 005番の 60 を区別する必要がありますね)



> 例えば設定値を590とした場合 検索結果は次のようになります。
> 詳細値:60, 500, 25  合計値:585

585 よりも、587 の方が設定値に近いように思えましたが、
585 の方が優先されるのでしょうか。

> 番号     寸法
> -------- -----
> 004      45
> 005      42
> 006      500

[ツリー表示へ]
タイトルRe^8: 組み合わせ合計探索
記事No12106
投稿日: 2023/02/13(Mon) 19:14
投稿者たけし
お世話になります。

サンプルありがとうございます。
(中を見ますと私にとってとても難しく感じています。)

番号と寸法を検索しています Formがありまして、
こちらへサンプル(No.12102 )を組み込もうと試みました。

Class1.vb と Module1.vb をプロジェクトに追加しまして
(ここまで問題なかったでしょうか?)
サンプルをそれぞれに記述しコンパイルしたところエラー出ています。
内容としましては次のようになっています。

対処方法わかりますでしょうか?

If values.Any(Function(v) v <= 0) Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")
→Any はsystem.array のメンバーではありません。

Console.WriteLine("合計値:{0} 詳細値:{1}", 結果.Sum(), String.Join(", ", 結果.Select(Function(寸法) CStr(寸法))))
→select はsystem.array のメンバーではありません。

Console.WriteLine("合計値:{0} 詳細値:{1}", 結果.Sum(), String.Join(", ", 結果.Select(Function(寸法) CStr(寸法))))
→selet はsystem.Sum のメンバーではありません。

Dim Search As Action(Of Integer, Node) =
→system.action(Of T)の型引数が多すぎます。

Dim ordered As Integer() = (From v In values Where v <= targetValue Order By v).ToArray()
→※valuesの所で※  型 Integerの 1次元配列'の式はクエリ不可能です。LINQプロバイターに対してアセンブリ参照や
名前空間インポートが不足していないことを確認してください。

[ツリー表示へ]
タイトルRe^9: 組み合わせ合計探索
記事No12107
投稿日: 2023/02/13(Mon) 23:55
投稿者魔界の仮面弁士
> (中を見ますと私にとってとても難しく感じています。)

他人が書いたコードを読むのは大変だろうとおもいます。
不明点があれば、説明を加えたり、別の書き方に
変更するなどのお手伝いはいたします。

プログラムの書き方がわからないとのことでしたが、
そもそも参考元(Excel VBA)のサイトに描かれていた
アルゴリズム(考方、手順)は把握できていますか?
まずはそこからかと。


> サンプルをそれぞれに記述しコンパイルしたところエラー出ています。

プロジェクトを作成する際に、「.NET Framework 4」を選択していなかったのでしょう。

おそらくは、ターゲット フレームワークが .NET Framework 2.0 もしくは 3.0 に
設定されているのだと思います。[My Project] のプロパティの [コンパイル]タブで、
[詳細コンパイル オプション]ボタンを押して、[対象のフレームワーク]を確認してみてください。

.NET Framework 4 にすれば動作すると思います。
(Visual Studio 2010 は、.NET Framework 2.0/3.0/3.5/4 をサポートしています。)


何らかの理由で .NET Framework 4 を選択できない場合には、
せめて .NET Framework 3.5 にまで上げることを検討してください。

.NET Framework 3.5 の場合は、
 String.Join(", ", 結果.Select(Function(寸法) CStr(寸法)))
と書かれている部分を
 String.Join(", ", 結果.Select(Function(寸法) CStr(寸法)).ToArray())
にすればコンパイルが通るはずです。

※String.Join( String, IEnumerable(Of String) ) メソッドは .NET Framework 4 以上が必要ですが
 String.Join( String, String() ) メソッドであれば .NET Framework 1.0 以上にて利用可能です。

…それとも、.NET Framework 2.0 向けのサンプルが必要だったりしますか?



ちなみに .NET Framework のサポート期間は以下の通りです。

 .NET Framework 1.0 Service Pack 1 …… 2009/07/14 終了済み
 .NET Framework 1.1 Service Pack 1 …… 2013/10/08 終了済み
 .NET Framework 2.0 Service Pack 2 …… 2011/07/12 終了済み
 .NET Framework 3.0 Service Pack 2 …… 2011/07/12 終了済み
 .NET Framework 3.5 Service Pack 1 …… 2029/01/09 まで
 .NET Framework 4 Update 3 ……………… 2016/01/12 終了済み
 .NET Framework 4.5 ………………………… 2016/01/12 終了済み
 .NET Framework 4.5.1 ……………………… 2016/01/12 終了済み
 .NET Framework 4.5.2 ……………………… 2022/04/26 終了済み
 .NET Framework 4.6 ………………………… 2022/04/26 終了済み
 .NET Framework 4.6.1 ……………………… 2022/04/26 終了済み
 .NET Framework 4.6.2 ……………………… 搭載OSのサポート期限まで
 .NET Framework 4.7 ………………………… 搭載OSのサポート期限まで
 .NET Framework 4.7.1 ……………………… 搭載OSのサポート期限まで
 .NET Framework 4.7.2 ……………………… 搭載OSのサポート期限まで
 .NET Framework 4.8 ………………………… 搭載OSのサポート期限まで
 .NET Framework 4.8.1 ……………………… 搭載OSのサポート期限まで

また、Windows 10 でサポートされている .NET Framework バージョンは下記の通りです。

 Windows 10 ver1507 ……………… 2.0/3.0/3.5 および 4.6(プリインストール)/4.6.1/4.6.2
 Windows 10 ver1511 ……………… 2.0/3.0/3.5 および 4.6.1(プリインストール)/4.6.2
 Windows 10 ver1607 ……………… 2.0/3.0/3.5 および 4.6.2(プリインストール)/4.7/4.7.1/4.7.2/4.8
 Windows 10 ver1703 ……………… 2.0/3.0/3.5 および 4.7(プリインストール)/4.7.1/4.7.2/4.8
 Windows 10 ver1709 ……………… 2.0/3.0/3.5 および 4.7.1(プリインストール)/4.7.2/4.8
 Windows 10 ver1803/1809 ……… 2.0/3.0/3.5 および 4.7.2(プリインストール)/4.8
 Windows 10 ver1903/1909/2004 … 2.0/3.0/3.5 および 4.8(プリインストール)
 Windows 10 ver20H2/21H1/22H2 … 2.0/3.0/3.5 および 4.8(プリインストール)/4.8.1
 ※ただし、21H1 以下のバージョンは既にサポート期限切れ
 ※Window 10 21H2 のサポート期限は 2023/06/13
 ※Window 10 22H2 のサポート期限は 2024/05/14
 ※Window 10 最終バージョン(2023年3〜4月頃リリース見込み)のサポート期限は 2025/10/14

[ツリー表示へ]
タイトルRe^10: 組み合わせ合計探索
記事No12108
投稿日: 2023/02/14(Tue) 14:06
投稿者たけし
お世話になります。

.NET Framework 3.5、.NET Framework 4.0でも
同じエラーでます。
iが追加でエラーでるようになりました
( Dim i As Integer )


If values.Any(Function(v) v <= 0) Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")
→Any はsystem.array のメンバーではありません。
For i = index To maxIndex
→ i は宣言されていません。アクセスできない保護レベルになっています。
Console.WriteLine("合計値:{0} 詳細値:{1}", 結果.Sum(), String.Join(", ", 結果.Select(Function(寸法) CStr(寸法))))
→select はsystem.array のメンバーではありません。
Console.WriteLine("合計値:{0} 詳細値:{1}", 結果.Sum(), String.Join(", ", 結果.Select(Function(寸法) CStr(寸法))))
→selet はsystem.Sum のメンバーではありません。
Dim ordered As Integer() = (From v In values Where v <= targetValue Order By v).ToArray()
→※valuesの所で※  型 Integerの 1次元配列'の式はクエリ不可能です。LINQプロバイターに対してアセンブリ参照や
名前空間インポートが不足していないことを確認してください。

[ツリー表示へ]
タイトルRe^11: 組み合わせ合計探索
記事No12109
投稿日: 2023/02/14(Tue) 14:48
投稿者魔界の仮面弁士
まずはいきなり自作アプリに組み込もうとするのではなく、
新規の コンソール アプリケーション プロジェクト(.NET Framework 4)を作成し、
期待する動作になっているか、個々の処理が何をしているのかを確認するようにしてみてください。

内容を理解していない状況で、前提条件の異なる環境に組み込もうとするのは無謀かと…。
(ある程度の基礎知識が十分にある場合には、いきなり組み込むこともできるでしょうけれども)


> .NET Framework 3.5、.NET Framework 4.0でも
> 同じエラーでます。
最初から 3.5 / 4 のプロジェクトで作成した場合も同様ですか?

> LINQプロバイターに対してアセンブリ参照や
> 名前空間インポートが不足していないことを確認してください。

[My Project]-[参照]タブ-[インポートされた名前空間]にて、
System.Linq 名前空間にチェックマークをいれてありますか?
(もしくは、.vb ファイルの先頭に Imports System.Linq と宣言する)



新規のコンソール アプリケーションを、
 A: 最初から .NET Framework 4 向けに作成したもの
 B: .NET Framework 2.0 向けで作成し、あとからターゲットを 4 向けにしたもの
とで比較すると、既定でインポートされた名前空間が異なっていることを確認できるでしょう。

[ツリー表示へ]
タイトルサンプル
記事No12102
投稿日: 2023/02/12(Sun) 10:52
投稿者魔界の仮面弁士
> Windows10
> vb.net 2010使用しています。

手元に VB2010 が無いので、
「VB2022 + .NET Framework 4」のコンソールアプリで作りました。

VB2010 当時の文法仕様だけで書いたつもりですが、
コンパイル エラーが出るようならご指摘ください。
→追記:VB2010 での動作を確認しました。(VB2008 では動きません)


・基本的なアルゴリズムは、最初の質問にあった Excel VBA 版の「木構造と枝刈りロジック」と同じです。
 https://blog-imgs-67-origin.fc2.com/h/a/t/hatenachips/VBASearchSumAlgo.png
 VBA 版では、ソート処理部を自作(クイックソート)していましたが、こちらは LINQ で処理しています。



・参考 URL (Excel VBA 版)では、合致する組み合わせを複数列挙していましたが、
 今回のコードは「合致する組み合わせを一つ見つけたら、そこで探索終了」としています。

・合致しない場合はより近い値を求める…というルールだったので、発見できない時は
 設定値を 1 ずつ減らして、再度探索しなおすという方式を採っています。

・No12091 の設問と No12093 の「最大桁数は4桁になります。最小桁数は2桁です。」の要件が
 矛盾するため、値リストの条件として No12095 の「自然数のみです。」を採用しています。

・[番号]は無視して、[寸法]の組み合わせのみを管理しています。そのため、
 No12097 にて『詳細値:60, 500, 25』という結果が例示されていましたが、このコードでは
 昇順に並んだ『詳細値:25, 60, 500』という結果で出力されます。


'-------------
Option Strict On

Public Class Node
    Inherits List(Of Node)
    Public ReadOnly Value As Integer    '選択された[値]
    Public ReadOnly Parent As Node      'ひとつ前に選択した[値]
    Public ReadOnly Total As Integer    '祖先からここまでの[値]の合計
    Public Sub New(Parent As Node, Value As Integer)
        Me.Value = Value
        Me.Parent = Parent
        Total = Value + If(Parent Is Nothing, 0, Parent.Total)
    End Sub
End Class

Module Module1
    Sub Main()
        'No12097 の設問
        Dim 値一覧1 As Integer() = {60, 57, 54, 45, 42, 500, 1000, 60, 25, 57}

        'No.12091 の設問
        Dim 値一覧2 As Integer() = {5988, 2994, 1245, 3296, 19777, 1497, 14823, 13177, 37885, 5988, 6290, 6038, 22653, 28474, 29564, 26871, 23844, 4366, 4101, 14116, 7037, 17500, 24062, 23644, 17717, 25162, 9461, 19788, 29762, 25099, 28935, 1011, 4655, 22234, 9589, 30377, 10081, 2887, 24336, 3517, 16020, 6494, 16745, 24100, 28340, 24825, 13382, 6801, 19893, 28700}


        '『設定値:590 合計値:587 詳細値:42, 45, 500』
        探索(590, 値一覧1)

        '『設定値:586 合計値:585 詳細値:25, 60, 500』
        探索(586, 値一覧1)

        '『設定値:88792 合計値:88792 詳細値:1011, 1245, 1497, 2887, 2994, 3296, 3517, 4101, 4366, 4655, 6290, 6494, 14116, 14823, 17500』
        探索(88792, 値一覧2)

        Console.ReadKey()
    End Sub

    Sub 探索(設定値 As Integer, 寸法一覧 As Integer())
        Console.Write("設定値:{0} ", 設定値)
        Dim 結果 As Integer() = {}
        For 設定値 = 設定値 To 設定値 - 20 Step -1
            結果 = FindCombination(設定値, 寸法一覧)
            If 結果.Length > 0 Then Exit For
        Next
        If 結果.Length = 0 Then
            Console.WriteLine("抽出できませんでした。")
        Else
            Console.WriteLine("合計値:{0} 詳細値:{1}", 結果.Sum(), String.Join(", ", 結果.Select(Function(寸法) CStr(寸法))))
        End If
    End Sub

    ''' <summary>合計値が完全一致する組み合わせを探す</summary>
    ''' <param name="targetValue">設定値</param>
    ''' <param name="values">値リスト</param>
    ''' <returns>最初に見つけたものを一つだけ返す</returns>
    Public Function FindCombination(targetValue As Integer, ParamArray values As Integer()) As Integer()
        If values Is Nothing OrElse values.Length = 0 Then Throw New ArgumentNullException("values")
        'If values.Any(Function(v) v < 10 OrElse v > 9999) Then Throw New ArgumentOutOfRangeException("values", "2〜4桁の自然数が必要です。")
        If values.Any(Function(v) v <= 0) Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")

        '設定値を超えるものは除外した上で、[値]の昇順に並べる
        Dim ordered As Integer() = (From v In values Where v <= targetValue Order By v).ToArray()

        '探索処理
        Dim maxIndex = ordered.GetUpperBound(0)
        Dim edge As Node = Nothing  '発見した組み合わせ
        Dim Search As Action(Of Integer, Node) =
            Sub(index, parent)
                If Not edge Is Nothing Then Return  '既に発見済み
                For i = index To maxIndex
                    Dim nextValue = ordered(i)      '値を昇順に抽出
                    Dim nextNode As New Node(parent, nextValue)
                    If nextNode.Total <= targetValue Then
                        parent.Add(nextNode)        '超過しないなら抽出
                        If nextNode.Total = targetValue Then
                            edge = nextNode         '目標値に達したので探索終了
                            Return
                        Else
                            Search(i + 1, nextNode) '再帰して次の組み合わせを選ぶ
                        End If
                    End If
                Next
            End Sub

        '探索実行
        Dim root As New Node(Nothing, 0)
        Search(0, root)
        If edge Is Nothing Then
            '見つからなかった
            Return New Integer(-1) {}
        Else
            Dim result As New Stack(Of Integer)()
            Dim e = edge
            Do
                result.Push(e.Value)
                e = e.Parent
            Loop Until e Is root
            Return result.ToArray()
        End If
    End Function
End Module

[ツリー表示へ]
タイトルサンプル2
記事No12103
投稿日: 2023/02/12(Sun) 12:54
投稿者魔界の仮面弁士
> ・参考 URL (Excel VBA 版)では、合致する組み合わせを複数列挙していましたが、
>  今回のコードは「合致する組み合わせを一つ見つけたら、そこで探索終了」としています。

先程の Function FindCombination は「最初に見つけたもの」を返す実装でしたが
今度の Function FindCombinations は、「条件に合致したものすべて」を
位置情報も含めて列挙するようにしてあります。(最小値と最大値を指定する仕様に変更)


> ・[番号]は無視して、[寸法]の組み合わせのみを管理しています。そのため、
>  No12097 にて『詳細値:60, 500, 25』という結果が例示されていましたが、このコードでは
>  昇順に並んだ『詳細値:25, 60, 500』という結果で出力されます。

条件に合致したもの組み合わせに対して、位置番号も併せて得られるようにしてみました。
これにより、重複値をもつ一覧であっても、どちらが選択されたのか分かるようになっています。

たとえば、585 という値を 60+500+25 の組み合わせを作成した場合に、
  詳細値:[0]=60, [5]=500, [8]=25
  詳細値:[5]=500, [7]=60, [8]=25
のように、位置番号の異なる重複値だった場合、それらは異なる組み合わせとして扱われます。
※各組み合わせは、位置番号順にて返されます。


ただし、複数の組み合わせを列挙するようになったため、アイテム数が多くなると、
列挙が開始されるまでに長い時間がかかってしまいます。

管理情報が増えたため、コードとしては少し複雑に見えるかも知れませんが、
探索ロジックは先の No12102 のサンプルと同一です。

そのため、このコードを読み解くのであれば、
先に No12102 の手順を把握してからの方が良いと思います。


ただし今回のコードは、 No12091 の「最も近い組み合わせを獲得したい」を優先しており、
「最小値を超えたけれど、もっと最大値に近い組み合わせがある」場合、必ずしも列挙されません。
そのため、すべての組み合わせが得られるわけではありません。
(それでも一応、当初の目的には合致しているはず…)

Dim 値一覧 = {1, 2, 3, 4, 5}
result = FindCombinations(1,  5, 値一覧) '1 以上  5 以下の組み合わせ

上記の場合、
 5 = 1+4, 2+3, 5
 4 = 1+3, 4
 3 = 1+2, 3
が列挙されますが、下記の組み合わせは取りこぼされます。
 2 = 2 → 2+3 にすれば、最大値により近くなるため
 1 = 1 → 1+4 にすれば、最大値により近くなるため


------
寸法一覧:10個
 [0]=60
 [1]=57
 [2]=54
 [3]=45
 [4]=42
 [5]=500
 [6]=1000
 [7]=60
 [8]=25
 [9]=57

設定値:570〜590
 合計値:587 組み合わせ:1件
  詳細値:[3]=45, [4]=42, [5]=500
 合計値:585 組み合わせ:2件
  詳細値:[0]=60, [5]=500, [8]=25
  詳細値:[5]=500, [7]=60, [8]=25
 合計値:582 組み合わせ:2件
  詳細値:[1]=57, [5]=500, [8]=25
  詳細値:[5]=500, [8]=25, [9]=57
 合計値:579 組み合わせ:1件
  詳細値:[2]=54, [5]=500, [8]=25
 合計値:570 組み合わせ:1件
  詳細値:[3]=45, [5]=500, [8]=25

'-------------
Option Strict On
Public Class Node
    Inherits List(Of Node)
    Public ReadOnly Value As Tuple(Of Integer, Integer)    '選択された[位置番号]と[値]
    Public ReadOnly Parent As Node      'ひとつ前に選択した[値]
    Public ReadOnly Total As Integer    '祖先からここまでの[値]の合計
    Public Sub New(Parent As Node, Index As Integer, Value As Integer)
        Me.Value = Tuple.Create(Index, Value)
        Me.Parent = Parent
        Total = Value + If(Parent Is Nothing, 0, Parent.Total)
    End Sub
End Class

Module Module1
    Sub Main()
        'No12097 の設問
        Dim 値一覧 As Integer() = {60, 57, 54, 45, 42, 500, 1000, 60, 25, 57}
        複数探索(570, 590, 値一覧)

        Console.ReadKey()
    End Sub


    Sub 複数探索(最小設定値 As Integer, 最大設定値 As Integer, 寸法一覧 As Integer())
        Console.WriteLine("寸法一覧:{0}個", 寸法一覧.Length)
        For i = 0 To 寸法一覧.Length - 1
            Console.WriteLine(" [{0}]={1}", i, 寸法一覧(i))
        Next
        Console.WriteLine()
        Console.WriteLine("設定値:{0}〜{1}", 最小設定値, 最大設定値)
        Dim 結果 = FindCombinations(最小設定値, 最大設定値, 寸法一覧)
        If 結果.Count = 0 Then
            Console.WriteLine("抽出できませんでした。")
        Else
            For Each result In 結果.OrderByDescending(Function(x) x.Key)
                Console.WriteLine(" 合計値:{0} 組み合わせ:{1}件", result.Key, result.Value.Count)
                For Each values In result.Value
                    Console.WriteLine("  詳細値:" & String.Join(", ", values.OrderBy(Function(x) x.Item1).Select(Function(v) String.Format("[{0}]={1}", v.Item1, v.Item2))))
                Next
            Next
        End If
    End Sub

    ''' <summary>合計値が範囲内となる組み合わせを列挙する</summary>
    ''' <param name="minValue">探索したい合計値の下限</param>
    ''' <param name="maxValue">探索したい合計値の上限</param>
    ''' <param name="values">「Key = 合計値, Value = (Index, 値)の組み合わせ」の一覧</param>
    Public Function FindCombinations(minValue As Integer, maxValue As Integer, ParamArray values As Integer()) As SortedDictionary(Of Integer, List(Of Tuple(Of Integer, Integer)()))
        If minValue > maxValue Then Throw New ArgumentOutOfRangeException("minValue", minValue, "minValue は maxValue 以下である必要があります。")
        If values Is Nothing OrElse values.Length = 0 Then Throw New ArgumentNullException("values")
        If values.Any(Function(v) v <= 0) Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")

        '設定値を超えるものは除外した上で、[値]の昇順に並べる
        Dim ordered = (
            From v In values.Select(Function(value, index) New With {Key index, value})
            Where v.value <= maxValue
            Order By v.value, v.index
        ).ToArray()

        Dim root As New Node(Nothing, -1, 0)

        'Node から値リストを作る
        Dim GetValueArray As Func(Of Node, Tuple(Of Integer, Integer)()) =
            Function(node)
                Dim result As New Stack(Of Tuple(Of Integer, Integer))
                Dim item = node
                Do
                    result.Push(item.Value)
                    item = item.Parent
                Loop Until item Is root OrElse item Is Nothing
                Return result.ToArray()
            End Function

        '探索処理
        Dim maxIndex = ordered.GetUpperBound(0)
        Dim edges As New SortedDictionary(Of Integer, List(Of Tuple(Of Integer, Integer)()))()
        Dim Search As Action(Of Integer, Node) =
            Sub(index, parent)
                For i = index To maxIndex
                    Dim nextItem = ordered(i)       '値を昇順に抽出
                    Dim nextNode As New Node(parent, nextItem.index, nextItem.value)
                    If nextNode.Total <= maxValue Then
                        parent.Add(nextNode)        '超過しないなら抽出
                        Search(i + 1, nextNode)     '再帰して次の組み合わせを選ぶ
                    End If
                Next
                If parent.Count = 0 Then
                    If parent.Total >= minValue Then
                        '最低値条件をクリアした終端を登録
                        Dim lst As List(Of Tuple(Of Integer, Integer)()) = Nothing
                        If Not edges.TryGetValue(parent.Total, lst) Then
                            lst = New List(Of Tuple(Of Integer, Integer)())()
                            edges.Add(parent.Total, lst)
                        End If
                        lst.Add(GetValueArray(parent))
                    End If
                End If
            End Sub

        '探索実行
        Search(0, root)
        Return edges
    End Function
End Module

[ツリー表示へ]
タイトルサンプル3
記事No12104
投稿日: 2023/02/12(Sun) 15:30
投稿者魔界の仮面弁士
> ただし、発見したすべての組み合わせを列挙するようにしたため、
> アイテム数が多くなると、列挙が開始されるまでに長い時間がかかるようになっています。

No12103「サンプル2」
No12105「サンプル2改」の実装は、
探索が終了するまで、結果が返されない仕様でした。

そこで応答を早くするため、まだ探索を完全に終えていなくても、
条件を満たす組み合わせをひとつ見つけるごとに、随時通知するようにしてみました。

組み合わせが多いと完了まで時間がかかる点は変わりませんが、
結果を表示し始めるまでの応答開始が早くなるというメリットがあります。

さらに、必要に応じて列挙を中断できるよう、キャンセル処理も可能な仕組みを追加してあります。


VB2010 という制限があるため、Iterator / Yield を利用することはできないので、
代わりにデリゲートで通知する方針にしています。(あるいはイベントで通知する方法にしても良いでしょう)

'------------
Option Strict On

Public Class Node
    Inherits List(Of Node)
    Public ReadOnly Value As Tuple(Of Integer, Integer)    '選択された[位置番号]と[値]
    Public ReadOnly Parent As Node      'ひとつ前に選択した[値]
    Public ReadOnly Total As Integer    '祖先からここまでの[値]の合計
    Public Sub New(Parent As Node, Index As Integer, Value As Integer)
        Me.Value = Tuple.Create(Index, Value)
        Me.Parent = Parent
        Total = Value + If(Parent Is Nothing, 0, Parent.Total)
    End Sub
End Class

Module Module1
    ''' <summary>探索された組み合わせの一つを通知するデリゲート。</summary>
    ''' <param name="cancel">既定値は False。True を渡すと列挙が中断される。</param>
    ''' <param name="total">組み合わせの合計数。</param>
    ''' <param name="values">組み合わせの内容。Item1 はインデックス、Item2 が値を示す。</param>
    Public Delegate Sub CombinationReceivedDelegate(ByRef cancel As Boolean, total As Integer, values As Tuple(Of Integer, Integer)())

    Sub Main()
        Dim 値一覧1 As Integer() = {1, 2, 3, 4, 5}
        反復探索(1, 15, 値一覧1) '31通りの組み合わせ

        'No12097 の設問
        Dim 値一覧2 As Integer() = {60, 57, 54, 45, 42, 500, 1000, 60, 25, 57}
        反復探索(570, 590, 値一覧2) '7通りの組み合わせ


        'No.12091 の設問
        Dim 値一覧3 As Integer() = {5988, 2994, 1245, 3296, 19777, 1497, 14823, 13177, 37885, 5988, 6290, 6038, 22653, 28474, 29564, 26871, 23844, 4366, 4101, 14116, 7037, 17500, 24062, 23644, 17717, 25162, 9461, 19788, 29762, 25099, 28935, 1011, 4655, 22234, 9589, 30377, 10081, 2887, 24336, 3517, 16020, 6494, 16745, 24100, 28340, 24825, 13382, 6801, 19893, 28700}
        '反復探索(88792, 88792, 値一覧3)
        '条件を満たす組み合わせがとても多いので、途中でメモリ不足になると思います…。

        Console.ReadKey()
    End Sub


    Sub 反復探索(最小設定値 As Integer, 最大設定値 As Integer, 寸法一覧 As Integer())
        Console.WriteLine("寸法一覧:{0}個", 寸法一覧.Length)
        For i = 0 To 寸法一覧.Length - 1
            Console.WriteLine(" [{0}]={1}", i, 寸法一覧(i))
        Next
        Console.WriteLine()
        Console.WriteLine("設定値:{0}〜{1}", 最小設定値, 最大設定値)

        'Dim limit As Integer = 30  '30件で中断する場合
        Dim progress As CombinationReceivedDelegate =
            Sub(ByRef cancel As Boolean, total As Integer, values As Tuple(Of Integer, Integer)())
                'limit -= 1
                Console.WriteLine("合計値:{0} 詳細値:{1}", total, String.Join(", ", values.OrderBy(Function(x) x.Item1).Select(Function(v) String.Format("[{0}]={1}", v.Item1, v.Item2))))
                'cancel = limit <= 0    '途中で列挙を止めたい場合は True をセットする
            End Sub

        Dim count As Integer = SearchCombinations(progress, 最小設定値, 最大設定値, 寸法一覧)
        If count = 0 Then
            Console.WriteLine("抽出できませんでした。")
        ElseIf count > 0 Then
            Console.WriteLine("総計 {0} 件の組み合わせを抽出しました。", count)
        Else
            Console.WriteLine("抽出処理が中断されました。{0} 件まで抽出されています。", -count)
        End If
        Console.WriteLine()
    End Sub

    ''' <summary>合計値が範囲内となる組み合わせを列挙する</summary>
    ''' <param name="progress">列挙結果を得るためのデリゲート。</param>
    ''' <param name="minValue">探索したい合計値の下限</param>
    ''' <param name="maxValue">探索したい合計値の上限</param>
    ''' <param name="values">値の一覧</param>
    ''' <returns>列挙完了数。列挙が中断された場合は、そこまでの列挙件数×-1 を返す。</returns>
    Public Function SearchCombinations(progress As CombinationReceivedDelegate, minValue As Integer, maxValue As Integer, ParamArray values As Integer()) As Integer
        If minValue > maxValue Then Throw New ArgumentOutOfRangeException("minValue", minValue, "minValue は maxValue 以下である必要があります。")
        If minValue <= 0 Then Throw New ArgumentOutOfRangeException("minValue", "自然数が必要です。")
        If values Is Nothing OrElse values.Length = 0 Then Throw New ArgumentNullException("values")
        If values.Any(Function(v) v <= 0) Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")

        'デリゲートが無ければ列挙しない。
        If progress Is Nothing Then Return 0

        '設定値を超えるものは除外した上で、[値]の昇順に並べる
        Dim ordered = (
            From v In values.Select(Function(value, index) New With {Key index, value})
            Where v.value <= maxValue
            Order By v.value, v.index
        ).ToArray()

        Dim root As New Node(Nothing, -1, 0)

        'Node から値リストを作る
        Dim GetValueArray As Func(Of Node, Tuple(Of Integer, Integer)()) =
            Function(node)
                Dim result As New Stack(Of Tuple(Of Integer, Integer))
                If Not node Is root Then
                    Dim item = node
                    Do
                        result.Push(item.Value)
                        item = item.Parent
                    Loop Until item Is root OrElse item Is Nothing
                End If
                Return result.ToArray()
            End Function

        '探索処理
        Dim maxIndex = ordered.GetUpperBound(0)
        Dim cancel As Boolean = False
        Dim count As Integer = 0
        Dim Search As Action(Of Integer, Node) =
            Sub(index, parent)
                If cancel Then Return
                For i = index To maxIndex
                    Dim nextItem = ordered(i)      '値を昇順に抽出
                    Dim nextNode As New Node(parent, nextItem.index, nextItem.value)
                    If nextNode.Total <= maxValue Then
                        parent.Add(nextNode)        '超過しないなら抽出
                        If minValue <= nextNode.Total Then
                            '最低値条件をクリアした終端を、順次通知する
                            progress.Invoke(cancel, nextNode.Total, GetValueArray(nextNode))
                            count += 1
                            If cancel Then Return
                        End If
                        Search(i + 1, nextNode)     '再帰して次の組み合わせを選ぶ
                    End If
                Next
            End Sub

        '探索実行
        Search(0, root)

        '列挙件数を返す(キャンセルされたときはマイナス値にする)
        Return count * If(cancel, -1, 1)
    End Function
End Module

[ツリー表示へ]
タイトルサンプル2改
記事No12105
投稿日: 2023/02/13(Mon) 13:51
投稿者魔界の仮面弁士
> ただし今回のコードは、 No12091 の「最も近い組み合わせを獲得したい」を優先しており、
> 「最小値を超えたけれど、もっと最大値に近い組み合わせがある」場合、必ずしも列挙されません。
> そのため、すべての組み合わせが得られるわけではありません。
> (それでも一応、当初の目的には合致しているはず…)
>
> Dim 値一覧 = {1, 2, 3, 4, 5}
> result = FindCombinations(1,  5, 値一覧) '1 以上  5 以下の組み合わせ


最小値以上、最大値以下となる「すべての組み合わせ」を返すように変更したもの。


''' <summary>合計値が範囲内となる組み合わせをすべて列挙する</summary>
''' <param name="minValue">探索したい合計値の下限</param>
''' <param name="maxValue">探索したい合計値の上限</param>
''' <param name="values">「Key = 合計値, Value = (Index, 値)の組み合わせ」の一覧</param>
Public Function FindCombinations(minValue As Integer, maxValue As Integer, ParamArray values As Integer()) As SortedDictionary(Of Integer, List(Of Tuple(Of Integer, Integer)()))
    If minValue > maxValue Then Throw New ArgumentOutOfRangeException("minValue", minValue, "minValue は maxValue 以下である必要があります。")
    If values Is Nothing OrElse values.Length = 0 Then Throw New ArgumentNullException("values")
    If values.Any(Function(v) v <= 0) Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")

    '設定値を超えるものは除外した上で、[値]の昇順に並べる
    Dim ordered = (
        From v In values.Select(Function(value, index) New With {Key index, value})
        Where v.value <= maxValue
        Order By v.value, v.index
    ).ToArray()

    Dim root As New Node(Nothing, -1, 0)

    'Node から値リストを作る
    Dim GetValueArray As Func(Of Node, Tuple(Of Integer, Integer)()) =
        Function(node)
            Dim result As New Stack(Of Tuple(Of Integer, Integer))
            Dim item = node
            Do
                result.Push(item.Value)
                item = item.Parent
            Loop Until item Is root OrElse item Is Nothing
            Return result.ToArray()
        End Function

    '探索処理
    Dim maxIndex = ordered.GetUpperBound(0)
    Dim edges As New SortedDictionary(Of Integer, List(Of Tuple(Of Integer, Integer)()))()
    For total = minValue To maxValue
        edges.Add(total, New List(Of Tuple(Of Integer, Integer)()))
    Next
    Dim Search As Action(Of Integer, Node) =
        Sub(index, parent)
            For i = index To maxIndex
                Dim nextItem = ordered(i)       '値を昇順に抽出
                Dim nextNode As New Node(parent, nextItem.index, nextItem.value)
                If nextNode.Total <= maxValue Then
                    parent.Add(nextNode)        '超過しないなら抽出
                    If minValue <= nextNode.Total Then
                        '最低値条件をクリアした終端を登録
                        edges(nextNode.Total).Add(GetValueArray(nextNode))
                    End If
                    Search(i + 1, nextNode)     '再帰して次の組み合わせを選ぶ
                End If
            Next
        End Sub

    '探索実行
    Search(0, root)
    Return edges
End Function

[ツリー表示へ]
タイトルRe: サンプル
記事No12110
投稿日: 2023/02/17(Fri) 08:59
投稿者たけし
御世話になります。

新規作成したプロジェクトにサンプルを記述しまして
結果得ることができました。
こちらに、自分が作成したプログラムを組み込んで
サンプルの結果も得ることができました。

自分が作成したプログラムに
サンプルを組み込むとエラーになる要因想定できますでしょうか?

また、デバック方法がわからないのと
以下プログラムの流れ(順番)について理解できませんでしたので教えてください。
私の知るプログラムはコールしたファンクションで答えを求めて
戻った値について、加算していくなどです。

Search(i + 1, nextNode) から
Search(0, root)に移って
再びSearch(i + 1, nextNode) に戻る(?)のでしょうか?

または
earch(i + 1, nextNode) から
Search(0, root)に移って
If edge Is Nothing Then
            '見つからなかった
            Return New Integer(-1) {}
        Else
            Dim result As New Stack(Of Integer)()
            Dim e = edge
            Do
                result.Push(e.Value)
                e = e.Parent
            Loop Until e Is root
            Return result.ToArray()
        End If
実行後に
再びSearch(i + 1, nextNode) に戻る(?)のでしょうか?


宜しくお願い致します。



'探索処理
        Dim maxIndex = ordered.GetUpperBound(0)
        Dim edge As Node = Nothing  '発見した組み合わせ
        Dim Search As Action(Of Integer, Node) =
            Sub(index, parent)
                If Not edge Is Nothing Then Return  '既に発見済み
                For i = index To maxIndex
                    Dim nextValue = ordered(i)      '値を昇順に抽出
                    Dim nextNode As New Node(parent, nextValue)
                    If nextNode.Total <= targetValue Then
                        parent.Add(nextNode)        '超過しないなら抽出
                        If nextNode.Total = targetValue Then
                            edge = nextNode         '目標値に達したので探索終了
                            Return
                        Else
                            Search(i + 1, nextNode) '再帰して次の組み合わせを選ぶ
                        End If
                    End If
                Next
            End Sub

        '探索実行
        Dim root As New Node(Nothing, 0)
        Search(0, root)
        If edge Is Nothing Then
            '見つからなかった
            Return New Integer(-1) {}
        Else
            Dim result As New Stack(Of Integer)()
            Dim e = edge
            Do
                result.Push(e.Value)
                e = e.Parent
            Loop Until e Is root
            Return result.ToArray()
        End If

[ツリー表示へ]
タイトルRe^2: サンプル
記事No12112
投稿日: 2023/02/18(Sat) 12:21
投稿者魔界の仮面弁士
> 私の知るプログラムはコールしたファンクションで答えを求めて
> 戻った値について、加算していくなどです。
ファンクションの戻り値で返しても良いのですが、それだと下図に相当する枝分かれを
表現しにくいので、今回は戻り値以外の変数に分岐を加えていく方法を採りました。
https://blog-imgs-67-origin.fc2.com/h/a/t/hatenachips/VBASearchSumAlgos.png


> 自分が作成したプログラムに
> サンプルを組み込むとエラーになる要因想定できますでしょうか?
まずはエラーメッセージを読みましょう。
そして、エラー発生時にそれぞれの変数の値が何であったのかを確認しましょう。


> また、デバック方法がわからないのと
デバックではなく
デバッグ(debug)です。

プログラムの不具合のことを bug(バグ) と呼びます。
そのバグを取り除く作業なので、debug(デバッグ) です。

Visual Studio のデバッグ機能について紹介されている記事を貼っておきます。
時間のある時にでも読んでみてください。
https://learn.microsoft.com/ja-jp/visualstudio/debugger/debugging-absolute-beginners?WT.mc_id=DT-MVP-8907&view=vs-2022&tabs=visualbasic

先のコードをデバッグするのであれば、Sub(index, parent) 内の先頭にある
「If Not edge Is Nothing Then」の行にブレークポイントを貼って一時停止してみてください。
その場所からステップ実行を行っていくと、追跡しやすいと思います。

VB のバージョンが古くて、Sub(index, parent) ラムダ式の追跡が難しい場合は、
ラムダ式を使用しない No.12111 のバージョンを試してみるのも良いでしょう。


ついでに、ステップ実行時に分岐内容を見やすくするため、Node クラスに
下記のような DebuggerDisplay 属性を付与しておくと良いでしょう。

一時停止中に、Node 型の変数にマウスカーソルをホバーさせた時や
ローカル ウィンドウやウォッチ ウィンドウなどに表示される変数一覧において、
その Node がどこまでの分岐情報を保持しているのか、目視しやくすなります。
https://vb-user.net/junk/replySamples/2023.02.18.11.21/DebuggerDisplay.png

<DebuggerDisplay("{ToString}")>
Public Class Node
    Inherits List(Of Node)
    Public ReadOnly Value As Integer    '選択された[値]
    Public ReadOnly Parent As Node      'ひとつ前に選択した[値]
    Public ReadOnly Total As Integer    '祖先からここまでの[値]の合計
    Public Sub New(Parent As Node, Value As Integer)
        Me.Value = Value
        Me.Parent = Parent
        Total = Value + If(Parent Is Nothing, 0, Parent.Total)
    End Sub

    Public Overrides Function ToString() As String
        If Value = 0 Then Return "root, (分岐数=" & Count & ")"

        Dim sb As New System.Text.StringBuilder(Value.ToString())
        Dim n = Parent
        Do Until n Is Nothing OrElse n.Value = 0
            sb.Insert(0, n.Value & "+")
            n = n.Parent
        Loop
        Return String.Format("{0}={1}, 分岐数={2}", sb.ToString(), Total, Count)
    End Function
End Class


> Search(i + 1, nextNode) から
> Search(0, root)に移って
> 再びSearch(i + 1, nextNode) に戻る(?)のでしょうか?

元の値リストが { a, b, c } の 3 パターンだった場合で考えてみましょうか。

ここでは、{ 2, 5, 7 } の組み合わせで、目標値「12」を探すものとします。
すなわち
 Dim result = FindCombination(12, 2, 5, 7)
の処理です。

サンプルコードでいうと、
 目標値 = targetValue …… 12
 a = ordered(0) …… 2
 b = ordered(1) …… 5
 c = ordered(2) …… 7
にあたります。ここまでは良いでしょうか。


a, b, c のすべての組み合わせを考える場合、その分岐はこうなります。

root
┣a   終端候補1 … 位置0
┃┣b  終端候補2 … 位置0,1
┃┗c  終端候補3 … 位置0,2
┣b   終端候補4 … 位置1
┃┗c  終端候補5 … 位置1,2
┗c   終端候補6 … 位置2

ただし 6 パターンすべてを試すわけではありません。
合計値が目標値を超えるなら、それ以上探索する意味はありませんし、
目標値に合致する組み合わせを見つけたなら、以降の組み合わせをスキップできるためです。


処理の最初は、ルート階層の呼び出しから始まります。

@【Search(0, root)】を実行します。
A 位置 0 からの探索なので、For i = 0 To 2 のループに入り、root に続く組み合わせを探します。
B  a は 2。これは 12 に満たないので、さらに【Search(1, root/a)】を実行。
C   位置 1 からの探索なので、For i = 1 To 2 のループに入り、root/a に続く組み合わせを探します。
D    a+b は 7。これは 12 に満たないので、さらに【Search(2, root/a/b)】を実行。
E     位置 2 からの探索なので、For i = 2 To 2 のループに入り、root/a/b に続く組み合わせを探します。
F      a+b+c は 14。これは 12 を超えるので打ち切られます。root/a/b/c な組み合わせは生成しません。
G     For ループが終了して End Sub に到達し、【Search(2, root/a/b)】の処理が終わります。
H    a+c は 9。これは 12 に満たないので、さらに【Search(3, root/a/c)】を実行。
I     位置 3 からの探索なので、For i = 3 To 2 のループに入ります。実際は 0 回ループですね。
J     For ループが終了して End Sub に到達し、【Search(3, root/a/c)】の処理を終わります。
K   For ループが終了して End Sub に到達し、【Search(1, root/a)】の処理を終わります。
L  b は 5。これは 12 に満たないので、さらに【Search(2, root/b)】を実行。
M   位置 2 からの探索なので、For i = 2 To 2 のループに入り、root/b に続く組み合わせを探します。
N    b+c は 12。★12 と合致する値を発見★ 終端変数 edge に root/b/c を割り当てて Return します。
O    Return によって終了し、【Search(2, root/b)】の処理を終わります。
P  c は 7。これは 12 に満たないので、さらに【Search(3, root/c)】を実行。
Q   手順Nの時点で edge が確定済みなので、【Search(3, root/c)】が即時終了します。
R For ループが終了して End Sub に到達し、【Search(0, root)】が終了します。
S探索終了。変数 edge に 5+12 な組み合わせが入っているので、それを結果として返します。

[ツリー表示へ]
タイトルサンプル1改
記事No12111
投稿日: 2023/02/18(Sat) 10:10
投稿者魔界の仮面弁士
> 手元に VB2010 が無いので、
> 「VB2022 + .NET Framework 4」のコンソールアプリで作りました。

No12102 のコードを、ローカル関数を使わないバージョンへと書き換えてみました。
処理の流れを追うのであれば、こちらの方がデバッグしやすいでしょう。


環境依存度を減らすため、今回は VB2005 でもコンパイルが通る文法で書いてみました。
(VB.NET 2002/2003 では動きません)

VB2022 + .NET Framework 2.0 での動作検証しかしていないですけれどね。


Option Strict On

Public Class Node
    Inherits List(Of Node)
    Public Value As Integer    '選択された[値]
    Public Parent As Node      'ひとつ前に選択した[値]
    Public Total As Integer    '祖先からここまでの[値]の合計
    Public Sub New(Parent As Node, Value As Integer)
        Me.Value = Value
        Me.Parent = Parent
        If Parent Is Nothing Then
            Total = Value
        Else
            Total = Value + Parent.Total
        End If
    End Sub
End Class

Module Module1
    Sub Main()
        'No12097 の設問
        Dim 値一覧1() As Integer = New Integer() {60, 57, 54, 45, 42, 500, 1000, 60, 25, 57}

        'No.12091 の設問
        Dim 値一覧2() As Integer = New Integer() {5988, 2994, 1245, 3296, 19777, 1497, 14823, 13177, 37885, 5988, 6290, 6038, 22653, 28474, 29564, 26871, 23844, 4366, 4101, 14116, 7037, 17500, 24062, 23644, 17717, 25162, 9461, 19788, 29762, 25099, 28935, 1011, 4655, 22234, 9589, 30377, 10081, 2887, 24336, 3517, 16020, 6494, 16745, 24100, 28340, 24825, 13382, 6801, 19893, 28700}


        '『設定値:590 合計値:587 詳細値:42, 45, 500』
        探索(590, 値一覧1)

        '『設定値:586 合計値:585 詳細値:25, 60, 500』
        探索(586, 値一覧1)

        '『設定値:88792 合計値:88792 詳細値:1011, 1245, 1497, 2887, 2994, 3296, 3517, 4101, 4366, 4655, 6290, 6494, 14116, 14823, 17500』
        探索(88792, 値一覧2)

        Console.ReadKey()
    End Sub

    Sub 探索(設定値 As Integer, 寸法一覧 As Integer())
        Console.Write("設定値:{0} ", 設定値)
        Dim 結果() As Integer = New Integer() {}
        For 設定値 = 設定値 To 設定値 - 20 Step -1
            結果 = FindCombination(設定値, 寸法一覧)
            If 結果.Length > 0 Then Exit For
        Next
        If 結果.Length = 0 Then
            Console.WriteLine("抽出できませんでした。")
        Else
            Dim 合計値 As Integer = Sum(結果)
            Console.Write("合計値:{0} 詳細値:{1}", 合計値, 結果(0))
            For n = 1 To UBound(結果)
                Console.Write(", {0}", 結果(n))
            Next
            Console.WriteLine()
        End If
    End Sub

    Private Function Sum(values() As Integer) As Integer
        Dim total As Integer = 0
        For Each value As Integer In values
            total += value
        Next
        Return total
    End Function

    ''' <summary>探索処理</summary>
    ''' <param name="edge">発見した組み合わせ</param>
    ''' <param name="targetValue">目標値</param>
    ''' <param name="ordered">昇順に並んだ値の一覧</param>
    ''' <param name="index">分岐位置…0 以上 UBound(ordered) 以下</param>
    ''' <param name="parent">ここまでの分岐情報</param>
    Private Sub Search(ByRef edge As Node, targetValue As Integer, ordered() As Integer, index As Integer, parent As Node)
        If Not edge Is Nothing Then Return  '既に最終結果を発見済みなので、もう探索しない
        For i As Integer = index To UBound(ordered)
            Dim nextValue As Integer = ordered(i)
            Dim nextNode As New Node(parent, nextValue)
            If nextNode.Total > targetValue Then
                Return '合計値が目標値を超えたので、この分岐はここで打ち切り
            Else
                parent.Add(nextNode)    '合計値以下なので、分岐を追加
                If nextNode.Total = targetValue Then
                    edge = nextNode     '目標値に達したので、最終結果を edge に渡して終了
                    Return
                End If
            End If
            '再帰して次の組み合わせを選ぶ
            Search(edge, targetValue, ordered, i + 1, nextNode)
        Next
    End Sub

    ''' <summary>合計値が完全一致する組み合わせを探す</summary>
    ''' <param name="targetValue">設定値</param>
    ''' <param name="values">値リスト</param>
    ''' <returns>最初に見つけたものを一つだけ返す</returns>
    Public Function FindCombination(targetValue As Integer, ParamArray values() As Integer) As Integer()
        If values Is Nothing OrElse values.Length = 0 Then Throw New ArgumentNullException("values")
        For Each v As Integer In values
            If v <= 0 Then Throw New ArgumentOutOfRangeException("values", "自然数が必要です。")
        Next

        '[値]の昇順に並べる
        Dim ordered() As Integer = CType(values.Clone(), Integer())
        Array.Sort(ordered)
        '設定値を超えるものは除外
        For n As Integer = 0 To UBound(ordered)
            If ordered(n) > targetValue Then
                ReDim Preserve ordered(n - 1)
            End If
        Next

        '探索処理
        Dim maxIndex As Integer = UBound(ordered)
        Dim edge As Node = Nothing  '発見した組み合わせ

        '探索実行
        Dim root As New Node(Nothing, 0)
        Search(edge, targetValue, ordered, 0, root) 'これが処理の本体
        'root は、抽出した分岐の組み合わせが入っており
        'edge には、合計値が合致したその分岐の末端部が入っている

        '分岐の末端である edge を親方向に辿って、抽出結果として返す
        If edge Is Nothing Then
            '見つからなかった
            Return New Integer(-1) {}
        Else
            Dim result As New List(Of Integer)()
            Dim n As Node = edge
            Do
                result.Insert(0, n.Value)
                n = n.Parent
            Loop Until n Is root
            Return result.ToArray()
        End If
    End Function
End Module

[ツリー表示へ]