アレイの同等のパーティションを見つける

Question

最小化の問題に基づいて、アレイのパーティションを見つけるアルゴリズムがあるとします（nodes=[1:10]）。アルゴリズムの出力は、特定のノードがどのパーティションに割り当てられているかを示すインデックスの配列になります。例：part=[1 1 1 1 3 3 2 2 2 2]。

このアルゴリズムには問題があります。それは確率的な成分を持ち、時々同じパーティションを返すことができますが、異なる番号を付けます。たとえば、part2=[2 2 2 2 3 3 1 1 1 1]です。この場合、part1とpart2は事実上同じパーティションです。

パーティション分割アルゴリズムを5回実行する必要があるとします。出力は5x10の行列Aになります。最後に、アルゴリズムが見つけたパーティションの数を確認する必要があります。これは、Aにいくつの同等のパーティションが存在するかを知る必要があることを意味します。

これは、と書いてありますが、大きな入力に対してはと遅いですが、となります。

ここで入力の例：私は別のパーティションに、最も頻繁にパーティション、それはmを発生する回数を取得

clusters=[ 1,1,2,2; 
      1,1,2,2; 
      2,2,1,1; 
      1,2,1,2; 
      2,1,2,1; 
      3,1,2,1; 
      2,1,2,1; 
      3,1,2,1; 
      1,2,1,2]; 

いる：

true_clusters = 

1  1  2  2 
1  2  1  2 
3  1  2  1 


frequest = 

1  2  1  2 

m = 

4 

誰もが知っています速い方法で問題を解決するには？

Answer 1

これはベクトル化バージョンです：

があるため、それらのすべてに同じパターンを持つ行[1 2 1 2]と[3 1 2 1]と[ 2 1 2 1]を考えてみましょう各ベクトルの連続した要素は互いに異なるので、これらの行についてdiff(clusters,1,2)~=0は同じパターン[1 1 1]を生成します。 しかし、それはアルゴリズムの正解を得るには不十分です。 また、各行には、固有の要素が必要です。 ので[1 1 2 2]にユニークな要素は[1 2]あり、[3 1 2 1]ユニークな要素に等しく論理ベクトルは、[1 1 2 2]論理ベクトルが[1 1 0]あり、[3 1 2 1]ために行うaccumarray[1 1 1]あるために[1 2 3]の各々は、行のメンバーである場合に表す[1 2 3] を作成することができるされています上記のタスク。 2つのパターンを連結して[diff(clusters,1,2)~=0 , ac]という配列を作成し、行が異なるパーティションを表すようにします。

many = 3 4 2 

true_clusters = 

    2 2 1 1 
    1 2 1 2 
    3 1 2 1 

m = 4 

frequest = 1 2 1 2 

：その後、 unique機能は、独自のパーティション

ac=accumarray([ repmat((1:size(clusters,1)).',size(clusters,2),1) clusters(:)],1,[],@any); 
[~, v, I]=unique([diff(clusters,1,2)~=0 , ac],'rows'); 
many= hist(I,I(v)); 
true_clusters = clusters(v,:); 
[m,im] = max(many); 
frequest = true_clusters(im,:); 

の検索結果を抽出するために適用することができ

Answer 2

、それはあなたのために十分に速い場合、私は知らない。

[~,~,c] = unique(clusters','rows','stable'); 

c_unique = unique(c,'rows')