1

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.

Szymek
  • 69
  • 9
  • Can you please provide the output you expect? – jkr Oct 02 '20 at 21:49
  • Please give a couple of examples to clarify what does, and does not, matter in price placement. – Prune Oct 02 '20 at 21:52
  • 1
    Do the separate buckets make any difference? I don't see any difference between `ABCDEFG` and three separate buckets `ABC` and `DE` and `FG`. – John Gordon Oct 02 '20 at 21:58
  • The goal is to maximise bargain we can get. Assume that the more items we have in bucket, the more discount we get for the cheapest item in one bucket. Let's say we get 10% off when 2 items are in bucket, 20% when 3 items are in bucket and so on. However, it might be worth to split items into few buckets instead of buying all in a single bucket to get higher bargain. – Szymek Oct 02 '20 at 22:08
  • It's unclear whether the order of the items within the 3/2/2 matter. If order does matter, then @YossiLevi's solution is just fine. If order doesn't matter, then you need to pull out three elements using itertools.combinations, and then handle either the other four elements using a nested itertools.combinations. – Frank Yellin Oct 02 '20 at 22:13
  • I read "It does not matter whether the price is placed inside the same bucket" as "the order in buckets does not matter" – Lesiak Oct 02 '20 at 22:17

2 Answers2

1

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

Doot
  • 555
  • 5
  • 15
  • 1
    The first part of the answer is something I was looking for. We don't care about the order in the single bucket (inside tuple). Great one liner. – Szymek Oct 03 '20 at 07:55
0

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.

Lesiak
  • 22,088
  • 2
  • 41
  • 65