如何去除排列矩阵中的反向行

Question

我正在MATLAB中寻找一种快速的方法来完成以下操作：

给定一个向量的排列矩阵，比如[1, 2, 3]，我想去掉所有重复的反向行。

所以矩阵P = perms([1, 2, 3])

3 2 1 
3 1 2     
2 3 1    
2 1 3    
1 3 2     
1 2 3 

成为

3 2 1    
3 1 2     
2 3 1

Answer 1

您可以注意到，对称地，每行的第一个元素必须比最后一个元素大：

n = 4;                    %row size
x = perms(1:n)            %all perms
p = x(x(:,1)>x(:,n),:)    %non symetrical perms

或者你可以注意到，p矩阵所包含的行数遵循每个n的OEIS序列，并对应于size(x,1)/2，因此由于置换以相反的字典顺序输出置换：

n = 4;                    %row size
x = perms(1:n)            %all perms
p = x(1:size(x,1)/2,:)    %non symetrical perms

Answer 2

您可以使用MATLAB的fliplr方法从左到右翻转数组，然后使用ismember在翻转版本中查找P的行。最后，迭代所有位置并选择已找到的行。

以下是一些代码(使用Octave 5.2.0和MATLAB在线测试(：

a = [1, 2, 3];
P = perms(a)
% Where can row x be found in the left right flipped version of row x?
[~, Locb] = ismember(P, fliplr(P), 'rows');
% Set up logical vector to store indices to take from P.
n = length(Locb);
idx = true(n, 1);
% Iterate all locations and set already found row to false.
for I = 1:n
if (idx(I))
idx(Locb(I)) = false;
end
end
% Generate result matrix.
P_star = P(idx, :)

你的例子：

P =
3   2   1
3   1   2
2   3   1
2   1   3
1   3   2
1   2   3
P_star =
3   2   1
3   1   2
2   3   1

在示例中添加了4：

P =
4   3   2   1
4   3   1   2
4   2   3   1
4   2   1   3
4   1   3   2
4   1   2   3
3   4   2   1
3   4   1   2
3   2   4   1
3   2   1   4
3   1   4   2
3   1   2   4
2   4   3   1
2   4   1   3
2   3   4   1
2   3   1   4
2   1   4   3
2   1   3   4
1   4   3   2
1   4   2   3
1   3   4   2
1   3   2   4
1   2   4   3
1   2   3   4
P_star =
4   3   2   1
4   3   1   2
4   2   3   1
4   2   1   3
4   1   3   2
4   1   2   3
3   4   2   1
3   4   1   2
3   2   4   1
3   1   4   2
2   4   3   1
2   3   4   1

正如你的问题所要求的那样(至少从我的理解来看(，行是从上到下的。

Answer 3

这里有另一种方法：

result = P(all(~triu(~pdist2(P,P(:,end:-1:1)))),:);

1. pdist计算P的行与P(:,end:-1:1)的行之间的距离
2. ~否定该结果，使得true对应于重合对
3. triu只保留矩阵的上三角部分，因此重合对的两行中只有一行将被移除
4. ~取反，使得true对应于不重合对
5. all为应该保留的行(因为它们与任何前行不一致(提供了一个具有true的行向量
6. 这被用作选择P的行的逻辑索引