在矩陣中查找k個不相交的行的組

問題陳述：讓S爲一組整數，例如， S = {1,2,...,12}。 M是一個整數矩陣，其行可以被視爲S的子集，其長度分爲S元素的數量，特別是每行M只包含不同的元素/整數。我試圖生成Matlab代碼，它可以識別所有不相交的行集合M，它們的集合聯合給出S（即具有固定大小的子集中的S的分區），並將每個這樣的組作爲矩陣返回。在矩陣中查找k個不相交的行的組

實施例：A = [1 2 5 6; 3 4 11 12; 9 10 7 8]是S一個分區，而B = [1 2 3 4; 5 6 7 8; 9 10 11 12; 1 5 9 12]不是S一個分區（由於最後一行不與先前的3不相交）。

數量級：通常，M將有〜500000行，並且S將有多達100個元素。

方法至今：讓m = size(M,1)，n = size(M,2)（分區子集的大小），s = |S|（下集的大小來劃分）和k = s/n（必要不相交的行數，形成分區 - 你可以假設s = 0 mod n，所以問題是明確的）。請注意，爲了建立這樣一個分區，只需檢查行的不相交情況，並且確切地說有很多這樣的分組。

對於j = 1:(m-k+1)，我觀察到ind = (sum(ismember(M((j+1):m,:),M(j,:)),2)==0)，它給出了M(j,:)之後的行的索引列，這些索引列也與它不相交。然後，我通過將M(j,:)與這些行中的每一行組合來創建2 x n矩陣。之後，我想重複所有這些新的2 x n矩陣的ismember()例程，並不斷重複，直到得到k x n矩陣。這可能都很好，並且很花哨，但它也是我偶然發現的地方，因爲其中一個for例程的數量取決於k。

問題：

（Q1）我怎樣才能完成我的方法的代碼？（Q2）是否有更好的方法來解決這個問題（即更快，矢量化/更少for循環，GPU輔助），如果是，它們是什麼？

來源

2014-08-27 July

是否有'M'的典型列數。即'n'？ 'S'總會有獨特的整數集合嗎？ – Divakar 2014-08-27 19:35:36

如果我沒有弄錯，'n'不應該超過8或9。對於'S'，可以假設'S =唯一的（M）'，即'S'的所有元素都已經包含在'M'的某處。「S」的所有元素都是不同的，它們的順序並不重要。我希望我能正確理解你的第二個問題。 – July 2014-08-27 19:58:47

@July：在你的大多數問題中，'M'是你輸入矩陣的名字，但在例子中'M'是一個可能的解決方案，請在那裏重新命名。至少我們知道解決方案的大小是'numel（S）'，這允許嘗試近似值並在達到此大小時停止。你能提供一個示例數據集嗎？ – Daniel 2014-08-27 20:03:16

這個問題的exact cover一個不是非常特殊的情況。如果你在C工作，我建議Knuth's Algorithm X，與bit arrays而不是dancing links實施，由於您所關注的實例的密度明顯。我期望MATLAB幾乎可以適應你。

作爲整數，集合{1,2,5,6}可以表示爲2 ** 1 + 2 ** 2 + 2 ** 5 + 2 ** 6。然後兩組的交集表示爲它們的表示的bitwise and，並且兩組的集合是按位或。空集是0.不幸的是，對於S = 100，你需要使用兩個或多個整數，這會使生活變得複雜。在進行一組設置後，您可以通過向量化的bitand來檢測與其他組的交集。

來源

2014-08-27 20:11:50

邏輯稀疏矩陣可能是實現它的替代方案。 – Daniel 2014-08-27 20:40:52

@Daniel如果以我期望的方式實現，那麼交集的運行時間將從二次方下降到線性，但字平行不會被利用。我希望這裏的關鍵改進在任何情況下都可以使用算法X，並具有良好的列順序。 – 2014-08-27 21:28:01

感謝您指點Knuth的算法X，至少在理論上解決了我的問題。 – July 2014-08-28 18:07:34

這是你想要的嗎？我認爲M行中的行順序（即排列2行是另一個有效的M）。本示例爲您提供了2列和3行的所有矩陣，其中元素全部不同且位於{1,2,3,4,5,6}中。但是，行是{1,2,3,4,5,6}的子集，順序無關緊要。不知道這是你的意思。如果訂單很重要，我們可以添加perms以獲得nchoosek返回的每行所有可能的排列。

我不得不使用遞歸函數，所以你必須把它放在一個文件：

function test() 
    s = 1:6; 
    n = 2; 

    M_all = ProcessOneRow(s, n, {}, {}); 

    disp('All possilbe M:') 
    M_all 
end 

function M_all = ProcessOneRow(s, n, cRows, M_all) 

    %// find all possible rows for this level 
    possibleRows = nchoosek(1:length(s), n); 

    for t=1:size(possibleRows, 1) 
     %// keep track of all rows so far 
     cRows(end+1) = s(possibleRows(t,:)); 

     %// get elements remaining (remove this row) 
     s_sub = s; 
     s_sub(possibleRows(t,:)) = []; 

     if isempty(s_sub) 
      %// We found a new complete matrix M 
      M = []; 
      for p = 1:numel(cRows) 
       M(p,:) = cRows{p}; 
      end 
      M_all{end+1} = M; 
     else 
      %// Still not a complete M, so we process the rest 
      M_all = ProcessOneRow(s_sub, n, cRows, M_all); 
     end 
     cRows(end) = []; 
    end 
end

來源

2014-08-27 20:10:20 seb

在矩陣中查找k個不相交的行的組

回答

相關問題