[ツリー表示へ] [ワード検索] [Home]
タイトル ： Re^5: 組み合わせ合計探索 投稿日 ： 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 を４回 57 = 15 を２回と 27 を１回 54 = 27 を２回 45 = 15 を３回 42 = 15 を１回と 27 を１回 の 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 > 効率の良いものではなかったので > 相談させていただいています。 効率はさておき、解は導き出せたわけですよね。それはどんな処理でしたか? 具体的なコードの提示が難しければ、ロジックの説明だけでもお願いします。 その時のロジックよりも効率の悪いものを提示しても意味が無い（徒労になる）ので。 また、「メモリ効率」「速度効率」「保守効率(汎用性/移植性/理解の容易度)」などを すべて満たすことはできませんから、この逆質問によって、どのあたりを落としどころに したいと考えているのかを探るという目的もあります。 |
をクリックするとツリー全体を一括表示します） - 組み合わせ合計探索 - たけし 23/02/07-20:51No.12091