如何有效地计算可能组合的数量（当至少选择一种类型时）？

Question

这是我要解决的练习：

Problem statement

Jack, the pirate finally found the treasure.He found that there were infinite numbers of coins but he can collect only N coins and the coins belong to R different countries (coins will be different for each country). Jack want to collect at least one coin of each country. Find the number of ways the coins can be collected. Assume that coins of same countries can't be distinguished and the order of the coins is irrelevant.

Input
T: Number of test case T lines containing N and R
N: Number of coins jack can collect
R: Number of different countries
Output
For each test case print the number of possibilities of selecting Coins.
Explanation :

In a pile of coins he can only collect 5 coins and there are 3 different coins; Let a, b and c be different coins
(a,a,a,b,c) (a,a,b,b,c) (a,a,b,c,c) (a,b,b,b,c) (a,b,b,c,c) (a,b,c,c,c)
So jack can collect the coins in 6 different ways. Constraint
1<=T<=1000 1<=N<=10 1<=R<=N

我无法编写出一种从数学上找到所有解决方案的方法，所以我尝试了一种蛮力方法，但我认识到这是一种资源浪费，尤其是当 n 很大时。

test_cases = int(input())
for case in range(test_cases):
    solutions = []
    n_r = tuple(map(lambda x: int(x), input().split()))
    n = n_r[0]
    r = n_r[1]
    excess = n - r
    if r >= n:
        print(1)
    else:
        array = [chr(i) for i in range(97, 97 + r)]
        for i in range(10**len(array)):
            digits = list(map(lambda x: int(x), str(i)))
            if sum(digits) == excess:
                solutions.append(i)
        print(len(solutions))

Answer 1

问题可以改写为：

给定 N 个硬币，你需要至少有 R 个不同的硬币和 N-R 个可以任意配置的硬币。

那么$N-R$个币的排列方式就是，你可以这么想。

假设您有 N-R 个圆圈和 R-1 个小棍。对于 R = 5 和 N-R=11

3 - 3 - 5 - 0 - 0
○○○|○○○|○○○○○||

对应A国3币，B国3币，C国5币，D国0币，E国0币

有R-1个可能的位置可以选择将木棍放置在N-R+R-1=N-1个槽位之外，所以总配置就是N-1选择N-R

所以，问题的答案是：在R个插槽中选择R种不同的硬币只有一种可能的配置，在剩下的插槽（N-R插槽）中有N-1个选择N-R个配置。

所以... 1 times N-1 Choose N-R = N-1 Choose N-R.

Answer 2

您将始终包含其中的每一个，而对于其余部分，您需要所有可能的方式 select N - R 硬币，您可以使用 itertools.permutations('ABC', N-R)

import itertools

function Jack(N, R):
    countries = [chr(i) for i in range(97, 97 + R)]
    return [list(p) + countries for p in itertools.permutations(countries, N-R)]

此外，因为您正在处理用户给定的值，所以值得添加一个 assert 来验证输入值：

assert 0 < test_cases < 1000
assert 1 <= N <= 10, 1 <= R <= N

Answer 3

要枚举所有情况，您可以使用 itertools 中的 combinations_with_repetition()。

from itertools import combinations_with_replacement
from string import ascii_lowercase

N = int(input('Number of coins '))
R = int(input('Number of countries '))

bins = [ascii_lowercase[i] for i in range(R)]

for tpl in combinations_with_replacement(bins, N-R):
    result = bins.copy()
    result += tpl

    result.sort()

    print(''.join(result))

N=5，R=3 的结果是：

Number of coins 5
Number of countries 3
aaabc
aabbc
aabcc
abbbc
abbcc
abccc

首先您有 3 个硬币（每个国家一个），剩下 5-3 == 2 个硬币可供选择。公式为：

{2 + (3-1)}! / {2! * (3-1)!} == 4! / (2! * 2!) == (4*3*2) / (2 * 2) == 6

(N-R + R-1)! / ((N-R)! * (R-1)!) == ...

编辑：仅获取方式的数量。

from math import factorial

N = int(input('Number of coins '))
R = int(input('Number of countries '))

print( factorial(N-R + R-1) / (factorial(N-R) * factorial(R-1)))

如何有效地计算可能组合的数量（当至少选择一种类型时）？

How to efficiently calculate number of possible combinations (when selecting at least one of each type)?

python

division

brute-force

python-3.x