2017-06-17 53 views
0

我想要生成前n個整數的所有排列,以使指定的整數組保留在它們的組中,並且這些組保持相同的順序。例如,如果我們有n = 5和分組[[1],[2,3],[4,5]],那麼我想輸出具有分組約束的前n個整數的排列

[[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

我想知道是否有我的解決方案的一個變體之前,我嘗試,雖然實現這一可能的工作。

回答

0

這是基於cellfunpermsndgrid

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 

} 
+0

謝謝!這很好用!唯一的事情是在你定義perm_size的第4行中,它應該是階乘(size(x,2))來得到置換的大小。它仍然有效,因爲我的示例案例包含兩個或更少元素的組。 – onehalfatsquared

+0

@onehalfatsquared好的,它應該是'size(x,1)'。或者它可以是'perm_size = cellfun(@(x){1:factorial(numel(x))},grouping)'。答案已更新。 – rahnema1