考虑每一行的所有可能排列，找出一个单元数组的独特行

Question

我有一个尺寸为 m * k 的单元数组 A。

我想保持 A 的行在k个单元格的顺序上唯一。

“棘手”的部分是“在k个单元格的顺序上唯一”：考虑 A(i,:) 中第 i 行的 k 个单元格；可能会存在一行 j，A(j,:) 与 A(i,:) 等效，只是其 k 个单元格重新排列，例如如果 k=4，则可能是这样的：

A{i,1}=A{j,2}
A{i,2}=A{j,3}
A{i,3}=A{j,1}
A{i,4}=A{j,4}

我现在正在做的是：

G=[0 -1 1; 0 -1 2; 0 -1 3; 0 -1 4; 0 -1 5; 1 -1 6; 1 0 6; 1 1 6; 2 -1 6; 2 0 6; 2 1 6; 3 -1 6; 3 0 6; 3 1 6]; 
h=7;
M=reshape(G(nchoosek(1:size(G,1),h),:),[],h,size(G,2));
A=cell(size(M,1),2);
for p=1:size(M,1)
    A{p,1}=squeeze(M(p,:,:)); 
    left=~ismember(G, A{p,1}, 'rows');
    A{p,2}=G(left,:); 
end

%To find equivalent rows up to order I use a double loop (VERY slow).
indices=[]; 
for j=1:size(A,1)
    if ismember(j,indices)==0 %if we have not already identified j as a duplicate
        for i=1:size(A,1)
            if i~=j
               if (isequal(A{j,1},A{i,1}) || isequal(A{j,1},A{i,2}))...
                  &&...
                  (isequal(A{j,2},A{i,1}) || isequal(A{j,2},A{i,2}))...
                  indices=[indices;i]; 
               end
            end
        end
    end
end
A(indices,:)=[];

它能够工作，但速度太慢了。我希望有更快的替代方案可供使用。

- TEX

---

你好！这个问题还没有完成。你添加了“我目前正在做的是：”，但缺少“它不起作用的原因是：”这部分内容。 - Ander Biguri

在你的例子中，对于所有的 p，A{p,1} 和 A{p,2} 的大小是否总是相等的？换句话说，G 是否总是被平均分成左右两个单元格？ - erfan

@erfan 不，这并不总是正确的。子单元可以具有不同的度量。 - TEX

@AnderBiguri 我已添加澄清。谢谢 - TEX

有任何改进吗？这一直让我很忙。 - erfan

Answer 1

我想提出另一个想法，它在概念上与erfan的相似。我的想法使用哈希函数，具体来说是GetMD5 FEX提交。

主要任务是如何将A中的每一行“缩减”为单个代表值（如字符向量），然后找到此向量的唯一条目。

根据基准测试和其他建议，我的答案表现不如其中一种替代方案，但我认为它的存在意义在于它完全与数据类型无关（在GetMD5¹的限制范围内），算法非常简单易懂，是一个即插即用的替换，因为它操作A，并且生成的数组与原始方法得到的完全相等。当然，这需要编译器才能正常工作，并且有哈希冲突的风险（这可能会在极其罕见的情况下影响结果）。

以下是我的计算机上典型运行的结果和代码：

Original method timing:     8.764601s
Dev-iL's method timing:     0.053672s
erfan's method timing:      0.481716s
rahnema1's method timing:   0.009771s

function q39955559
G=[0 -1 1; 0 -1 2; 0 -1 3; 0 -1 4; 0 -1 5; 1 -1 6; 1 0 6; 1 1 6; 2 -1 6; 2 0 6; 2 1 6; 3 -1 6; 3 0 6; 3 1 6]; 
h=7;
M=reshape(G(nchoosek(1:size(G,1),h),:),[],h,size(G,2));
A=cell(size(M,1),2);
for p=1:size(M,1)
    A{p,1}=squeeze(M(p,:,:)); 
    left=~ismember(G, A{p,1}, 'rows');
    A{p,2}=G(left,:); 
end

%% Benchmark:
tic
A1 = orig_sort(A);
fprintf(1,'Original method timing:\t\t%fs\n',toc);

tic
A2 = hash_sort(A);
fprintf(1,'Dev-iL''s method timing:\t\t%fs\n',toc);

tic
A3 = erfan_sort(A);
fprintf(1,'erfan''s method timing:\t\t%fs\n',toc);

tic
A4 = rahnema1_sort(G,h);
fprintf(1,'rahnema1''s method timing:\t%fs\n',toc);

assert(isequal(A1,A2))
assert(isequal(A1,A3))
assert(isequal(numel(A1),numel(A4)))  % This is the best test I could come up with...

function out = hash_sort(A)
% Hash the contents:
A_hashed = cellfun(@GetMD5,A,'UniformOutput',false);
% Sort hashes of each row:
A_hashed_sorted = A_hashed;
for ind1 = 1:size(A_hashed,1)
  A_hashed_sorted(ind1,:) = sort(A_hashed(ind1,:));
end
A_hashed_sorted = cellstr(cell2mat(A_hashed_sorted));
% Find unique rows:
[~,ia,~] = unique(A_hashed_sorted,'stable');
% Extract relevant rows of A:
out = A(ia,:);

function A = orig_sort(A)
%To find equivalent rows up to order I use a double loop (VERY slow).
indices=[]; 
for j=1:size(A,1)
    if ismember(j,indices)==0 %if we have not already identified j as a duplicate
        for i=1:size(A,1)
            if i~=j
               if (isequal(A{j,1},A{i,1}) || isequal(A{j,1},A{i,2}))...
                  &&...
                  (isequal(A{j,2},A{i,1}) || isequal(A{j,2},A{i,2}))...
                  indices=[indices;i]; 
               end
            end
        end
    end
end
A(indices,:)=[];

function C = erfan_sort(A)
STR = cellfun(@(x) num2str((x(:)).'), A, 'UniformOutput', false);
[~, ~, id] = unique(STR);
IC = sort(reshape(id, [], size(STR, 2)), 2);
[~, col] = unique(IC, 'rows');
C = A(sort(col), :); % 'sort' makes the outputs exactly the same.

function A1 = rahnema1_sort(G,h)
idx = nchoosek(1:size(G,1),h);
%concatenate complements
M = [G(idx(1:size(idx,1)/2,:),:), G(idx(end:-1:size(idx,1)/2+1,:),:)];
%convert to cell so A1 is unique rows of A
A1 = mat2cell(M,repmat(h,size(idx,1)/2,1),repmat(size(G,2),2,1));

---

¹ - 如果需要对更复杂的数据类型进行哈希处理，可以使用DataHash FEX提交，但这会稍微慢一些。

- Dev-iL

---

不错！实际上，为了在涵盖一般情况的同时最高效地处理，应该使用您的“GetMD5”想法和我的排序方法！ - erfan

Answer 2

问题陈述：在识别数组中的唯一行时，理想的选择是使用C = unique(A,'rows')。但是有两个主要问题阻止我们在这种情况下使用此函数。首先是您想要在与其他行进行比较时考虑每行的所有可能排列。如果A有5列，则这意味着每行检查120个不同的重新排列!听起来不可能。

第二个问题与unique本身有关；它不接受单元格，除了字符向量的单元格数组。因此，您不能简单地将A传递给unique并获得您期望的结果。

为什么要寻找替代方案？因为目前速度非常慢:

With nested loop method:
------------------- Create the data (first loop):
Elapsed time is 0.979059 seconds.
------------------- Make it unique (second loop):
Elapsed time is 14.218691 seconds.

我的解决方案：

1. 生成另一个包含相同单元格的 cell 数组，但将其转换为字符串形式（STR）。
2. 找到所有唯一元素的索引（id）。
3. 生成与唯一索引相关联的矩阵并按行排序（IC）。
4. 找到唯一行（rows）。
5. 收集 A 的对应行（C）。

以下是代码：

disp('------------------- Create the data:')
tic
G = [0 -1 1; 0 -1 2; 0 -1 3; 0 -1 4; 0 -1 5; 1 -1 6; 1 0 6; ...
    1 1 6; 2 -1 6; 2 0 6; 2 1 6; 3 -1 6; 3 0 6; 3 1 6];
h = 7;
M = reshape(G(nchoosek(1:size(G,1),h),:),[],h,size(G,2));
A = cell(size(M,1),2);
for p = 1:size(M,1)
    A{p, 1} = squeeze(M(p,:,:));
    left = ~ismember(G, A{p,1}, 'rows');
    A{p,2} = G(left,:);
end
STR = cellfun(@(x) num2str((x(:)).'), A, 'UniformOutput', false);
toc

disp('------------------- Make it unique (vectorized):')
tic
[~, ~, id] = unique(STR);
IC = sort(reshape(id, [], size(STR, 2)), 2);
[~, col] = unique(IC, 'rows');
C = A(sort(col), :); % 'sort' makes the outputs exactly the same.
toc

性能检查：

------------------- Create the data:
Elapsed time is 1.664119 seconds.
------------------- Make it unique (vectorized):
Elapsed time is 0.017063 seconds.

虽然初始化需要更多的时间和内存，但考虑到所有排列组合中找到唯一行的能力，该方法执行速度极快。在A列数上的执行时间几乎不受影响。

- erfan

Answer 3

看起来G是一个误导性的点。 以下是小数字的nchoosek结果。

idx=nchoosek(1:4,2)
ans =

   1   2
   1   3
   1   4
   2   3
   2   4
   3   4

第一行是最后一行的补集。

第二行是倒数第二行的补集。

......

因此，如果我们从 G 中提取行 {1, 2}，那么它的补集将是行 {3, 4}，依此类推。换句话说，如果我们假设 G 的行数为4，则G(idx(1,:),:)是G(idx(end,:),:)的补集。

由于G的行都是唯一的，因此所有的A{m,n}的大小始终相同。 A{p,1}和A{p,2}是彼此的补集。而A的唯一行的大小为size(idx,1)/2 因此，不需要任何循环或进一步的比较。

h=7;
G = [0 -1 1; 0 -1 2; 0 -1 3; 0 -1 4; 0 -1 5; 1 -1 6; 1 0 6; ...
    1 1 6; 2 -1 6; 2 0 6; 2 1 6; 3 -1 6; 3 0 6; 3 1 6];
idx = nchoosek(1:size(G,1),h);
%concatenate complements
M = [G(idx(1:size(idx,1)/2,:).',:), G(idx(end:-1:size(idx,1)/2+1,:).',:)];
%convert to cell so A1 is unique rows of A
A1 = mat2cell(M,repmat(h,size(idx,1)/2,1),repmat(size(G,2),2,1));

更新：上述方法最好的效果是，如果想要从A中获取A1而不是G，则建议使用以下基于 erfan 提供的方法。我们可以直接使用数组，而不是将数组转换为字符串：

STR=reshape([A.'{:}],numel(A{1,1}),numel(A)).';
[~, ~, id] = unique(STR,'rows');

IC = sort(reshape(id, size(A, 2),[]), 1).';
[~, col] = unique(IC, 'rows');
C1 = A(sort(col), :);

由于我使用Octave，目前无法运行mex文件，因此无法测试Dev-iL的方法。

结果:

erfan method (string):  4.54718 seconds.
rahnema1 method (array): 0.012639 seconds.

在线演示

- rahnema1

---

@EBH 我不完全同意你的看法 - 这是一个关于“真实”输入数据是什么的问题。描述更大的画面之美在于，有人可能会建议一个完全不同的方法，这个方法可以更好地工作。我喜欢上述答案中恰好这个方面。@rahnema - 你如何确保你的A1等效于OP的A？由于行的顺序不同，我认为你应该包含一些验证代码。 - Dev-iL

@Dev-iL 简单的嵌套循环 [r c] = size(A);for m = 1:r;for n = 1:c; if ~isequal(A{m,n} ,A1{m,n});disp('有些地方出了问题！');break;end;end;end; - rahnema1

当元素的顺序相同时，您可以使用isequal(A,A1) - 无需循环。由于isequal（对于完整的A数组）与您的A1不起作用，但是您的A1大小正确，我假设这是因为元素的不同排序。您建议的循环由于上述元素排序而注定失败。 - Dev-iL

唯一的问题是“子单元可以具有不同的度量” - EBH

@rahnema1 做得好！当我开始时，我的想法也是这个方向。有一点需要注意，在MATLAB中，A.'{:}语法不起作用，需要分两步完成。你的方法唯一的缺点是只适用于这个例子。 - erfan