グループ分けを行うプログラムを考えています.
具体的には,

A,B,C,D,Eがあったとき,
A-B,A-C,B-Dが1つのグループ(ペア)であれば,
A-B-C-Dを1つのグループ(群)とする.

このようなルールのもとで,グループ分けをおこないたいのですが,
どのようにしたらよいものかいい考えが浮かんできません.

なお,元データはそれぞれのペアが1行に1つずつあります.

A B
A C
B C
B D
: :
: :

どなたか良い考えが思いつかれた方がいれば,
些細なことでも結構ですので御教授よろしくお願いします.

このQ&Aに関連する最新のQ&A

A 回答 (2件)

う~ん, どこで悩んでいるかが分かればなぁ....


基本的にはアルゴリズムをそのまま実装するだけでいいです. ただし, 本当にそのまま実装するととてつもなく効率が悪くなる可能性があるのでその辺はちょっと考える:
1. 入力ータをグラフと思って隣接リストにする
2. すべての要素のグループを空にする
3. until すべての要素にグループが割り当てられる do
4. グループが割り当てられていない要素を 1つ見つける
5. その要素を始点として幅優先探索でも深さ優先探索でも好きな方で探索する
6. 探索中に見つかったすべての要素を始点と同じグループに割り当てる
7. end until
要素数を n, ペアの数を m とすると, よほど下手に組まない限り O(n^2+m) より悪くはできないはず. ちょっと頭を使えば O(n+m).
    • good
    • 0
この回答へのお礼

Tacosan さん

 ありがとうございます.
 とりあえず四苦八苦しながらではありますがやってみます.

お礼日時:2009/05/26 20:30

グラフを連結成分に分割しろ, ってことだよね?


素直に
「X-Y というペアがあって X がグループ a に入っていたら Y もグループ a に入れる」
というのをひたすら繰り返すだけでいいのでは?
特に悩むことはないと思いますが.
    • good
    • 0
この回答へのお礼

その通りなんですが・・・
どういう風にプログラムを書けばよいかを悩んでまして・・・

お礼日時:2009/05/25 07:14

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

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

こんにちは。
プログラミングでつまってしまったため質問させて頂きます。
プログラミング言語は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を同じ組とはできない。
従って以下の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だったら、データ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;
}
}
}
}

こんにちは。
プログラミングでつまってしまったため質問させて頂きます。
プログラミング言語は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が似ているとは言えない。)

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

Aベストアンサー

データは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通りですね
それほど多くないので、グループ数の少ないほうからすべての組み合わせについて当てはまるかどうかを検査すればよいのではないでしょうか。

Qscanf("%s", buf);でスペースを含んだ文字

コンソールプログラムで
scanf("%s", buf);
を使用してユーザに入力された文字によって処理を行いたいのですが、このままではスペースを含む文字列がスペースの手前で切られてしまいます。
C:\Program Filesなどを入力可能にさせたい場合にはどのようにするのがベターですか?

Aベストアンサー

お任せください!
そもそもscanfを使うというのはお勧めでは
ありません。scanfは文字+改行文字が入力
されないと完了しないためです。
が、それは良しとしましょう。
scanfの書式ですが、

int n = scanf("%[^\r\n]",buf);

という便利な書式があります。
perlでもおなじみの書式ですね。
上記の山文字"^"より前が読み込ませたい文字の集まりで、ハイフン指定が出来ます。
"^"より後ろが読込みを停止させたい文字の集まりです。上記の指定は復帰改行以外の文字が現れるまで読み込みます、という書式です。
下記のような指定も出来ます。

int n = scanf("%[a-zA-Z0-9\\: \t^\r\n]",buf);

なお、戻り値は読み込んだ項目数ですので、
if(n >= 1)
{
}
で判断できますね。

Qbreak文でループを一気に抜けるには

break文でループを一気に(2個以上)
抜けたい場合はどのようにすればいいのでしょうか?
たとえば下のプログラムで1から2に抜けたい
すなわちifとforの2つの中括弧を同時に抜けたい場合には
どうやってbreak文を記述すればいいのでしょうか?
(goto文は使わないということでお願いします。

int k=0;
int i;

for (i=1;i<10;i++){
  k++;
  printf("%d",k);
  if (k == 5){
    printf("a");
    break;・・・・・・・・・1→
  }
}
printf("finish");・・・・・・・・・2←

Aベストアンサー

No.2 です。

> for文を2つ一気に抜ける場合にはどうしたらいいんでしょうか?

この場合は、素直に goto 文を使うか、No.1 さんのようにフラグで制御するしかないでしょう。

私はC言語実務経験20年以上ですが、goto 文について言えば、「無闇やたらに使うべきではないが、使うべき所で使うのをためらってはいけない」ということです。
よく、「何が何でも絶対に goto は使うな!」と言う人がいますが、これは間違っています。
たった1個の goto 文を避けるために、フラグなどを組み合わせて複雑怪奇な構造にすることの害の方が、余程大きいです。

Q配列の要素数に変数を入れたいときには

よろしくお願いします。
配列の要素数には定数しか入れられないのですが,どうしても変数を入れたいときは,それを引数として関数を呼び出すしか方法はないでしょうか。
具体的には,scanfで手に入れたint型の変数を要素数とする配列を宣言したいのですが,どうすれば良いでしょうか。
ご教授ください。

Aベストアンサー

c99と呼ばれる最近の規格では、配列の大きさに変数を使用できます。
bccはc99に対応していないようです。

それ以前の規格では、動的領域確保関数 malloc や callocを使って領域を確保するか、効率等を無視してバカデカい配列を用意しておくかです。
「それを引数として関数を呼び出す」っていうのは、malloc/callocのことですか?

QC言語 名前順にソートする方法

こんにちは。

C言語で「入力された文字列から名前順にソート」する場合、どのようにすればよろしいのでしょうか?
名前順にソートする考え方、コードを教えていただけませんか?
※qsortは使わない前提です。
私の中のイメージは「文字列[5]と文字列[4]を比較して、文字列[5]の頭文字が若い場合、交換する」といった具合なのですが、うまくコードに表すことができないです...。

ご教示お願いします><

Aベストアンサー

バブルソート?

http://www1.cts.ne.jp/~clab/hsample/Sort/Sort1.html

Q関数から配列を返すには?

return で配列を返すにはどうしたらよいのでしょうか。
例えば以下のような場合です。

int main (){

char Value[] = "999";
int a;

 a = test(Value);

 printf ("%d", a);
 
}


int test(char *Value)
{
int nVal[255];

ここで nVal に適当な処理をして・・・

 return Value;

}


 int a を配列とかにしてみましたけど、コンパイラが
通りません。
要は配列数値を main で受け取って表示したいのですが、
本日C言語はじめたところなので、教えていただければありががたいです。

Aベストアンサー

戻り値は1つしか戻せません。
引数で配列の先頭のポインタが渡され、それを使って関数で配列の中身を
書き換えて戻ってきて、メインで配列を参照すればいいです。

参考urlの(3)を参考にしてください。

参考URL:http://www9.plala.or.jp/sgwr-t/c/sec11-3.html

Qセグメントエラー

Cプログラムを実行した時に発生する、セグメントエラー
は何が原因なのでしょうか?
コンパイルはちゃんとととっているのに、
なぜエラーがでるのでしょうか?
C言語の本を見たのですが、
のってません。
お願いします。

Aベストアンサー

こんにちわ。

「セグメントエラー」ってSegmentation Fault の事ですよね。
そうであれば、メモリのアクセス侵害です。
原因としては、
・アクセスできない筈のアドレス (NULL アドレスとか) にアクセスした
・獲得したアドレスを越えてアクセスした。
・初期化していないポインタ変数を使ってアクセスした。
と言う感じです。

ケースとしては少ないと思いますが、1つの変数 (領域) を複数の
データ型でアクセスした場合に、起きる事があります。

Qセグメンテーション違反

C言語を使用しています。

構造体に値をいれようとしたら、コンパイルは出来るのですが、実行時に
「セグメンテーション違反です (core dumped)」
となってしまい、それ以上行えません。

構造体と代入したい変数との型は、合っています。

いろいろ本などで見ましたが、何が原因かわからず困っています。
教えてください。
宜しくお願いします。

Aベストアンサー

OSは何でしょうか。コンパイラは何を使用していますか?
通常、デバッグオプションをつけて実行すると、異常の発生したソースの箇所で止まりますので、それが手がかりになります。またNo1の方が言われてますように、ソースが公開できるのであれば、ソースを提示するのが良いかと思います。

Qエクセル STDEVとSTDEVPの違い

エクセルの統計関数で標準偏差を求める時、STDEVとSTDEVPがあります。両者の違いが良くわかりません。
宜しかったら、恐縮ですが、以下の具体例で、『噛み砕いて』教えて下さい。
(例)
セルA1~A13に1~13の数字を入力、平均値=7、STDEVでは3.89444、STDEVPでは3.741657となります。
また、平均値7と各数字の差を取り、それを2乗し、総和を取る(182)、これをデータの個数13で割る(14)、この平方根を取ると3.741657となります。
では、STDEVとSTDEVPの違いは何なのでしょうか?統計のことは疎く、お手数ですが、サルにもわかるようご教授頂きたく、お願い致します。

Aベストアンサー

データが母集団そのものからとったか、標本データかで違います。また母集団そのものだったとしても(例えばクラス全員というような)、その背景にさらならる母集団(例えば学年全体)を想定して比較するような時もありますので、その場合は標本となります。
で標本データの時はSTDEVを使って、母集団の時はSTDEVPをつかうことになります。
公式の違いは分母がn-1(STDEV)かn(STDEVP)かの違いしかありません。まぁ感覚的に理解するなら、分母がn-1になるということはそれだけ結果が大きくなるわけで、つまりそれだけのりしろを多くもって推測に当たるというようなことになります。
AとBの違いがあるかないかという推測をする時、通常は標本同士の検証になるわけですので、偏差を余裕をもってわざとちょっと大きめに見るということで、それだけ確証の度合いを上げるというわけです。

QLNK2019: 未解決の外部シンボルのエラーが出る

Microsoft Visual Studio 2008
Version 9.0.21022.8 RTM
Microsoft .NET Framework
Version 3.5 SP1
----------------------------------------------------------------
新しいプリジェクト→Win32 コンソール アプリケーション(ソリューションのディレクトリを作成 チェック外す)→Windows アプリケーション(空のプロジェクト チェック外す)
----------------------------------------------------------------
 プログラム

 mymain.cpp
#include "myhelper.h"
#include "mymain.h"

//自キャラのデータ
Point2D g_jikipos = {40, 400};//自キャラの座標

//画像ハンドル
int g_jikiimage[11];

//色々なファイルの読み込み
int LoadFiles(){
//画像ファイル読み込み
if(LoadDivGraph("media\\player01.bmp",
11,11,1,64,64,g_jikiimage) == -1) return -1;

return 1;
}


 mymain.h
//他から呼び出させるMyMainの関数
void MyMain();
int LoadFiles();


 myhelper.h(サンプルなので打ちミスはない)
#include "DxLib.h"
#include <limits.h>
#include <math.h>

//構造体宣言
//座標またはベクトルを記録する構造体
struct Vector{
float x,y;
};
typedef Vector Point2D;
//線を記録する構造体
struct Line2D{
Point2D startpos, endpos;
float katamuki;//傾きをラジアン値で記録
Vector speed;//移動している場合は速度をセット
};
//球体を記録する構造体
struct Ball2D{
Point2D position;
float hankei;//半径
};
//四角形を記録する構造体
struct Rect2D{
Point2D lefttop;
Point2D rightbottom;
float width;
float height;
};


//ライブラリ関数
Point2D PosInView(Point2D in);
int XInView(float inx);
int YInView(float iny);
void ScrollToLeft(float jikiposx);
void ScrollToRight(float jikiposx);
void ScrollToUp(float jikiposy);
void ScrollToDown(float jikiposy);
void DrawLineInView(float x1, float y1, float x2, float y2, int Color, int Thickness);
void DrawCircleInView(float x, float y, float r, int Color, int FillFlag);
void DrawAnimation(float x, float y, double ExtRate, double Angle,int TurnFlag,
int *imgarray, int allframe, float fps);
//ベクトル関数
Vector CreateVector(Vector in, float veclen);
Vector AddVector(Vector v1, Vector v2);
Vector SubVector(Vector v1, Vector v2);
Vector AddVectorInFrameTime(Vector pos, Vector speed);
Vector AddVectorInFrameTime2(Vector pos, Vector speed, Vector accel);
Vector Normalize(Vector in);
Vector RotateVector(Vector in, float radian);
float VectorLengthSquare(Vector in);
float DotProduct(Vector v1, Vector v2);
float CrossProduct(Vector v1, Vector v2);
void SetLine2DKatamuki(Line2D *in);
void DrawLine2D(Line2D in, int Color, int Thickness);
void DrawBall2D(Ball2D in, int Color, int Fill);
//当たり判定関数
bool HitTestLineAndBall(Line2D linein, Ball2D ballin);
bool IsPointAtLineFace(Line2D linein, Point2D ptin);
bool HitTestLineAndLine(Line2D line1, Line2D line2);
bool HitTestBallAndBall(Ball2D a, Ball2D b);
bool HitTestPointAndBox(Rect2D rect, Point2D pt);
//タイマー関数
void SetSimpleTimer(int idx, int time);
int GetPassedTime(int idx);


//グローバル変数
extern float g_frametime;
extern Rect2D g_framerect;//画面領域(当たり判定)
extern Point2D g_current_field_pos;//現在の左上座標
extern Rect2D g_stagesize;//ステージサイズ

//定数宣言
const float ZEROVALUE = 1e-10f;
const float PIE = 3.1415926f;
const int SCROLL_LIMIT = 200;
----------------------------------------------------------------
 エラー内容
1>myhelper.obj : error LNK2019: 未解決の外部シンボル "void __cdecl MyMain(void)" (?MyMain@@YAXXZ) が関数 _WinMain@16 で参照されました
1>C:\Documents and Settings\Owner\My Documents\Visual Studio 2008\Projects\my\Debug\my.exe : fatal error LNK1120: 外部参照 1 が未解決です
1>my - エラー 2、警告 0
ビルド: 0 正常終了、1 失敗、0 更新不要、0 スキップ
----------------------------------------------------------------
画像を貼り付けときます
(見えにくい場合→http://www.dotup.org/uploda/www.dotup.org154142.jpg.html)
初心者なのでわかりやすくお願いします

Microsoft Visual Studio 2008
Version 9.0.21022.8 RTM
Microsoft .NET Framework
Version 3.5 SP1
----------------------------------------------------------------
新しいプリジェクト→Win32 コンソール アプリケーション(ソリューションのディレクトリを作成 チェック外す)→Windows アプリケーション(空のプロジェクト チェック外す)
----------------------------------------------------------------
 プログラム

 mymain.cpp
#include "myhelper.h"
#include "mymain.h"

//自...続きを読む

Aベストアンサー

ファイル構成から推測するに
mymain.cpp というファイルに
void MyMain(void) {
// ここに処理を書く
}
という関数が必要なようです。


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング

おすすめ情報