如何创建 2 列元胞数组的所有排列？

Question

我创建了一个形状为 m x 2 的元胞数组，其中每个元素都是一个形状为 d x d.

的矩阵

例如像这样：

A = cell(8, 2);
for row = 1:8
    for col = 1:2
        A{row, col} = rand(3, 3);
    end
end

更一般地，我可以将A表示如下：

其中每个 A_{ij} 是一个矩阵。

现在，我需要从A的每一行中随机选择一个矩阵，因为A总共有m行，所以最终我会选择m个矩阵，我们称组合.

显然，由于每一行只有两个选择，因此总共有 2^m 种可能的组合。

我的问题是，如何快速得到这些2^m组合？

可以看出，上面的问题实际上是求以下集合的笛卡尔积：

Answer 1

2^m 实际上是一个二进制数，所以我们可以用它们来创建线性索引。您将得到一个包含 1 和 0 的数组，类似于 [1 1 0 0 1 0 1 0 1]，我们可以将其视为列“索引”，使用 0 表示第一列，使用 1 表示第二个。

m = size(A, 1);
% Build all binary numbers and create a logical matrix
bin_idx = dec2bin(0:(2^m -1)) == '1';

row = 3;  % Loop here over size(bin_idx,1) for all possible permutations
linear_idx = [find(~bin_idx(row,:)) find(bin_idx(row,:))+m];
A{linear_idx}  % the combination as specified by the permutation in out(row)

在我的 R2007b 版本上，它几乎可以立即运行 m = 20。

注意：这将占用 m * 2^m 字节的内存来存储 bin_idx。对于 m = 20 只有 20 MB，对于 m = 30 已经有 30 GB，也就是说，您很快就会运行内存不足，而这只是将排列存储为布尔值！如果 m 在你的情况下很大，你无论如何都不能存储所有的可能性，所以我只是 select 一个随机的：

bin_idx = rand(m, 1);  % Generate m random numbers
bin_idx(bin_idx > 0.5) = 1;  % Set half to 1
bin_idx(bin_idx < 0.5) = 0;  % and half to 0

大 m

的旧的、缓慢的答案

perms()¹ gives you all possible permutations of a given set. However, it does not take duplicate entries into account, so you'll need to call unique() 获取唯一行。

unique(perms([1,1,2,2]), 'rows')

ans =

     1     1     2     2
     1     2     1     2
     1     2     2     1
     2     1     1     2
     2     1     2     1
     2     2     1     1

现在唯一剩下的就是以某种方式对所有可能的 1s 和 2s 进行此操作。我建议使用一个简单的循环：

m = 5;
out = [];

for ii = 1:m
    my_tmp = ones(m,1);
    my_tmp(ii:end) = 2;
    out = [out; unique(perms(my_tmp),'rows')];
end

out = [out; ones(1,m)];  % Tack on the missing all-ones row

out =
     2     2     2     2     2
     1     2     2     2     2
     2     1     2     2     2
     2     2     1     2     2
     2     2     2     1     2
     2     2     2     2     1
     1     1     2     2     2
     1     2     1     2     2
     1     2     2     1     2
     1     2     2     2     1
     2     1     1     2     2
     2     1     2     1     2
     2     1     2     2     1
     2     2     1     1     2
     2     2     1     2     1
     2     2     2     1     1
     1     1     1     2     2
     1     1     2     1     2
     1     1     2     2     1
     1     2     1     1     2
     1     2     1     2     1
     1     2     2     1     1
     2     1     1     1     2
     2     1     1     2     1
     2     1     2     1     1
     2     2     1     1     1
     1     1     1     1     2
     1     1     1     2     1
     1     1     2     1     1
     1     2     1     1     1
     2     1     1     1     1
     1     1     1     1     1

注意：我没有初始化 out，这会很慢，尤其是对于大 m。当然 out = zeros(2^m, m) 将是它的最终大小，但您需要在 for 循环中调整索引以说明唯一排列的大小变化。

您可以创建linear indices from out using find()

linear_idx = [find(out(row,:)==1);find(out(row,:)==2)+size(A,1)];
A{linear_idx}  % the combination as specified by the permutation in out(row)

线性索引在 MATLAB 中是 row-major，因此无论何时您需要第 1 列中的矩阵，只需使用其行号，而每当您需要第二列时，使用行号 + size(A,1)，即总行数。

将所有内容组合在一起：

A = cell(8, 2);
for row = 1:8
    for col = 1:2
        A{row, col} = rand(3, 3);
    end
end

m = size(A,1);
out = [];

for ii = 1:m
    my_tmp = ones(m,1);
    my_tmp(ii:end) = 2;
    out = [out; unique(perms(my_tmp),'rows')];
end

out = [out; ones(1,m)];

row = 3;  % Loop here over size(out,1) for all possible permutations
linear_idx = [find(out(row,:)==1).';find(out(row,:)==2).'+m];
A{linear_idx}  % the combination as specified by the permutation in out(row)

¹ 文档中有注释：

perms(v) is practical when length(v) is less than about 10.

如何创建 2 列元胞数组的所有排列？

How to create all permutations of a 2-column cell-array?

matlab

permutation

cell-array

cartesian-product