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

    return max(sum(combination) for combination in itertools.combinations(ls, k) if sum(combination) <= t)
    return None

Related articles: