有訂單限制的排列

讓L爲對象列表。此外，讓C是一組約束，例如：有訂單限制的排列

C(1) = t1 comes before t2，其中t1和t2屬於L
C(2) = t3 comes after t2，其中t3和t2屬於L

我怎樣才能找到（在MATLAB中）的約束在C未被違反的一組排列？

我的第一個解決方案是幼稚：

orderings = perms(L); 
    toBeDeleted = zeros(1,size(orderings,1)); 
    for ii = 1:size(orderings,1) 
      for jj = 1:size(constraints,1) 
        idxA = find(orderings(ii,:) == constraints(jj,1)); 
        idxB = find(orderings(ii,:) == constraints(jj,2)); 
        if idxA > idxB 
          toBeDeleted(ii) = 1; 
        end 
      end 
    end

其中constraints是一組約束的（每個約束是在兩個元件的行，指定第一元件而來的第二元件之前）。

我想知道是否存在一個更簡單（和更高效）的解決方案。

在此先感謝。

來源

2013-06-03 Eleanore

每當你在向量或矩陣中尋找東西時，都應該使用find或ismember。 – 2013-06-03 08:54:10

當然。建議的解決方案是一個僞代碼（perms指令除外）。但是，我認爲這不是可能的最佳解決方案，因爲我必須遍歷所有排序和所有約束。但是，我更新了代碼（現在不是僞代碼）。 – Eleanore

最好[不要在Matlab中使用'i'和'j'作爲變量名]（http://stackoverflow.com/questions/14790740/using-i-and-j-as-variables-in-matlab）。 – Shai

我想說，這是迄今爲止您的一個很好的解決方案。

雖然我看到了一些優化。這裏是我的變化：

% INITIALIZE 

NN = 9; 
L = rand(1,NN-1); 
while numel(L) ~= NN; 
    L = unique(randi(100,1,NN)); end 

% Some bogus constraints 
constraints = [... 
    L(1) L(2) 
    L(3) L(6) 
    L(3) L(5) 
    L(8) L(4)]; 


% METHOD 0 (your original method) 

tic 

orderings = perms(L); 

p = size(orderings,1); 
c = size(constraints,1); 

toKeep = true(p,1); 
for perm = 1:p 
    for constr = 1:c   
     idxA = find(orderings(perm,:) == constraints(constr,1)); 
     idxB = find(orderings(perm,:) == constraints(constr,2)); 
     if idxA > idxB 
      toKeep(perm) = false; 
     end 
    end 
end 

orderings0 = orderings(toKeep,:); 

toc 

% METHOD 1 (your original, plus a few optimizations) 

tic 

orderings = perms(L); 

p = size(orderings,1); 
c = size(constraints,1); 

toKeep = true(p,1); 
for perm = 1:p  
    for constr = 1:c 
     % break on first condition breached 
     if toKeep(perm) 
      % find only *first* entry 
      toKeep(perm) = ... 
       find(orderings(perm,:) == constraints(constr,1), 1) < ... 
       find(orderings(perm,:) == constraints(constr,2), 1); 
     else 
      break 
     end 
    end  
end 

orderings1 = orderings(toKeep,:); 

toc 


% METHOD 2 

tic 

orderings = perms(L); 

p = size(orderings,1); 
c = size(constraints,1); 

toKeep = true(p,1); 
for constr = 1:c 

    % break on first condition breached1 
    if any(toKeep) 

     % Vectorized search for constraint values 
     [i1, j1] = find(orderings == constraints(constr,1)); 
     [i2, j2] = find(orderings == constraints(constr,2)); 

     % sort by rows 
     [i1, j1i] = sort(i1); 
     [i2, j2i] = sort(i2); 

     % Check if columns meet condition 
     toKeep = toKeep & j1(j1i) < j2(j2i); 

    else 
     break 
    end 

end 
orderings2 = orderings(toKeep,:); 

toc 

% Check for equality 
all(orderings2(:) == orderings1(:))

結果：

Elapsed time is 17.911469 seconds. % your method 
Elapsed time is 10.477549 seconds. % your method + optimizations 
Elapsed time is 2.184242 seconds. % vectorized outer loop 
ans = 
    1 
ans = 
    1

然而，整個方法有一個根本的缺陷恕我直言;直接使用perms。這由於內存限制而固有地構成限制（NN < 10，如在help perms中所述）。

我有一個強烈的懷疑，你可以得到更好的性能，無論是在時間上和記憶方面，當你把自定義perms。幸運的是，perms不是內置的，因此您可以通過將該代碼複製粘貼到自定義函數中開始。

來源

2013-06-03 10:56:58

有訂單限制的排列

回答

相關問題