具有分组约束的前n个整数的排列

Question

我想要生成前n个整数的所有排列，以使指定的整数组保留在它们的组中，并且这些组保持相同的顺序。例如，如果我们有n = 5和分组[[1]，[2,3]，[4,5]]，那么我想输出

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

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

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

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

每个置换都应该在矩阵中显示为一行，为了便于查看分组，我刚刚包含了括号表示法。就我而言，数字1始终是每个排列的第一个元素。我已经尝试生成每个组的所有排列，然后将它们粘贴到矩阵中适当次数，但无法弄清楚循环组的一般方法，使得排列不会重复。这里是我的代码：f是一个向量，其中f（i）是组i的起始索引，r是一个向量，使得r（i）是组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 

末

我在循环使用circshift在j来取得不同的排列组合，可以得到它的特定的情况下工作，但不是一般的尝试。有没有系统的方法来做到这一点？我不想生成所有的排列，然后过滤它们。

我也发现这个文件：

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

我想知道是否有我的解决方案的一个变体之前，我尝试，虽然实现这一可能的工作。

Answer 1

这是基于cellfun，perms和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 

这里的解决方案是结果：

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 

}