行列の各行に対してラベル付け

現在、MATLABで行列の各行に対してラベル付けをするアルゴリズムを考えています。

例えば [1 2 ; 3 4 ; 2 5]という行列があった場合に1行目は「1」、２行目は１行目と重複する要素がないため「2」、３行目は２が１行目と重複しているため「1」とラベルを付けるアルゴリズムを考えています。

重複する要素がある行は同じ数字のラベル付けをするというアルゴリズムです。

この例の場合、最終的には [1 ; 2 ; 1]が得られればよいということになります。

何かアイデアがある方、よろしくお願いします。

[Akira Agata]

念のため確認なのですが、複数の行に重複する要素がある場合はどうなるのでしょうか？

例えば [1 2 ; 3 4 ; 2 4] という行列があった場合、３行目は１行目とも２行目とも重複する要素があることになりますが、その場合どのようなラベルになるのでしょうか？（あるいはそもそも複数の行に重複しないようなデータになっているのでしょうか？）

[YA]

説明が不十分で申し訳ありませんでした。

その場合はすべて同じラベル分けになるので、「1」となります。

なので、[1 ; 1 ; 1 ]が求めたいラベル分けになります。

重複が複数行になることもありうるデータとなっています。

よろしくお願いします。

Answer 1

[Akira Agata]

グラフ理論を使う方法はどうでしょうか？

配列Aの各要素をノード番号、各行をエッジとみなすと、配列からグラフGを構成することができます。

すると、「求めたいラベル番号」は「エッジが属するサブグラフの番号」と等価になります。

言葉だけでは分かりにくいと思いますので、以下に具体例を示します。

% 例
A = [1 2; 3 4; 2 5];

% 各行を Edge とみなしてグラフを構築
G = graph(A(:,1), A(:,2));

% ノード一覧と属するサブグラフ情報を取得
node = 1:max(A(:));
id = conncomp(G);

% Aの1列目のノードがどのサブグラフに属しているかを判別
label = interp1(node, id, A(:,1));

% ラベルを表示
disp(label)

     1
     2
     1

% 参考として、構築したグラフを可視化
figure
plot(G)

[YA]

ご回答ありがとうございます。

グラフ理論を使うという発想はありませんでした。

とても参考になりました。ありがとうございます。