値によって組み分けを作成するプログラムについて

質問

こんにちは。
プログラミングでつまってしまったため質問させて頂きます。
プログラミング言語はC++です(visual c++ではありません)。

■作成したいプログラム
A,B,C,D,Eがある。

AとBの類似度は91%
以下同様に
AとCは89%
AとDは79%
AとEは77%
BとCは93%
BとDは97%
・・・のように続いていく..
(*ABが似ている、BCが似ている。だからと言ってACが似ているとは言えない。)

この中で、類似度が閾値以上である場合は同じ組とする。
ただし、複数のパターンが考えられる場合は組の数が一番すくなくなるように作る。

■プログラムの動作イメージ
例1：
閾値=0.90

//入力データ
01 = 0.91; OK
02 = 0.90; OK
03 = 0.78; NG
04 = 0.83; NG
12 = 0.94; OK
13 = 0.78; NG
14 = 0.77; NG
23 = 0.78; NG
24 = 0.69; NG
34 = 0.94; OK

OKなのは,01,02,12,34
つまり以下のような出力が得られる
>>0,1,2
>>3,4

---------------------------------------
例2：
閾値=0.90

//入力データ
01 = 0.91; OK
02 = 0.90; OK
03 = 0.94; OK
04 = 0.83; NG
12 = 0.95; OK
13 = 0.78; NG
14 = 0.77; NG
23 = 0.78; NG
24 = 0.69; NG
34 = 0.94; OK

OKなのは,01,02,03,12,34
つまり
0,1,2
3,4
or
0,3
1,2
4
となった場合は、組数の少ない上を選択する。
従って以下のような出力が得られる。
>>0,1,2
>>3,4

---------------------------------------
例3：
閾値=0.90

//入力データ
01 = 0.91; OK
02 = 0.90; OK
03 = 0.78; NG
04 = 0.83; NG
12 = 0.77; NG
13 = 0.78; NG
14 = 0.77; NG
23 = 0.78; NG
24 = 0.69; NG
34 = 0.94; OK

OKなのは,01,02,34
この場合は、01と02は閾値を超えているが、12は閾値を超えていないため、
0,1,2を同じ組とはできない。
従って以下の２パターンが考えられる。
0,1
2
3,4
or
0,2
1
3,4
この場合は組の数は同じなのでどちらが出力されてもOK。
番号の若いものから出力されるとすると以下のような出力が得られる。
>>0,1
>>2
>>3,4
------------------------------------------------------

以上のようなプログラムを作成したいです。

自分で考えてみたのプログラムが以下のものです。
01,02,12,34は閾値を超えているということまではできたのですが、その後のグループの作り方のところで詰まってしまいました。
そこで、上記のような動作をするプログラムについて教えていただきたいです。
よろしくお願い致します。

int main(){
//閾値
double THRESHOLD = 0.9;
//dataを格納する配列
double in_data[5][5] = {0};
//group_flagを格納する配列
bool group_flag[5][5] = {0};

in_data[0][1] = 0.91;
in_data[0][2] = 0.90;
in_data[0][3] = 0.78;
in_data[0][4] = 0.83;
in_data[1][2] = 0.94;
in_data[1][3] = 0.78;
in_data[1][4] = 0.77;
in_data[2][3] = 0.78;
in_data[2][4] = 0.69;
in_data[3][4] = 0.94;

//組の番号を格納する配列　　　
//group[3]=2だったら、データ３はグループ２に入る
int group[5];

int i=5; //データ数
int num=0;
for(int n=0; n<=i; n++){
for(int m=n+1; m<i ;m++){
cout << "in_data[" << n << "][" << m << "]=" << in_data[n][m] << endl;
if(in_data[n][m] >= THRESHOLD){
cout << "OK" << endl;
group_flag[n][m] = 1;
}
}
}

for(int n=0; n<=i; n++){
for(int m=n+1; m<i ;m++){
if(group_flag[n][m] == 1){
cout << n << m <<endl;
}
}
}
}

回答No.1

akayoroshi · ベストアンサー

データは5個だけでしょうか
5個をグループ分けする組み合わせの数は
5個全部が1グループになる:1通り
4個と1個の2グループになる:5通り
3個と2個の2グループになる:5C2=10通り
2個と2個と1個の3グループになる:5C2x3C2=30通り
2個と1個と1個と1個の4グループになる:10通り
1個ずつ5グループになる:1通り
合わせて57通りですね
それほど多くないので、グループ数の少ないほうからすべての組み合わせについて当てはまるかどうかを検査すればよいのではないでしょうか。

お礼

データ数が５つの場合はif文で処理することでできました！
場合の数は５７通りとはなりませんでしたが、おそらく見落としはないと思います。
ありがとうございます。
もし、データ数を柔軟に変更することが可能な手法がありましたら引き続きご教授ください。
よろしくお願い致します。

//1グループ
ABCDE
//２グループ
//AB,CDE
//AC,BDE
//AD,BCE
//AE,BCD
//BC,ADE
//BD,ACE
//BE,ACD
//CD,ABE
//CE,ABD
//DE,ABC

//3グループ
//AB,CD,E
//AB,CE,D
//AB,DE,C
//AC,BD,E
//AC,BE,D
//AC,DE,B
//AD,BC,E
//AD,BE,C
//AD,CE,B
//AE,BC,D
//AE,BD,C
//AE,CD,B
//BC,DE,A
//BD,CE,A
//BE,CD,A
//CD,BE,A
//CE,BD,A
//DE,BC,A

//4グループ
//AB,C,D,E
//AC,B,D,E
//AD,B,C,E
//AE,B,C,D
//BC,A,D,E
//BD,A,C,E
//BE,A,C,D
//CD,A,B,E
//CE,A,B,D
//DE,A,B,C

//5グループ
//A,B,C,D,E

補足

回答ありがとうございます。
データ数は初めは５つで考えております。
成功したら７つに増やす予定ですが。

なるほど、全ての場合分けをグループ数の少ない順にやっていき、当てはまった時点でループを終了させてしまうという事ですね。
プログラムをうまく書けるかわかりませんが、今からその方法で考えてみます。

しかし、データ数を柔軟に変更することが難しそうですので、その他の手法などがありましたらご教授ください。
よろしくお願いします。

回答No.5

nag0720

＃１さんの方法は５個の振り分け方の数ですが、５個中４個だけしか選ばれない場合もあるので、
４個、３個、２個の場合の振り分け方も必要になります。

それはそれとして、
この質問は言語は違いますが少し前の質問に似ています。

http://okwave.jp/qa/q7621154.html

このときの質問は、どの２つを選んでもOKとなる組み合わせを求める質問でした。

今回の例で言えば、
例1：01,02,12,34　は、
0,1,2
3,4

例2：01,02,03,12,34　は、
0,1,2
0,3
3,4

例3：01,02,34　は、
0,1
0,2
3,4

という組み合わせを求めるアルゴリズムです。

ここまでできればあとは重複している数字があったとき、どちらを選ぶかだけの問題になります。

例1は重複している数字がないので、そのまま。
例2は重複している数字は0と3ですが、0,1,2と3,4のほうを選べば0,3の組が消えます。
例3は重複している数字は0だけですが、どっちを選んでも同じ。

そのロジックはそんなに難しくはないでしょう。

お礼

ありがとうございます。
このようなものがあるのですね。
いま行なっている手法が終わりましたら、こちらの方でもコーディングしてみたいと思います。

回答No.4

akayoroshi

3個と1個と1個の3グループになる:5C2=10通り
が抜けていました。#3の42通りと合わせて52通りになります。

回答No.3

akayoroshi

組み合わせの数を間違えていました
誤:2個と2個と1個の3グループになる:5C2x3C2=30通り
正:2個と2個と1個の3グループになる:5C2x3C2/2!=15通り
合計は42通りでしょうか。
ところで、
#1のお礼の場合分けには
4個と1個の2グループになる:5通り
が抜けているようです。
〉 データ数を柔軟に変更することが可能な手法がありましたら引き続きご教授ください。
グループ分けの組み合わせを作り出してそれに適合するかどうかを検査するプログラムが作れるのではありませんか。

お礼

ありがとうございます。
みなさんのご指摘の通り52通りとなりました。

＞グループ分けの組み合わせを作り出してそれに適合するかどうかを検査するプログラムが
作れるのではありませんか。
なるほど。ただ、７つの時は量が多くなりそうで大変かなと。
その手法でやってみたいと思います。
ありがとうございました。

回答No.2

Tacosan

5つの場合だと「源氏香」と同じなので合計 52通りになるはずです. #1 は 3グループにわかれるときの計算を間違えてます (数えわすれと数え過ぎの両方がある).

で, 各グループに対し「そのグループに入っているデータ (A とか B とか)」を覚えておくと「そのグループに入れていいかどうか」の判定が簡単になるはず.

一般には彩色問題ですね.

お礼

源氏香というものを初めて聞きました。
こういうものがあるのですね、面白かったです。