枚举n个球到k个盒子的所有可能分布

Question

我所指的确切问题和问题的分布数量已计算 here。我有兴趣明确了解这些分布。

例如，有 5 个球和 3 个盒子：一种分布是盒子 1 中有 2 个球，盒子 2 中有 2 个球，盒子 3 中有 1 个称为 221。现在我想列出所有这些可能的分布: -

212

131

104

。 . .

一种方法是我运行 matlab 命令：perms([0,0,0,0,0,1,1,1])。这基本上生成了 5 个球和 2 个棍子的所有排列。但由于命令 perms 无法识别相同的对象，因此存在大量多算。

Answer 1

您可以使用 unique() 删除由 perms():

生成的相同行

A = unique(perms([0,0,0,0,0,1,1,1]), 'rows');
% `A` will contain all combinations, not permutations, of [0,0,0,0,0,1,1,1]

Answer 2

很简单……有点像。

function alloc(balls, boxes):

    if boxes = 1
        return [balls]
    else
       for n in range 0:balls
           return alloc(balls-n, boxes-1)

这是基本的递归逻辑：选择每个可能数量的球，然后对剩余的球进行递归并减少一个盒子。

列表粘合方法将依赖于语言；我把它们留给学生作为练习。

枚举n个球到k个盒子的所有可能分布

Enumerate all possible distributions of n balls into k boxes

algorithm

matlab

combinations

permutation

combinatorics