考虑到每行上所有可能的排列，找到单元格数组的唯一行 [英] Find unique rows of a cell array considering all possible permutations on each row

问题描述

我有尺寸为m * k的单元格数组A.

I have cell array A of dimension m * k.

我想将A的行保持唯一性最多按k个单元格的顺序.

I want to keep the rows of A unique up to an order of the k cells.

棘手"部分是最多k个单元格" :考虑A，A(i,:)的第i行中的k个单元格；可能存在A，A(j,:)的行j，相当于A(i,:)，直到对其k单元格的重新排序，这意味着例如k=4可能是:

The "tricky" part is "up to an order of the k cells": consider the k cells in the ith row of A, A(i,:); there could be a row j of A, A(j,:), that is equivalent to A(i,:) up to a re-ordering of its k cells, meaning that for example if k=4it could be that:

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,:)=[];

它可以工作，但是速度太慢.我希望可以更快地使用一些东西.

It works but it is too slow. I am hoping that there is something quicker that I can use.

推荐答案

我想提出另一个想法，该想法与哈希函数，特别是

I'd like to propose another idea, which has some conceptual resemblance to erfan's. My idea uses hash functions, and specifically, the GetMD5 FEX submission.

主要任务是如何将A中的每一行还原"为单个代表值(例如字符向量)，然后查找该向量的唯一条目.

The main task is how to "reduce" each row in A to a single representative value (such as a character vector) and then find unique entries of this vector.

根据基准与其他建议相比，我的答案不如其他方法之一好，但我认为其 raison d'être在于它完全不可知的数据类型(在GetMD5 ¹ 的限制内)，该算法易于理解，是在A上运行时的直接替代，因此数组与通过原始方法获得的数组完全相等.当然，这需要编译器开始工作，并且存在散列冲突的风险(在极少数情况下可能会影响结果).

Judging by the benchmark vs. the other suggestions, my answer doesn't perform as well as one of the alternatives, but I think its raison d'être lies in the fact that it is completely data-type agnostic (within the limitations of the GetMD5¹), that the algorithm is very straightforward to understand, it's a drop-in replacement as it operates on A, and that the resulting array is exactly equal to the one obtained by the original method. Of course this requires a compiler to get working and has a risk of hash collisions (which might affect the result in VERY VERY rare cases).

这是计算机上一次典型运行的结果，其后是代码:

Here are the results from a typical run on my computer, followed by the code:

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 ，但速度较慢.

---

¹ - If more complicated data types need to be hashed, one can use the DataHash FEX submission instead, which is somewhat slower.

这篇关于考虑到每行上所有可能的排列，找到单元格数组的唯一行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！