CODEWITHSUNDEEP
pythonpython-3.xcombinations
Szymek
Szymek

Reputation: 69

How to generate all possible combinations of given length

Assume we have a list of prices items_prices = [1500, 2000, 1600, 2100, 2200, 1400, 1900].

We want to find all the possible combinations of putting all 7 prices into buckets containing the following number of prices in each bucket [3, 2, 2]. It does not matter whether the price is placed inside the same bucket, but it does matter to which bucket price is placed.

How to do this? I found this answer, but it assumes we are interested only in one combination of r length subsequence of given elements. However here, we are also interested in the remains after the first combination containing 3 prices, then 2 and lastly 2.

Please note that the 7 prices and the combination in the given bucket is a simple case of a general problem.

Upvotes: 1

Views: 442

Answers (2)

Doot
Doot

Reputation: 745

I may have interpreted this incorrectly, and will edit this answer if I have, but I'm assuming that the order within a single group of does not matter.

If so, there are 7C5 = 21 unique ways (e.g. in group of 3, [1500, 2000, 1600] is the same as [2000, 1600, 1500]). I simply do all the unique combinations (not permutations) of selecting 5 prices from 7, then split that 5 into a 3 and 2, then append the remaining 2 values not picked as the 3rd group (in either order).

They are:

((1600, 1400, 1900), (2000, 2100), (2200, 1500))
((1600, 1400, 1900), (2000, 2200), (1500, 2100))
((1600, 1400, 1900), (2000, 1500), (2200, 2100))
((1600, 1400, 1900), (2100, 2200), (2000, 1500))
((1600, 1400, 1900), (2100, 1500), (2000, 2200))
((1600, 1400, 1900), (2200, 1500), (2000, 2100))
((1600, 1400, 2000), (2100, 2200), (1500, 1900))
((1600, 1400, 2000), (2100, 1500), (2200, 1900))
((1600, 1400, 2000), (2200, 1500), (1900, 2100))
((1600, 1400, 2100), (2200, 1500), (2000, 1900))
((1600, 1900, 2000), (2100, 2200), (1400, 1500))
((1600, 1900, 2000), (2100, 1500), (1400, 2200))
((1600, 1900, 2000), (2200, 1500), (1400, 2100))
((1600, 1900, 2100), (2200, 1500), (1400, 2000))
((1600, 2000, 2100), (2200, 1500), (1400, 1900))
((1400, 1900, 2000), (2100, 2200), (1600, 1500))
((1400, 1900, 2000), (2100, 1500), (1600, 2200))
((1400, 1900, 2000), (2200, 1500), (1600, 2100))
((1400, 1900, 2100), (2200, 1500), (1600, 2000))
((1400, 2000, 2100), (2200, 1500), (1600, 1900))
((1900, 2000, 2100), (2200, 1500), (1600, 1400))

Calculated from

[(chosen_5[:3], chosen_5[3:5], tuple(set(items_prices) - set(chosen_5))) for chosen_5 in tuple(itertools.combinations(items_prices, 5))]

Note that in all 3 tuples, the actual values are not all the same, even if the order is different since we don't care what order the values are in - we can treat the 3 tuples in each order as 3 (frozen) sets.

However, if you meant that the ordering in the individual groups does matter, then there are 7! = 5040 possible permutations, which is the same as picking any 1 of 7 then after that, any 1 of the 6 remaning (since you've picked one out) then 1 of 5... down to the last 1. They can all be calculated using

[(this_permutation[:3], this_permutation[3:5], this_permutation[5:]) for this_permutation in itertools.permutations(items_prices)]

((1500, 2000, 1600), (2100, 2200), (1400, 1900))
((1500, 2000, 1600), (2100, 2200), (1900, 1400))
((1500, 2000, 1600), (2100, 1400), (2200, 1900))
((1500, 2000, 1600), (2100, 1400), (1900, 2200))
((1500, 2000, 1600), (2100, 1900), (2200, 1400))
((1500, 2000, 1600), (2100, 1900), (1400, 2200))
((1500, 2000, 1600), (2200, 2100), (1400, 1900))
((1500, 2000, 1600), (2200, 2100), (1900, 1400))
((1500, 2000, 1600), (2200, 1400), (2100, 1900))
((1500, 2000, 1600), (2200, 1400), (1900, 2100))
((1500, 2000, 1600), (2200, 1900), (2100, 1400))
((1500, 2000, 1600), (2200, 1900), (1400, 2100))
...

Note that the first and second tuple are distinct because the 2200 and 1500 are in a different order, which would not be distinguished in the other output using combinations not permutations

Upvotes: 1

Lesiak
Lesiak

Reputation: 25966

Firstly, the answer you posted does not assume anything. 'Combination' is a well-defined term. See https://mathworld.wolfram.com/Combination.html

Secondly, I would approach the problem as follows (in pseudo-code):

  • generate list of all indices from 0 to len(items_prices) - 1
  • generate a list of all combinations of length 3 from the given indices (using the formal definition of Combination and itertools.combinations function you linked).
  • for each generated combination:
    • remove the selected indices
    • generate combinations for the next bucket (in your example of length 2) out of remaining list of indices

carry on as long as you have no buckets left.

I used indices instead of elements to handle the cases where prices may be duplicated on input. If you have a constraint that they are different, you may use the actual values.

Upvotes: 0

Related Questions