2

设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是一组约束（每个约束在一行两个元素上，指定第一个元素在第二个元素之前）。

我想知道是否存在更简单（更有效）的解决方案。

提前致谢。

4

1 回答 1

1

我会说这是你迄今为止的一个很​​好的解决方案。

我看到了一些优化。这是我的变化：

% 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-03T10:56:58.457 回答