CODEWITHSUNDEEP
algorithmmatlabconstraintspermutation
onehalfatsquared
onehalfatsquared

Reputation: 3

Permutations of first n integers with grouping constraints

I would like to generate all the permutations of the first n integers such that specified groups of integers remain in their group, and the groups remain in the same order. For example, if we have n=5 and the grouping [[1],[2,3],[4,5]], then I want to output

[[1],[2,3],[4,5]]

[[1],[2,3],[5,4]]

[[1],[3,2],[4,5]]

[[1],[3,2],[5,4]

Each permutation should appear as a row in a matrix, I have just included the bracket notation for ease of seeing the groupings. In my case, the number 1 is always the first element of each permutation. I have tried generating all the permutations of each group, and then pasting them into a matrix an appropriate number of times, but can't figure out a general way to cycle the groups such that permutations don't repeat. Here is my code: f is a vector where f(i) is the starting index of group i, and r is a vector such that r(i) is the number of elements in group i. 

function AP=allPerms(f,r)
%Construct all possible permutations of integers consistent with their
%grouping
n=length(r);                   %Number of groups
num_parts=f(n)+r(n)-1;         %Number of integers
num_perms=factorial(r(1)-1);   %Initialize num of perms
for i=2:n
    num_perms=num_perms*factorial(r(i));    %Formula for num_perms
end
AP=zeros(num_perms,num_parts); %Initialize matrix to store perms
AP(:,1)=ones(num_perms,1);     %First column is all 1's

%handle case where there is only 1 group
if n==1
    AP(:,2:num_parts)=perms(2:num_parts);
    return
end

%Construct all the sublist perms
v{1}=perms(2:f(2)-1); v{n}=perms(f(n):f(n)+r(n)-1);
for i=2:n-1
    v{i}=perms(f(i):f(i+1)-1);
end

%Insert into perm array appropriate number of times. consider i=1,n
%seperately
if r(1)~=1
    for j=1:num_perms/factorial(r(1)-1)
        AP((j-1)*factorial(r(1)-1)+1:j*factorial(r(1)-1),2:f(1)+r(1)-1)=v{1}; 
    end
end
for i=2:n-1
    for j=1:num_perms/factorial(r(i))
        AP((j-1)*factorial(r(i))+1:j*factorial(r(i)),f(i):f(i)+r(i)-1)=v{i};
    end
end 
for j=1:num_perms/factorial(r(n))
    AP((j-1)*factorial(r(n))+1:j*factorial(r(n)),f(n):f(n)+r(n)-1)=v{n};
end

end

I have tried using circshift in the loops over j to get distinct permutations and can get it to work for specific cases, but not in general. Is there a systematic way to do this? I do not want to generate all the permutations and then filter them.

I also found this paper:

https://arxiv.org/pdf/1311.3813.pdf

I would like to know if there is a variant of my solution that may work before I try to implement this though.

Upvotes: 0

Views: 106

Answers (1)

rahnema1
rahnema1

Reputation: 15867

Here is a solution based on cellfun, perms and ndgrid

grouping={1,[2 3],[4 5]};
perm = cellfun(@(x){perms(x)},grouping);      %for each group generate all permutations
cart = cell(1,numel(grouping));               
perm_size = cellfun(@(x){1:size(x,1)},perm);  % [1 : size_of_permutation] to be used in ndgrid
[cart{:}]=ndgrid(perm_size{:});               % Cartesian product of indexes of permutations
result = cell(1,numel(grouping));
for k = 1:numel(cart)
    result(k) = perm{k}(cart{k},:);           % In the loop index permutations with the cartesian product of their indexes
end

Here is the result:

result =
{
  [1,1] =

     1
     1
     1
     1

  [1,2] =

     2   3
     3   2
     2   3
     3   2

  [1,3] =

     4   5
     4   5
     5   4
     5   4

}

Upvotes: 0

Related Questions