データの値の近いものをグルーピングする方法について

質問

以下アルゴリズムについて考えております。

複数のデータの内、差が±1以内のものをグループ分けする。
ただし、複数の候補がある場合は値の近い方をグループとする。
また、差がまったく同じであった場合は番号の若いほうのグループとする。

例１
・入力
data1=1
data2=1.5
data3=2
data4=5
data5=6
・出力
グループ１：1,2,3
グループ2：4,5

例2
・入力
data1=1
data2=1.3
data3=2.3
data4=5
data5=6
・出力
グループ１：1,2
グループ3：3
グループ2：4,5

例3
・入力
data1=1
data2=2
data3=3
data4=4
data5=6
・出力
グループ１：1,2
グループ2：3,4
グループ3：5

このような結果が得られるプログラムを作成中です。
簡単なグループ分けならできるのですが、候補が複数でてきてしまう場合におかしく
なってしまいます。
以下に書いてあるものが初めに思いついた方法の概要です。
このプログラムでは適切なグループ分けが出来ませんでした。
現在はデータの差が±１以内ならばフラグを立てて後でグループ分けをするといった
方法でやっておりますがどうも上手くいきません。

そのため、今回のプログラムについて教えて頂きたく質問をさせて頂きました。
よろしくお願いします。

以下、初めに思いついた方法の概要です。

double in_data[] //データの値
double data[][] //データの差
group[]//グループ番号　　　　//例えばgroup[3]=2だったら、データ３はグループ２に入る

//data1-data2
//data1-data3
//・・・
//と計算をしていくforループ

for(n=0; n<=i; n++){
　　for(m=n+1; m<i ;m++){
　　　　data[n][m]=fabs(in_data[n]-in_data[m]);
　　　　if(data[n][m]<=1){
　　　　　　group[n]= num;　　//グループ番号振り分け
　　　　　　group[m]= num;
　　　　　　num++;
　　　　}
　　}
}

回答No.4

yuu_x · ベストアンサー

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

typedef struct {
unsigned int no;
double value;
} Data;

int cmp (const void* a, const void* b) { return (int)ceil(((Data*)a)->value - ((Data*)b)->value); }

int main(int argc, char* argv[])
{
Data data[] = {{1, 1},{2, 1.3},{3, 2.3},{4, 5},{5, 6}};
int n = sizeof(data) / sizeof(*data);
Data *group[n * 2];
int i, j;
double min;

memset(group, NULL, n * 2 * sizeof(Data*));

qsort(data, n, sizeof(*data), cmp);

group[0] = &data[0];
min = data[0].value + 1;
for (i=1, j=1; i<n; i++, j++) {
if (data[i].value > min) {
min = data[i].value + 1;
j ++;
}
group[j] = &data[i];
}

for (i=0; i<n*2; i++) {
if (group[i] == NULL) {
printf("\n");
if (group[i+1] == NULL) break;
} else {
printf("%d, ", group[i]->no);
}
}
return 0;
}

お礼

#include "string.h"
を追加したところ問題なく動きました。
ありがとうございました。

回答No.5

yuu_x

int n = sizeof(data) / sizeof(*data); → const int n ...

回答No.3

himajin100000

>セグメンテーション違反
なんとなくそんな気がした。俺、識者に怒られるんだろうなあ。

>data1 = 1
>data2 = 2
>data3 = 3

>グループ１：data1,data2
>グループ２：data3

data1とdata2が同じグループ data1
data2とdata3が同じグループ
よって
data1とdata2とdata3が同じグループ

…にならないってことは、そういう仮定をおかないといけないんだろうなぁ、って思って敢えてそのへん聞かずに放置して回答してたんだ。

補足

度々すみません。
セグメンテーション違反は私のミスでした、申し訳ありません。
補足を書いてから分かったことなので編集できませんでした。
このように書き換えたところ正常に動きました。ありがとうございました。
現在はソートされていない状態でも動くように考えております。
何かよい方法があったら御教授ください。
よろしくお願いします。

double in_data[5];
in_data[0] = 0;
in_data[1] = 1.2;
in_data[2] = 1.5;
in_data[3] = 3;
in_data[4] = 4;
vector< double > data;
for(int i=0;i<5;i++){
data.push_back(in_data[i]);
}

回答No.2

noname#137556

> 複数のデータの内、差が±1以内のものをグループ分けする。
> ただし、複数の候補がある場合は値の近い方をグループとする。
> また、差がまったく同じであった場合は番号の若いほうのグループとする。

「値が近い」とか，「差が全く同じ」というのは，
　隣接する要素についてなのか，
　グループ内の最大値と最小値についてなのか，
どちらでしょうか？

補足

例えば
data1=2,data2=3,data3=4
とあった場合に
data2から見て±1以内であるものはdata1,3があるということです。
その場合は
グループ１：data1,data2
グループ２：data3
となる結果が得たいです。
よろしくお願いします。

回答No.1

himajin100000

質問文が難しい条件で述べられているように見えるだけ。

数値はソートされているものとする。

「低い方を見たときに条件に一致している場合は、その低い方を基準としたグループに既に含まれている」から
「高い方と低い方の両方を見る必要はない」

http://ideone.com/vG2y6

#元々C#で書いたものを慣れていないC++に移植したが、問題あるかも。(初期化子が書けるかどうかとか詳しいことは知らん)
#表示されている数値が1ずつ少ないのは、添字が0から始まっているから

補足

ありがとうございます。
動かして見たところセグメンテーション違反が出ました。
もう少し考えてみます。
また、数値がソートされているとは限りませんので、そのソート
方法についても考えてみたいと思います。