matlab - 在 Matlab 中随机选择所有可能组合的子集？

Question

我需要从一组 n 个元素中选择 k 个元素的随机组合，其中 n 可能相当大。鉴于集合的大小，简单地使用 combnk 或 nchoosek 生成所有可能的组合，并从中随机选择是不可行的。

有没有一种简单的方法可以生成这些组合的 M 个唯一随机子集？

当 n 很小时，以下工作:

M = 20; %want to pick M random combinations
n = 10; %number of elements 
k = 5;  %number of elements in each combination
allCombos = nchoosek([1:n], k);  %for large n this is not feasible
numCombos = nchoosek(n,k);
permutationsToUse = randperm(numCombos, M);
randomCombos = allCombos(permutationsToUse, :);

当 n 很大时，这不再可行。

相关帖子

Retrieve a specific permutation without storing all possible permutations in Matlab

How to randomly pick a number of combinations from all the combinations efficiently?

Select a subset of combinations

Answer 1

您可以尝试使用 randi 并生成从 1 到 Nelements 的 7 个整数的随机组合，然后检查您是否只有唯一的组合:

Nelements=100;
M=10;
combsubset=randi(Nelements,[M 7]);
combsubset=unique(combsubset,'rows');

如果你想得到恰好 M 的组合，你可以使用一个循环:

Nelements=100;
M=10;
combsubset=[];
while(size(combsubset,1)<M)
    combsubset=[combsubset;randi(Nelements,[M 7])];
    combsubset=unique(combsubset,'rows');
end
combsusbet=combsubset(1:M,:);

如果您想重用它来获得其他组合，您几乎可以使用相同的代码:

Nelements=100;
Mtotal=20
M=10;
while(size(combsubset,1)<Mtotal)
    combsubset=[combsubset;randi(Nelements,[M 7])];
    combsubset=unique(combsubset,'rows');
end
combsusbet=combsubset(1:Mtotal,:);

编辑:满足您需求的另一种方法是对组合进行排序，使其只能获得给定的子集。可以通过以下示例解释一种排序方法:如果您有三个索引 i、j、k，范围从 0 到 N-1，您可以使用唯一索引 n=i*N*N+j*N +k 遍历所有可能性。然后如果你想得到第n个向量:

k=mod(n,N);
j=mod((n-k)/N,N);
i=mod((((n-k)/N)-j)/N,N);

我不知道您是否会觉得这更优雅，但借助一个使用递归的小函数，您可以轻松获得组合的固定子集。