CODEWITHSUNDEEP
pythonpython-3.xdivisionbrute-force
Andy
Andy

Reputation: 40

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

This is the exercise I am trying to solve:

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

I couldn't code a way to find all the solutions mathematically, so I tried a brute-force approach, but I recognize it's a wate of resources, especially when n is large.

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))

Upvotes: 0

Views: 339

Answers (3)

Chris Charley
Chris Charley

Reputation: 6633

To enumerate all the cases, you could use combinations_with_repetition() from itertools.

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))

The results from N=5, R=3, are:

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

These results are found by first you have 3 coins (one from each country) and that leaves 5-3 == 2 coins to be chosen. The formula is:

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

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

EDIT: To just get the number of ways.

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)))

Upvotes: 0

Tom
Tom

Reputation: 828

The question can be reworded as:

Given N coins, you need to have at least R coins that are different and N-R coins that can be in a whatever configuration.

The arrangements of $N-R$ coins are then, you can think of this way.

Imagine you have N-R circles and R-1 sticks. For R = 5 and N-R=11

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

which corresponds to 3 coins from country A,3 coins from country B, 5 coins from country C, 0 coins from country D, and 0 coins from country E.

There are R-1 possible positions to choose to place the sticks out of N-R+R-1=N-1 slots, so the total configuration is just N-1 Choose N-R.

So, the answer to the question is: there is only one possible configuration for choosing R different coins in R slots,and there are N-1 Choose N-R configurations in the slots that's left (N-R slots).

So... 1 times N-1 Choose N-R = N-1 Choose N-R.

Upvotes: 2

tituszban
tituszban

Reputation: 5152

You'll always have one of each included, and for the rest, you need all the ways you can select N - R coins, which you can do using 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)]

Also, because you're dealing with user given values, it's worth adding an assert to validate the input values:

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

Upvotes: 0

Related Questions