数値を複数の群に分ける最適な組み合わせを求める方法

質問

次のような問題をCで記述するにはどのようにすればいいでしょうか？

要素数が不定の整数値配列がある。
この配列の各要素を、与えられた個数の群に分ける。
条件として、与えられた数値列で隣り合う数値しか同じ群に含めることは出来ない。

例：
数値列は{5,2,7,12,6,15,4}
群の個数を3とする。

(1) {5,2},{7,12,6},{15,4}
(2) {5},{2,7},{12,6,15,4}
(3) {5,2,7},{12},{6,15,4}
・・・

と複数の組み合わせがある。
これらの組み合わせのうち、各群の合計値が最も均等になるような組み合わせを求める。最大値と最小値の差が最小となる組み合わせを最も均等と考える。

上の例であれば、各群の合計値と、合計値の最大値と最小値の差は、

(1) {5,2},{7,12,6},{15,4} ==> 7,25,19 (25-7=18)
(2) {5},{2,7},{12,6,15,4} ==> 5,9,37 (37-5=32)
(3) {5,2,7},{12},{6,15,4} ==> 14,12,25 (25-12=13) ☆

のようになり、この３つの中で最も均等なのは

(3) {5,2,7}{12}{6,15,4}

となる。
実際は、これ以外の組み合わせでより均等となるものがあるかと思います。

この問題そのものが必要なわけではなく、この結果を利用して別のある問題を解決しようとしています。

数値の数が増えると組み合わせの数も大幅に増えて計算時間に影響すると思います。
全ての組み合わせを試すことなく答えにたどり着く方法があれば、考え方だけでも提示頂ければと思います。

回答No.27

amanojaku1 · ベストアンサー

>回答No.23　amanojaku1

「2018/06/15 03:48:47」の時点で修正しました。
それ以前にコピーしている場合は注意して下さい。

数値を複数の群に分ける最適な組み合わせを求める方法
http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&

お礼

コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。

それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。

回答No.72

amanojaku1

>回答No.71　amanojaku1

もし最大値最小値を条件付分岐なしに記述できると微妙にパフォーマンスが良くなる可能性があります(あくまで可能性ですが)。
最大値最小値に条件付分岐自体がなければ、そこ(最大値最小値)でパイプラインのStall(ストール：停止状態)が発生することもない訳です。

回答No.71

amanojaku1

「(int)(0==0)」は「1」になると言うのは言語仕様ですか？(どんなC++でも共通ですか？)

下記は可能ですか？、bは「18446744073709551615」になりますか？

long long a = (long long)(0!=0);
unsigned long long b = _UI64_MAX;
a = (a & 1)-1;
b = (unsigned long long)a & b;

下記は可能ですか？、bは「9223372036854775807」になりますか？

long long a = (long long)(0!=0);
long long b = _I64_MAX;
a = (a & 1)-1;
b = a & b;

回答No.70

amanojaku1

下記は可能ですか？、bは「18446744073709551615」になりますか？

long long a = 0!=0;
unsigned long long b = _UI64_MAX;
a = (a & 1)-1;
b = a & b;

下記は可能ですか？、bは「9223372036854775807」になりますか？

long long a = 0!=0;
long long b = _I64_MAX;
a = (a & 1)-1;
b = a & b;

回答No.69

amanojaku1

>回答No.67　amanojaku1

セミコロンが全角になってました。

下記は可能ですか？、bは「18446744073709551615」になりますか？

long long a = 0==0;
unsigned long long b = _UI64_MAX;
b = a&b;

下記は可能ですか？、bは「18446744073709551615」になりますか？

unsigned long long a = 0==0;
unsigned long long b = _UI64_MAX;
b = a&b;

下記は可能ですか？、bは「9223372036854775807」になりますか？

long long a = 0==0;
long long b = _I64_MAX;
b = a&b;

回答No.68

amanojaku1

>回答No.45

>ULLONG* gmp = new ULLONG[gp];
>fill(gmp, gmp + gp, 0);

↑少々疑問なんですが「ULLONG* gmp = new ULLONG[gp];」だけで、gmpはゼロ・クリアされないですか？

お礼

C++はそういう言語仕様です。
Javaなら０で初期化されます。

回答No.67

amanojaku1

>回答No.66　amanojaku1

>signed long long a = 0==0;
>
>↑例えばこれで「-1」になりませんか？
>そうすれば最大値最小値を条件付分岐なしに記述できると思いますが。

long long a = 0==0;

↑例えばこれで「-1」になりませんか？

unsigned long long b = 0==0;

↑例えばこれで「18446744073709551615」になりませんか？

下記は可能ですか？、bは「18446744073709551615」になりますか？

long long a = 0==0；
unsigned long long b = _UI64_MAX；
b = a&b;

下記は可能ですか？、bは「18446744073709551615」になりますか？

unsigned long long a = 0==0;
unsigned long long b = _UI64_MAX；
b = a&b;

下記は可能ですか？、bは「9223372036854775807」になりますか？

long long a = 0==0；
long long b = _I64_MAX；
b = a&b;

お礼

私の環境では全て１になります。bool型のtrueが全ビット１になるような言語や処理系があるのでしょうか？

回答No.66

amanojaku1

>これは特定のコンパイラでしか使えないpragmaですね。そもそもpragmaは言語仕様ではなく、コンパイラ固有のオプションのようなものですね。
>私の環境ではこのpragmaは使えませんでした。

駄目でしたか。

>最大値最小値を条件付分岐なしに記述できると良いのですが。

signed long long a = 0==0;

↑例えばこれで「-1」になりませんか？
そうすれば最大値最小値を条件付分岐なしに記述できると思いますが。

お礼

これは１になりますね。C言語ではbool型は１バイトで内部表現はtrueが0x01、falseが0x00となります。
trueを0xffで表現するような自前のbool型を開発すれば、期待されている処理も可能かもしれませんが。
プリミティブ型のオーバーロード(?)は出来ないと思います。

回答No.65

amanojaku1

>分岐予測が外れStall(ストール：停止状態)が発生すると言うのはベルトコンベア上の"命令"の破棄です。

例えばパイプラインが15ステージだとすると、分岐予測が外れStall(ストール：停止状態)が発生すると、ベルトコンベア上の14個の"命令"が破棄されます。

回答No.64

amanojaku1

>ザックリと言うとCPUのパイプラインとはベルトコンベアのように"命令"を流れ作業で処理するとイメージして下さい。
>分岐予測が外れStall(ストール：停止状態)が発生すると言うのはベルトコンベア上の"命令"の破棄です。
>一番単純なパイプラインは3ステージです「フェッチ、デコード、実行」、実際のパイプラインは おおよそ10～20ステージ程度です。

製品の製造とはチョット違うのですが、下記のようなベルトコンベアをイメージすると分かりやすいでしょう。

回答No.63

amanojaku1

>分岐予測が外れたら(CPUの)パイプラインのStall(ストール：停止状態)が発生します。

ザックリと言うとCPUのパイプラインとはベルトコンベアのように"命令"を流れ作業で処理するとイメージして下さい。
分岐予測が外れStall(ストール：停止状態)が発生すると言うのはベルトコンベア上の"命令"の破棄です。
一番単純なパイプラインは3ステージです「フェッチ、デコード、実行」、実際のパイプラインは おおよそ10～20ステージ程度です。
Stall(ストール：停止状態)して10～20もパイプラインの"命令"が破棄されると言うのは、できるだけ避けるべきでしょう。