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

質問

次のような問題を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.21

bunjii

>参考にさせて頂きます。
言葉のキャッチボールが上手くできていないようです。
元データの数列（要素数が不定の整数値配列）を何処から持ってくるのかを補足して頂くこととグループの数（与えられた個数の群）をどのように定義するかを補足頂けないと一般化の可否が考え難いと言ったつもりです。
回答No.11のお礼にある下記の関数のコードが今回の質問の趣旨のように推測しました。
void GetOptimalCombination(int* pSrc, int nSize, int nBlock, int** ppResult);
従って、元データの数列とグループ数の組み合わせを数例提示して頂けるよう申し上げました。
別解（C言語以外での処理）の方法で対処することになったのであれば質問を締め切ってください。

回答No.20

bunjii

>任意のグループ数に対応出来ますか？
要素数とグループの数によってはループの多重化に限界があると思います。
グループ数が4以上になるとパターン数の計算にも工夫が増えますので専門のプログラマーに委託された方が良いでしょう。
パターン毎のグループ合計を配列変数に保存してすべての計算が済んでから組み合わせの判定をすれば良いでしょう。

>再帰を使うようなイメージだったのですが。
私はプログラマーではありませんので詳しいことは分かりませんが再帰を多重化したときにループから抜け出せなくなることもあるようですから方法論を良く検討してください。

>I/Fのイメージとしてはこんな感じです。
前述のようにプログラマーではないので提示の関数（サブルーチン）については理解できません。
何れにしてもmain()から関数へ条件を渡して戻り値で要素の配列とグループ数を得ると解釈します。
要素の配列とグループ数の模擬データを数組提示して頂ければ暇を見ながら考えたいと思います。（解決は難しいかも知れません）

お礼

ご回答ありがとうございました。参考にさせて頂きます。

回答No.19

amanojaku1

>回答No.18　amanojaku1

ただし、デメリットもあります。
x64で「int_fast32_t」と定義した場合(8 バイト：64 ビット)と、386(32bit)で「int_fast32_t」と定義した場合(4 バイト：32 ビット)では、ザイズが変わってしまいます。
4 バイト (32 ビット)で符号付き整数値の範囲は「－2,147,483,648～2,147,483,647」
8 バイト (64 ビット)で符号付き整数値の範囲は「-9,223,372,036,854,775,808～9,223,372,036,854,775,807」
例えば、ビット演算でNOTを使ったりすると明確に違う値になります(当然、それ以外でも明確に違う値になる場合はあるでしょう)。

(「x64、386(32bit)」の両対応にしたい場合で)これが問題になる場合は基本的に「int_fast～_t」は使わないほうが良いでしょうが、どうしても必要な場合はプログラマーが それに対応できるプログラムを作る必要があります。

お礼

ご回答ありがとうございました。参考にさせて頂きます。

回答No.18

amanojaku1

>回答No.17　amanojaku1

x64で「int_fast32_t」と定義しても、32bit演算にはならないと言う事に注意して下さい。
32bit以上のbit数が保障され、そのCPUの最速のbit数になります(x64なら64bit)。

回答No.17

amanojaku1

>回答No.16　amanojaku1

組み込みにおけるCプログラムの速度最適化
https://qiita.com/YankeeDeltaBravo225/items/274b92735fbafc060a75

>32bit CPUを使う前提で書きます。
>基本的に32bit CPUは32bit演算しかできません。
>(64bit演算もできるものはあったりしますが)
>では8bit,16bit変数の演算はどうなるかと言うと、
>32bitで演算した結果に対して0xFF (8bit) / 0xFFFF (16bit)の
>ビットマスクを掛けるので、その分遅くなります。

↑これは32bit CPUの話ですが、恐らく64bit CPUでも「32bit、16bit、8bit」演算ではマスク処理が入り遅くなると予想されます。

回答No.16

amanojaku1

>回答No.15　amanojaku1

x64だけで良いなら「int_fast64_t」で定義すれば良いですし、i386(32bit)も視野に入れたいなら「int_fast32_t」で定義しておけばi386(32bit)でコンパイルした時に極端に遅くなったりはしないと思われます(ただしi386(32bit)はレジスターが少ないのでレジスターによる最適化の恩恵は あんまり受けられないと思われますが…)

回答No.15

amanojaku1

>回答No.14　amanojaku1

最も速い数値型
http://cpp.aquariuscode.com/int_fast_t

>今やどこを見ても64bitCPUで溢れています。
>にも関わらず、多くの環境でintは4byteのままです。
>今の時代で引数に盲目的にintを指定することは、環境の変化に対応しきれていない可能性があります。
>幸いにも、どの環境でもなるべく高効率になる数値型を標準が用意してくれています。

>fastの後ろの数値が最低限保証するbit精度です。
>例えばuint_fast8_tは「最低でも8bitの精度が保証された中で最速のデータ幅」を持つ符号無し整数を表します。

回答No.14

amanojaku1

>>ただJavaScriptだと群の数が増えると急激に重くなりますね。Cに移植すれば高速になるでしょうか。

>コンパイラーなら問題ないと思いますよ。

x64の方がレジスターが多いので、x64で(最適化を有効にし)コンパイルすると良いらしいです。

コンパイラの最適化についてすべてのプログラマが知っておくべきこと (第 2 部)
https://msdn.microsoft.com/ja-jp/magazine/dn973015.aspx

>レジスタ割り当て
>レジスタ割り当てとは、変数用にメモリを確保する必要をなくし、使用可能なレジスタに一連の変数を割り当てるプロセスです。このプロセスは通常、1 つの関数全体のレベルで実行されます。ただし、リンク時のコード生成 (/LTCG) が有効になっている場合は特に、複数の関数にまたがってこのプロセスを実行して、さらに効率の高い割り当てが可能になる場合があります (ここでは、特に記載がない限り、変数はすべて自動変数、つまり構文上有効期間が決まる変数です)。
>
>レジスタ割り当ては、特に重要な最適化です。これを理解するために、さまざまなレベルのメモリへのアクセスにかかる時間を確認します。レジスタへのアクセスにかかる時間は 1 プロセッサ サイクル未満です。キャッシュへのアクセスは少し時間がかかり、数サイクル～数十サイクルです。(リモート) DRAM メモリへのアクセスはそれよりもずっと時間がかかります。さらに、ハード ドライブへのアクセスは非常に遅く、数百万サイクルかかります。また、メモリ アクセスによって共有キャッシュやメイン メモリとのトラフィックが増加します。レジスタ割り当てを行い、使用可能なレジスタをできる限り活用することで、メモリへのアクセス回数が減少します。
>
>コンパイラは各変数のレジスタへの割り当てを試みます。その変数が関係するすべての命令が実行されるまで、変数がレジスタに割り当たったままの状態が理想です。後ほど簡単に説明する理由からよく起こることですが、割り当て状態を維持できないと、1 つ以上の変数がメモリに吐き出され、読み込みと書き込みが頻繁に行われることになります。レジスタ負荷とは、レジスタの使用を維持できないために変数がメモリに吐き出されたレジスタの数を表します。レジスタ負荷が大きいほどメモリのアクセス回数が多くなり、メモリのアクセス回数が増えるとプログラム自体が遅くなるだけでなく、システム全体の処理速度が低下する可能性があります。
>
>最新の x86 プロセッサには、コンパイラが割り当てることができるレジスタとして、8 個の 32 ビット汎用レジスタ、8 個の 80 ビット浮動小数点レジスタ、および 8 個の 128 ビット ベクター レジスタがあります。すべての x64 プロセッサに、16 個の 64 ビット汎用レジスタ、8 個の 80 ビット浮動小数点レジスタ、および最低 16 個の (128 ビット幅以上の) ベクター レジスタがあります。最新の 32 ビット ARM プロセッサには、15 個の 32 ビット汎用レジスタと 32 個の 64 ビット浮動小数点レジスタがあります。すべての 64 ビット ARM プロセッサには、31 個の 64 ビット汎用レジスタ、32 個の 128 ビット浮動小数点レジスタ、および 16 個の 128 ビット ベクター レジスタ (NEON) があります。これらのレジスタはすべて、レジスタ割り当てに使用できます (また、グラフィック カードに用意されているレジスタもこの一覧に加えることができます)。使用可能なレジスタのどれにもローカル変数を割り当てられない場合、その変数はスタック上に割り当てられます。

回答No.13

amanojaku1

>ただJavaScriptだと群の数が増えると急激に重くなりますね。Cに移植すれば高速になるでしょうか。

コンパイラーなら問題ないと思いますよ。

お礼

C++に移植したところ、性能はかなり改善しました。実用的には十分です。
ところで、提示頂いたプログラムですが、簡単なコメントを入れて頂くことは出来ますでしょうか？各変数の意味、ブロック単位の処理内容、while文を抜ける条件などが書いてあれば処理の流れを理解出来ると思います。

回答No.12

amanojaku1

>回答No.10　amanojaku1

ほんのチョッピリ(処理的に)スマートになりました。
デバッグ用の表示も分かりやすく変更してます。

>群の数をＮに一般化出来るでしょうか？

「gp」に群の数を代入して下さい。
下記はJavaScriptです(「gp = 4」にしています)

<head>
<meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS">
<!-- charset=Shift-JIS、UTF-8 -->
<TITLE>test</TITLE>
</head>
<body>

<script type="text/javascript">
<!--

gpa = [5,2,7,12,6,15,4];
gp = 4;

gmq = Array(gp).fill(1);
gmp = Array(gp).fill(0);

gmmin = -1;
gmmax = -1;
gmmdif = -1;
gtmin = -1;
gtmax = -1;
gtmdif = -1;
gppc = 0;
// gtmp, gtmq, gppc
while(0<gmq[gp-1]){
gppc++;
// gmq[2] = gpa.length-(gmq[0]+gmq[1]);
gmq[gp-1] = gpa.length
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
gmt = Array(gp).fill(0);
gmc = 0;
pc = 1;
for(let i = 0; i<gpa.length; i++){
if(pc<gmp.length){
if(gmp[pc]==i){
pc++;
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gmt='+gmt+'<br>');
gmm = gmt.slice().sort((a, b) => a-b);
gmmin = gmm[0];
gmmax = gmm[gmm.length-1];
gmmdif = gmmax-gmmin;
document.write(
'gmmin='+gmmin+'; '+
'gmmax='+gmmax+'; '+
'gmmdif='+gmmdif+'; '+
'<br>');
if((gtmdif<0)||(gtmdif>gmmdif)){
gtmdif = gmmdif;
gtmin = gmmin;
gtmax = gmmax;
gtmq = gmq.slice();
gtmp = gmp.slice();
}
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
document.write('<br>');
for(let k = 0; k<(gmq.length-1); k++){
gmq[k]++;
for(let i = 0; i<k; i++){
gmq[i] = 1;
}
gmq[gp-1] = gpa.length
document.write(
'k='+k+'; '+
'gmq[k]='+gmq[k]+'; '+
'<br>');
p = 0;
for(let i = 0; i<(gmq.length-1); i++){
gmq[gp-1] -= gmq[i];
p += gmq[i];
gmp[i+1] = p;
}
document.write('gmq='+gmq+'<br>');
if(0<gmq[gp-1]){
break;
}
}
document.write('<br>');
}

document.write('<br>');
document.write("<< Answer >>"+'<br>');
gppc
document.write('PatternCounter='+gppc+'<br>');
gmp = gtmp;
gmt = Array(gp).fill(0);
gmc = 0;
for(let i = 0; i<gpa.length; i++){
for(let j = 1; j<gmp.length; j++){
if(gmp[j]==i){
document.write(' | ');
gmc++;
}
}
gmt[gmc] = gmt[gmc]+gpa[i];
document.write(gpa[i]+',');
}
document.write('<br>');
document.write('gmt='+gmt+'<br>');
document.write(
'gtmin='+gtmin+'; '+
'gtmax='+gtmax+'; '+
'gtmdif='+gtmdif+'; '+
'<br>');
// -->
</script>

</body>
</html>

お礼

素晴らしいです。意外とシンプルに書けるものなんですね。
ただJavaScriptだと群の数が増えると急激に重くなりますね。Cに移植すれば高速になるでしょうか。