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

发布于 2025-01-16 15:48:07 字数 862 浏览 1 评论 0 原文

我创建了一个形状为 mx 2 的元胞数组,其中每个元素都是形状为 dx 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组合?


可以看出,上述问题实际上是求以下集合的笛卡尔积:

在此处输入图像描述

I created a cell array of shape m x 2, each element of which is a matrix of shape d x d.

For example like this:

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

More generally, I can represent A as follows:

enter image description here

where each A_{ij} is a matrix.

Now, I need to randomly pick a matrix from each row of A, because A has m rows in total, so eventually I will pick out m matrices, which we call a combination.

Obviously, since there are only two picks for each row, there are a total of 2^m possible combinations.

My question is, how to get these 2^m combinations quickly?


It can be seen that the above problem is actually finding the Cartesian product of the following sets:

enter image description here

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

旧伤慢歌 2025-01-23 15:48:07

2^m 实际上是一个二进制数,因此我们可以使用它们来创建线性索引。您将得到一个包含 1 和 0 的数组,类似于 [1 1 0 0 1 0 1 0 1],我们可以使用 00 将其视为列“索引” code> 表示第一列,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 在你的情况下很大,你无论如何都无法存储所有的可能性,所以我只是选择一个随机的:

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()1 为您提供给定的所有可能的排列 放。但是,它不会考虑重复的条目,因此您需要调用 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

现在剩下的唯一一件事就是以某种方式对所有可能数量的 12 执行此操作。我建议使用一个简单的循环:

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 循环中调整索引以适应变化独特排列的大小。

您可以使用 out 创建线性索引。 com/help/matlab/ref/find.html" rel="nofollow noreferrer">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 中以行优先,因此每当您需要列中的矩阵时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)

1 文档中有一条注释:

perms(v)length(v) 小于大约 10 时实用。

2^m is actually a binary number, so we can use those to create linear indices. You'll get an array containing 1s and 0s, something like [1 1 0 0 1 0 1 0 1], which we can treat as column "indices", using a 0 to indicate the first column and a 1 to indicate the second.

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)

On my R2007b version this runs virtually instant for m = 20.

NB: this will take m * 2^m bytes of memory to store bin_idx. Where that's just 20 MB for m = 20, that's already 30 GB for m = 30, i.e. you'll be running out of memory fairly quickly, and that's for just storing permutations as booleans! If m is large in your case, you can't store all of your possibilities anyway, so I'd just select a random one:

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

Old, slow answer for large m

perms()1 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() to get the unique rows.

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

The only thing left now is to somehow do this over all possible amounts of 1s and 2s. I suggest using a simple loop:

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

NB: I've not initialised out, which will be slow especially for large m. Of course out = zeros(2^m, m) will be its final size, but you'll need to juggle the indices within the for loop to account for the changing sizes of the unique permutations.

You can create 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)

Linear indices are row-major in MATLAB, thus whenever you need the matrix in column 1, simply use its row number and whenever you need the second column, use the row number + size(A,1), i.e. the total number of rows.

Combining everything together:

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)

1 There's a note in the documentation:

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

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文