How to use itertools to solve the problem of unordered permutation and combination
- 2020-06-01 10:15:45
- OfStack
Recently, I started to fight for Codewars as a rookie of Python, so I plan to write down the interesting questions I met here. Today's first question is called "Best Travel" :
John and Mary plan to travel to some small towns. Mary has listed the distances between these towns as ls=[50, 55, 57, 58, 60]. But John didn't want to drive too hard, so they made two requirements: 1) drive no more than a certain distance, t=174, miles 2) only go to three towns.
Which three towns would satisfy both John and Mary? (find the 3 towns whose distances are closest to or equal to t)
The question can be abstracted as:
Enter a list of integers ls and t:
1. Find all combinations of any three elements from ls
2. Calculate the sum of the three elements of each combination
3. If there is a sum less than or equal to t, then select the largest from it and output the combination of the largest and the corresponding 3 elements
4. If it doesn't exist, you have to return None
Key points of implementation:
1. Disordered permutation and combination:
Use the combinations method of the itertools module
2. The sum:
Using sum function
3. Maximum value:
Using max function
4. Catch exceptions:
Use try - except
To borrow an best solution from this 1 question, the implementation code is:
def choose_best_sum(t, k, ls):
import itertools
try:
return max(sum(combination) for combination in itertools.combinations(ls, k) if sum(combination) <= t)
except:
return None