考虑每行的所有可能排列，查找元胞数组的唯一行
Find unique rows of a cell array considering all possible permutations on each row
我有维度 m * k 的元胞数组 A。
我想保持 A 的行唯一 直到 k 个单元格的顺序 。
"tricky" 部分是 "up to an order of the k cells"：考虑 i 第 i 行的 A 单元格=], A(i,:);可能有一行 j of A, 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,:)=[];
可以用，但是太慢了。我希望我可以使用更快的东西。
陈述问题： 识别数组中唯一行的理想选择是使用 C = unique(A,'rows')。但是这里有两个主要问题，阻止我们在这种情况下使用这个功能。首先是您希望在与其他行进行比较时计算每一行的所有可能排列。如果 A 有 5 列，这意味着每行检查 120 个不同的重新排列！ 听起来不可能。
第二个问题与unique本身有关；它does not accept cells except cell arrays of character vectors。所以你不能简单地将 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.
我的解决方案：
- 生成另一个包含相同单元格的元胞数组，但转换为字符串 (
STR)。
- 在那里找到所有唯一元素的索引 (
id)。
- 生成具有唯一索引的关联矩阵并对行进行排序 (
IC)。
- 查找唯一行（
rows）。
- 收集
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.
中的列数几乎不敏感
看来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));
Update：以上方法效果最好，但是如果想要从 G 以外的 A 获取 A1，我建议使用基于 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.
我想提出另一个想法，它在概念上与 . My idea uses hash functions, and specifically, the GetMD5 FEX submission 有一些相似之处。
主要任务是如何将A中的每一行"reduce"化为一个单一的代表值（比如字符向量），然后找到这个向量的唯一条目。
从基准对比其他建议来看，我的答案不如其中一种选择，但我认为它的 raison d'être 在于事实上，它完全与数据类型无关（在 GetMD51 的限制内），该算法非常易于理解，它是一个替代品，因为它对 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));
1 - 如果需要散列更复杂的数据类型，可以使用 DataHash FEX submission 来代替，这会稍微慢一些。
我有维度 m * k 的元胞数组 A。
我想保持 A 的行唯一 直到 k 个单元格的顺序 。
"tricky" 部分是 "up to an order of the k cells"：考虑 i 第 i 行的 A 单元格=], A(i,:);可能有一行 j of A, 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,:)=[];
可以用，但是太慢了。我希望我可以使用更快的东西。
陈述问题： 识别数组中唯一行的理想选择是使用 C = unique(A,'rows')。但是这里有两个主要问题，阻止我们在这种情况下使用这个功能。首先是您希望在与其他行进行比较时计算每一行的所有可能排列。如果 A 有 5 列，这意味着每行检查 120 个不同的重新排列！ 听起来不可能。
第二个问题与unique本身有关；它does not accept cells except cell arrays of character vectors。所以你不能简单地将 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.
我的解决方案：
- 生成另一个包含相同单元格的元胞数组，但转换为字符串 (
STR)。 - 在那里找到所有唯一元素的索引 (
id)。 - 生成具有唯一索引的关联矩阵并对行进行排序 (
IC)。 - 查找唯一行（
rows）。 - 收集
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.
看来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));
Update：以上方法效果最好，但是如果想要从 G 以外的 A 获取 A1，我建议使用基于 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.
我想提出另一个想法，它在概念上与 GetMD5 FEX submission 有一些相似之处。
主要任务是如何将A中的每一行"reduce"化为一个单一的代表值（比如字符向量），然后找到这个向量的唯一条目。
从基准对比其他建议来看，我的答案不如其中一种选择，但我认为它的 raison d'être 在于事实上，它完全与数据类型无关（在 GetMD51 的限制内），该算法非常易于理解，它是一个替代品，因为它对 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));
1 - 如果需要散列更复杂的数据类型，可以使用 DataHash FEX submission 来代替，这会稍微慢一些。