给定元素集的唯一(有限长度)组合 - 在Matlab中实现

Question

我有以下问题.我需要重现0和1的所有独特组合,包括正好m个零和正好n个.例如,如果我有2个零和3个,我正在寻找的组合是以下10个:

1)0 0 1 1 1

2)0 1 0 1 1

3)0 1 1 0 1

4)0 1 1 1 0

5)1 0 0 1 1

6)1 0 1 0 1

7)1 0 1 1 0

8)1 1 0 0 1

9)1 1 0 1 0

10)1 1 1 0 0

现在,我使用A = perms([0 0 1 1 1])然后使用唯一(A,'rows')但如果向量的长度大于10,这实在是非常耗时.任何人都可以想到更高效的解决方案

Answer 1

方法一：

1. m+n生成从集合中取出的元素的所有“组合” [0 1]。使用这种方法可以有效地完成此任务。

2. 仅保留那些包含 的组合n。

代码：

m = 7; %// number of zeros
n = 9; %// number of ones
L = m+n;
vectors = repmat({[0 1]}, 1, L);
combs = cell(1,L);
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1});
combs = cat(L+1, combs{:});
combs = reshape(combs,[],L);
combs = combs(sum(combs,2)==n,:);

结果示例m=2; n=3：

combs =
     0     0     1     1     1
     0     1     0     1     1
     0     1     1     0     1
     0     1     1     1     0
     1     0     0     1     1
     1     0     1     0     1
     1     0     1     1     0
     1     1     0     0     1
     1     1     0     1     0
     1     1     1     0     0

方法1修改

为了节省内存，请使用步骤 1 中的值，并在步骤 2 结束时uint8转换为：double

m = 7; %// number of zeros
n = 9; %// number of ones
L = m+n;
vectors = repmat({uint8([0 1])}, 1, L);
combs = cell(1,L);
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1});
combs = cat(L+1, combs{:});
combs = reshape(combs,[],L);
combs = double(combs(sum(combs,2)==n,:));

方法2：

与方法 1 类似，但在步骤 1 中，使用生成所有组合作为从0到 的所有整数的二进制表达式。这会生成一个数组，因此它应该与修改后的方法 1 一样节省内存。然后，步骤 2 应稍微调整以使用s，并且需要最终转换为数值：2^(m+n)-1dec2bincharchar

m = 7; %// number of zeros
n = 9; %// number of ones
combs = dec2bin(0:2^(m+n)-1);
combs = combs(sum(combs=='1',2)==n,:)-'0';