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

Question

我有以下问题。我需要重现 0 和 1 的所有唯一组合，其中恰好包含 m 个零和恰好 n 个 1。例如，如果我有 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]) 然后使用 unique(A,'rows') 但如果向量的长度超过 10，这真的很耗时。任何人都可以想出更有效的解决方案？

Answer 1

方法 1:

1. 从集合 [0 1] 中生成 m+n 元素的所有“组合”。这可以使用 this approach 高效地完成。

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 步中使用 uint8 值，并在第 2 步结束时转换为 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 中使用 dec2bin 将所有组合生成为从 0 到 2^(m+n)-1 的所有整数的二进制表达式.这会生成一个 char 数组，因此它应该与修改后的方法 1 一样节省内存。然后，步骤 2 应该稍微适应使用 char，并且需要最终转换为数值:

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';