Permutationen der ersten n ganzen Zahlen mit Gruppierungseinschränkungen

Question

Ich möchte alle Permutationen der ersten n ganzen Zahlen erzeugen, so dass bestimmte Gruppen von ganzen Zahlen in ihrer Gruppe bleiben und die Gruppen in der gleichen Reihenfolge bleiben. Zum Beispiel, wenn wir n = 5 und die Gruppierung [[1], [2,3], [4,5]] haben, dann möchte ich ausgeben

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

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

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

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

Jede Permutation sollte als eine Zeile in einer Matrix erscheinen, ich habe gerade die Bracket-Notation eingefügt, um die Gruppierungen leichter zu sehen. In meinem Fall ist die Zahl 1 immer das erste Element jeder Permutation. Ich habe versucht, alle Permutationen jeder Gruppe zu erzeugen und sie dann in einer Matrix in angemessener Anzahl einzufügen, aber ich kann keinen allgemeinen Weg finden, die Gruppen so zu zyklieren, dass Permutationen sich nicht wiederholen. Hier ist mein Code: f ist ein Vektor, wobei f (i) der Startindex der Gruppe i ist und r ein Vektor ist, so dass r (i) die Anzahl der Elemente in der Gruppe i ist.

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 

Ende

ich in den Schleifen über j mit circshift versucht haben, verschiedene Permutationen zu bekommen und kann es für bestimmte Fälle zu arbeiten, aber nicht im Allgemeinen. Gibt es einen systematischen Weg, dies zu tun? Ich möchte nicht alle Permutationen generieren und sie dann filtern.

Ich fand auch dieses Papier:

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

Ich möchte wissen, ob es eine Variante meiner Lösung ist, die funktionieren kann, bevor ich versuche, dies allerdings zu implementieren.

Answer 1

Hier ist eine Lösung basierend auf cellfun, perms und 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 

Hier ist das Ergebnis:

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 

}