我可以用多少种方式将 "n" 糖果分发给 3 children，这样每人至少得到 1 糖果，并且至少 1 child 应该比其他人得到更多

Question

我可以用多少种不同的方式将“n”个糖果分发给 m = 3 children，这样每个人至少得到 1 个糖果，并且至少 1 个 child 应该比其他人得到更多的糖果？

例如：糖果数量 = 6，总方式 = 9
[1,4,1] , [1,1,4] , [4,1,1] , [1,2,3] , [1,3,2] 等等....总方式 = 9 .

我的代码在Python:

import itertools

n = int(input())
arr = []

for i in range(1,n+1):
    for j in range(1, n+1):
        for k in range(1,n+1):
            if (i+j+k == n) and (i!=j or j!=k):
                if sorted(list(set(itertools.permutations([i,j,k],3)))) not in arr:
                    arr.append(sorted(list(set(itertools.permutations([i,j,k],3)))))

print(arr)       
arr1 = [arr[i][j] for i in range(len(arr)) for j in range(len(arr[i]))]
print(arr1)
print(len(arr1))

我自己解决了这个问题，尽管我对高级编程还比较陌生，而且我知道我的代码没有经过优化。我想优化它，并使用列表理解在一行中列出不同的方式。

我的列表理解有误：

arr = [sorted(list(set(itertools.permutations([i,j,k],3))) if ((i+j+k == n) and (i!=j or j!=k) and sorted(list(set(itertools.permutations([i,j,k],3))))) not in arr for i in range(1,n+1) for j in range(1, n+1) for k in range(1,n+1)]

如有任何帮助，我们将不胜感激！

Answer 1

我建议您避免过多的嵌套条件和循环。您是否有理由希望您的答案涉及列表理解？我也喜欢使用它们，但超过一定程度它们就会变得太长，嗯……无法理解。这是一个替代解决方案，它使用更少的循环，避免长列表理解并且更易于阅读——至少在我看来是这样。

In [29]: from itertools import permutations, combinations_with_replacement

In [30]: def all_valid_permutations(candies, members):
    ...:     combos = combinations_with_replacement(range(1, candies), members)
    ...:     valid_permutations = set()
    ...:     for item in combos:
    ...:         for perm in permutations(item):
    ...:             if sum(perm) == candies and len(set(perm)) >= members-1:
    ...:                 valid_permutations.add(perm)
    ...:
    ...:     return valid_permutations
    ...:

In [31]: all_valid_permutations(6, 3)
Out[31]:
{(1, 1, 4),
 (1, 2, 3),
 (1, 3, 2),
 (1, 4, 1),
 (2, 1, 3),
 (2, 3, 1),
 (3, 1, 2),
 (3, 2, 1),
 (4, 1, 1)}

如果您了解基本组合学，您可以猜出导入函数的作用。（或者您可以阅读 docs，如果您愿意的话。）不过，在不完全了解您的用例的情况下，我无法保证性能。这只是一个快速的解决方案，不在我的脑海中。我打赌你可以进一步优化它。

Answer 2

由于您只需要方法的数量而不是所有组合，因此这看起来更像是数学问题而不是编程问题。

分配n个糖果给m children的方法的数量，其中所有children至少得到1个糖果，就是(n - 1)C(m - 1)。有关原因的详细解释，请阅读本页最后一节：https://brilliant.org/wiki/identical-objects-into-distinct-bins/#distribution-into-non-empty-bins

“至少1个child应该比其他人得到更多的糖果”也可以理解为“并非所有child人应该有相同数量的糖果”。这样的话，我们只需要在计算的路数中减去所有children拥有相同数量糖果的情况即可，如果糖果数量是children数量的倍数.

from math import comb

n = 6
m = 3

numberOfWays = comb(n - 1, m - 1) - 1 if n % m == 0 else 0
print(numberOfWays)

我可以用多少种方式将 "n" 糖果分发给 3 children，这样每人至少得到 1 糖果，并且至少 1 child 应该比其他人得到更多

In how many ways can I distribute "n" candies to 3 children such that each gets at least 1 candy and at least 1 child should get more than others

python

arrays

combinations

list-comprehension

permutation