我创建了一个形状为 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:
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:
发布评论
评论(1)
2^m
实际上是一个二进制数,因此我们可以使用它们来创建线性索引。您将得到一个包含 1 和 0 的数组,类似于[1 1 0 0 1 0 1 0 1]
,我们可以使用0
0 将其视为列“索引” code> 表示第一列,1
表示第二列。在我的 R2007b 版本上,
m = 20
几乎可以立即运行。注意:这将需要
m * 2^m
字节的内存来存储bin_idx
。对于m = 20
来说,这只是 20 MB,对于m = 30
来说,这已经是 30 GB 了,也就是说,您很快就会耗尽内存,而这只是用于存储排列为布尔值!如果m
在你的情况下很大,你无论如何都无法存储所有的可能性,所以我只是选择一个随机的:旧的,缓慢的大
m
答案perms()
1 为您提供给定的所有可能的排列 放。但是,它不会考虑重复的条目,因此您需要调用unique()
获取唯一的行。现在剩下的唯一一件事就是以某种方式对所有可能数量的
1
和2
执行此操作。我建议使用一个简单的循环:注意:我还没有初始化
out
,这会很慢,尤其是对于大型m
来说。当然out = Zeros(2^m, m)
将是其最终大小,但是您需要在for
循环中调整索引以适应变化独特排列的大小。您可以使用 out 创建线性索引。 com/help/matlab/ref/find.html" rel="nofollow noreferrer">
find()
线性索引在 MATLAB 中以行优先,因此每当您需要列中的矩阵时1、只需使用它的行号,每当需要第二列时,使用行号 +
size(A,1)
,即总行数。将所有内容组合在一起:
1 文档中有一条注释:
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 a0
to indicate the first column and a1
to indicate the second.On my R2007b version this runs virtually instant for
m = 20
.NB: this will take
m * 2^m
bytes of memory to storebin_idx
. Where that's just 20 MB form = 20
, that's already 30 GB form = 30
, i.e. you'll be running out of memory fairly quickly, and that's for just storing permutations as booleans! Ifm
is large in your case, you can't store all of your possibilities anyway, so I'd just select a random one: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 callunique()
to get the unique rows.The only thing left now is to somehow do this over all possible amounts of
1
s and2
s. I suggest using a simple loop:NB: I've not initialised
out
, which will be slow especially for largem
. Of courseout = zeros(2^m, m)
will be its final size, but you'll need to juggle the indices within thefor
loop to account for the changing sizes of the unique permutations.You can create linear indices from
out
usingfind()
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:
1 There's a note in the documentation: