Permutations with order restrictions

Question

Let L be a list of objects. Moreover, let C be a set of constraints, e.g.:

C(1) = t1 comes before t2, where t1 and t2 belong to L
C(2) = t3 comes after t2, where t3 and t2 belong to L

How can I find (in MATLAB) the set of permutations for which the constraints in C are not violated?

My first solution is naive:

    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

where constraints is a set of constraints (each constraint is on a row of two elements, specifying that the first element comes before the second element).

I was wondering whether there exists a simpler (and more efficient) solution.

Thanks in advance.

Whenever you're looking for something in a vector or matrix you should use find or ismember. — , Jun 03 '13 at 08:54
Sure. The proposed solution is a pseudocode (except for the perms instruction). However, I think this is not the best solution possible, since I have to iterate through all the orderings and all the constraints. However, I have updated the code (it is not a pseudocode now). — Eleanore, Jun 03 '13 at 08:55
It is best [not to use `i` and `j` as variable names in Matlab](http://stackoverflow.com/questions/14790740/using-i-and-j-as-variables-in-matlab). — Shai, Jun 03 '13 at 09:32
This quesiton is highly related to [topological sort](http://en.wikipedia.org/wiki/Topological_sorting). — Shai, Jun 03 '13 at 10:23

score 1 · Answer 1 · answered Jun 03 '13 at 10:56

I'd say that's a pretty good solution you have so far.

There is a few optimizations I see though. Here's my variation:

% 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(:))

Results:

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

The whole approach however has one fundamental flaw IMHO; the direct use of perms. This inherently poses a limitation due to memory constraints (NN < 10, as stated in help perms).

I have a strong suspicion you can get better performance, both time-wise and memory-wise, when you put together a customized perms. Luckily, perms is not built-in, so you can start by copy-pasting that code into your custom function.

Permutations with order restrictions

1 Answers1