如何生成n类球中选取k个的可重复无顺序组合？

Your current code is generating ordered combinations (permutations with repetition)—that's why you're seeing pairs like 1 2 and 2 1 as distinct entries. What you need are unordered combinations with repetition, where the order doesn't matter and duplicates are allowed (sometimes called "multisets").

Why Your Current Code Fails #

The line nchoosek(repmat(1:n, 1, n), k) picks k elements from a list that repeats each number n times. This includes all possible ordered selections, so both [1,2] and [2,1] get included. The unique function can't fix this because those are different rows in the matrix.

The Correct Approach: Using Stars and Bars Theorem #

A mathematical trick here is that combinations with repetition of n elements taken k at a time are equivalent to combinations of n + k - 1 elements taken k at a time (without repetition). We can convert these "standard" combinations into the repeated ones we want by adjusting the values.

Here's the code that will give you exactly the result you want:

n = 3; % Number of ball types
k = 2; % Number of balls to pick

% Step 1: Generate standard combinations of (n+k-1) elements taken k at a time
standard_combs = nchoosek(1:n+k-1, k);

% Step 2: Convert to combinations with repetition
result = standard_combs - repmat(0:k-1, size(standard_combs,1), 1);

Let's Test It with Your Example #

For n=3 and k=2:

• n+k-1 = 4, so standard_combs is:

  1 2
  1 3
  1 4
  2 3
  2 4
  3 4
  

• Subtracting [0,1] from each row gives:

  1 1
  1 2
  1 3
  2 2
  2 3
  3 3
  

Which is exactly the output you expected!

Alternative: Generating Non-Decreasing Sequences #

If you prefer a more intuitive (though less efficient) approach, you can generate all sequences where each element is greater than or equal to the previous one. Here's a quick loop-based method for small values of n and k:

result = [];
for i1 = 1:n
    for i2 = i1:n
        % Add more nested loops for larger k values
        result = [result; i1 i2];
    end
end

This works for k=2, but you'd need to add nested loops for larger k values. The first method is better for bigger n and k since it avoids nested loops.

内容的提问来源于stack exchange，提问作者Sophie Garcia