グループ化制約を持つ最初の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（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 

エンド

私は明確な順列を取得するために、Jの上にループでcircshiftを使用してみましたが、それは特定のケースではなく、一般的に仕事を得ることができます。これを行う体系的な方法はありますか？私はすべての順列を生成し、それらをフィルタリングしたくありません。

また、私はこの論文を見つけました：

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 

}