3
$\begingroup$

My question is about choosing a subset of combinations within a list, based on a condition.

Fot example, a shop sells 26 products. The name of a product starts with a letter. Each product has a price. For example, the customer pays 1 dollar for product 'a'. The product-price range for this shop looks like:

shop = {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 6}, {g, 7}, {h, 
   8}, {i, 9}, {j, 10}, {k, 11}, {l, 12}, {m, 13}, {n, 14}, {o, 
   15}, {p, 16}, {q, 17}, {r, 18}, {s, 19}, {t, 20}, {u, 21}, {v, 
   22}, {w, 23}, {x, 24}, {y, 25}, {z, 26} };

A customers visit a store with 30 dollar in his pocket.The customer wants to know all combinations of products he can buy for 30 dollar, or less.

For example: {{z, 26},{d, 4}},{{z, 26},{c, 3}},{{z, 26},{b, 2}}....{{j, 10},{t, 20}}

I tried to use 'Subsets' to find als possible combinations. Then I get a error:

test = Subsets[shop];
test1 = {#, Sum[i, {i, #}]} & /@ test;
Select[test1[[All, 2]][[2 ;; -1]], #[[2]] < 30 &]

$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation.

When I made a smaller selection (for example the first 8 products) it works fine.

test = Subsets[shop[[1 ;; 8]]];
test1 = {#, Sum[i, {i, #}]} & /@ test;
Select[test1[[All, 2]][[2 ;; -1]], #[[2]] < 30 &]

Who has a solution for this problem? Or a different approach?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

The key part here is using FrobeniusSolve.

shop = {{a,1},{b,2},{c,3},{d,4},{e,5},{f,6},{g,7},{h,8},{i,9},{j,10},{k,11},{l,12},{m,13},{n,14},{o,15},{p,16},{q,17},{r,18},{s,19},{t,20},{u,21},{v,22},{w,23},{x,24},{y,25},{z,26}};

money = 30;
(*All combos with possibly multiple of each*)FrobeniusSolve[shop[[;; , 2]], money];
(*If the store only has one of each item*) Pick[shop, #, 1] & /@ Select[%, Max[#]==1 &]

{{{n, 14}, {p, 16}}, {{m, 13}, {q, 17}}, <<288>>, {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 6}, {i, 9}}}

$\endgroup$
2
  • $\begingroup$ Nice answer, Thanks. In the case, de prices are not integers,for example shop = {{a,1.1},{b,2.2},{c,3.3},{d,4.4},{e,5.5},{f,6.6}}, this formula doesn't work. What do you suggest for this situations? $\endgroup$ Dec 3, 2021 at 8:24
  • $\begingroup$ @MichielvanMens Sorry for the late response, but I would first convert everything to pennies so you're working with integers again and can still use FrobeniusSolve. Then, as a first approach, I would simply map over the range (i.e. one by one). I did a quick and dirty test and it was actually rather quick. $\endgroup$ Dec 12, 2021 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.