Message Boards Message Boards

1
|
9597 Views
|
9 Replies
|
9 Total Likes
View groups...
Share
Share this post:

Generate number combinations using KnapsackSolve[] function?

Hello,

I have a problem where there is a list of numbers lets say {2,3,4} and it has to add up to a total of 10. I need to find combinations that add up only to 10. One solution I came up was this:

Module[{total = 10}, 
 Select[Flatten[
   Table[DeleteDuplicates[Sort /@ Tuples[{2, 3, 4}, i]], {i, total}], 
   1], Total[#] === total &]]

Output:

{{2, 4, 4}, {3, 3, 4}, {2, 2, 2, 4}, {2, 2, 3, 3}, {2, 2, 2, 2, 2}}

But, when my input total is large numbers, lets say 100 or more, the Tuples function takes more than 5 mins to get the correct output. So, I figured out, KnapsackSolve[] function solves it. I need help in figuring out its parameters.

KnapsackSolve[{2, 3, 4}, 100]
{50, 0, 0}
KnapsackSolve[{2, 3, 4}, 987687]
{493842, 1, 0}

Since this function can crunch big numbers in no time at all, how do I use this to generate combinations? The documentation has <= in the for max totals parameters.
POSTED BY: Manjunath Babu
9 Replies
Sort By:

"Combinatorial enumeration" is one term that covers this area. Also check "generating functions".
POSTED BY: Daniel Lichtblau

Also, if all that is needed is the count rather than specific solutions, one can go well beyond methods that provide solutions (which of course incurs a memory and speed hit).

countCombos[n_, vals_] := Module[{x},
  SeriesCoefficient[1/Apply[Times, 1 - x^(vals)], {x, 0, n}]
  ]

Example:

AbsoluteTiming[countCombos[10^4, {5, 11, 14, 19}]]

(* Out[3]= {3.385363, 11476034} *)
POSTED BY: Daniel Lichtblau

Interesting! What's the name of the theory behind this?
POSTED BY: Sander Huisman
Okkes Dulgerci
Okkes Dulgerci
Posted 7 years ago

Partition in number theory
POSTED BY: Okkes Dulgerci
Okkes Dulgerci
Okkes Dulgerci
Posted 7 years ago 
Coefficient[ Sum[x^(2 i), {i, 0, 100}] Sum[x^(3 i), {i, 0, 100}] Sum[x^(4 i), {i, 0, 100}] // Expand, x^100]
POSTED BY: Okkes Dulgerci

Could use FrobeniusSolve. By default this will give all solutions.

FrobeniusSolve[{2, 3, 4}, 100]

(* Out[954]= {{0, 0, 25}, {0, 4, 22}, {0, 8, 19}, {0, 12, 16}, {0, 16, 
  13}, {0, 20, 10}, {0, 24, 7}, {0, 28, 4}, {0, 32, 1}, {1, 2, 
  23}, {1, 6, 20}, {1, 10, 17}, {1, 14, 14}, {1, 18, 11}, {1, 22, 
  8}, {1, 26, 5}, {1, 30, 2}, {2, 0, 24}, {2, 4, 21}, {2, 8, 18}, {2, 
  12, 15}, {2, 16, 12}, {2, 20, 9}, {2, 24, 6}, {2, 28, 3}, {2, 32, 
  0}, {3, 2, 22}, {3, 6, 19}, {3, 10, 16}, {3, 14, 13}, {3, 18, 
  10}, {3, 22, 7}, {3, 26, 4}, {3, 30, 1}, {4, 0, 23}, {4, 4, 20}, {4,
   8, 17}, {4, 12, 14}, {4, 16, 11}, {4, 20, 8}, {4, 24, 5}, {4, 28, 
  2}, {5, 2, 21}, {5, 6, 18}, {5, 10, 15}, {5, 14, 12}, {5, 18, 
  9}, {5, 22, 6}, {5, 26, 3}, {5, 30, 0}, {6, 0, 22}, {6, 4, 19}, {6, 
  8, 16}, {6, 12, 13}, {6, 16, 10}, {6, 20, 7}, {6, 24, 4}, {6, 28, 
  1}, {7, 2, 20}, {7, 6, 17}, {7, 10, 14}, {7, 14, 11}, {7, 18, 
  8}, {7, 22, 5}, {7, 26, 2}, {8, 0, 21}, {8, 4, 18}, {8, 8, 15}, {8, 
  12, 12}, {8, 16, 9}, {8, 20, 6}, {8, 24, 3}, {8, 28, 0}, {9, 2, 19},
  {9, 6, 16}, {9, 10, 13}, {9, 14, 10}, {9, 18, 7}, {9, 22, 4}, {9, 
  26, 1}, {10, 0, 20}, {10, 4, 17}, {10, 8, 14}, {10, 12, 11}, {10, 
  16, 8}, {10, 20, 5}, {10, 24, 2}, {11, 2, 18}, {11, 6, 15}, {11, 10,
   12}, {11, 14, 9}, {11, 18, 6}, {11, 22, 3}, {11, 26, 0}, {12, 0, 
  19}, {12, 4, 16}, {12, 8, 13}, {12, 12, 10}, {12, 16, 7}, {12, 20, 
  4}, {12, 24, 1}, {13, 2, 17}, {13, 6, 14}, {13, 10, 11}, {13, 14, 
  8}, {13, 18, 5}, {13, 22, 2}, {14, 0, 18}, {14, 4, 15}, {14, 8, 
  12}, {14, 12, 9}, {14, 16, 6}, {14, 20, 3}, {14, 24, 0}, {15, 2, 
  16}, {15, 6, 13}, {15, 10, 10}, {15, 14, 7}, {15, 18, 4}, {15, 22, 
  1}, {16, 0, 17}, {16, 4, 14}, {16, 8, 11}, {16, 12, 8}, {16, 16, 
  5}, {16, 20, 2}, {17, 2, 15}, {17, 6, 12}, {17, 10, 9}, {17, 14, 
  6}, {17, 18, 3}, {17, 22, 0}, {18, 0, 16}, {18, 4, 13}, {18, 8, 
  10}, {18, 12, 7}, {18, 16, 4}, {18, 20, 1}, {19, 2, 14}, {19, 6, 
  11}, {19, 10, 8}, {19, 14, 5}, {19, 18, 2}, {20, 0, 15}, {20, 4, 
  12}, {20, 8, 9}, {20, 12, 6}, {20, 16, 3}, {20, 20, 0}, {21, 2, 
  13}, {21, 6, 10}, {21, 10, 7}, {21, 14, 4}, {21, 18, 1}, {22, 0, 
  14}, {22, 4, 11}, {22, 8, 8}, {22, 12, 5}, {22, 16, 2}, {23, 2, 
  12}, {23, 6, 9}, {23, 10, 6}, {23, 14, 3}, {23, 18, 0}, {24, 0, 
  13}, {24, 4, 10}, {24, 8, 7}, {24, 12, 4}, {24, 16, 1}, {25, 2, 
  11}, {25, 6, 8}, {25, 10, 5}, {25, 14, 2}, {26, 0, 12}, {26, 4, 
  9}, {26, 8, 6}, {26, 12, 3}, {26, 16, 0}, {27, 2, 10}, {27, 6, 
  7}, {27, 10, 4}, {27, 14, 1}, {28, 0, 11}, {28, 4, 8}, {28, 8, 
  5}, {28, 12, 2}, {29, 2, 9}, {29, 6, 6}, {29, 10, 3}, {29, 14, 
  0}, {30, 0, 10}, {30, 4, 7}, {30, 8, 4}, {30, 12, 1}, {31, 2, 
  8}, {31, 6, 5}, {31, 10, 2}, {32, 0, 9}, {32, 4, 6}, {32, 8, 
  3}, {32, 12, 0}, {33, 2, 7}, {33, 6, 4}, {33, 10, 1}, {34, 0, 
  8}, {34, 4, 5}, {34, 8, 2}, {35, 2, 6}, {35, 6, 3}, {35, 10, 
  0}, {36, 0, 7}, {36, 4, 4}, {36, 8, 1}, {37, 2, 5}, {37, 6, 2}, {38,
   0, 6}, {38, 4, 3}, {38, 8, 0}, {39, 2, 4}, {39, 6, 1}, {40, 0, 
  5}, {40, 4, 2}, {41, 2, 3}, {41, 6, 0}, {42, 0, 4}, {42, 4, 1}, {43,
   2, 2}, {44, 0, 3}, {44, 4, 0}, {45, 2, 1}, {46, 0, 2}, {47, 2, 
  0}, {48, 0, 1}, {50, 0, 0}} *)

Or Reduce.

Reduce[{2 x + 3 y + 4 z == 100, 0 <= x, 0 <= y, 0 <= z}, {x, y, z}, Integers]

(* (x == 0 && y == 2 && z == 1) || (x == 1 && y == 0 && 
   z == 2) || (x == 2 && y == 2 && z == 0) || (x == 3 && y == 0 && 
   z == 1) || (x == 5 && y == 0 && z == 0) *)

Also there is IntegerPartitions.

Map[Tally, IntegerPartitions[10, Infinity, {2, 3, 4}]]

(* Out[959]= {{{4, 2}, {2, 1}}, {{4, 1}, {3, 2}}, {{4, 1}, {2, 3}}, {{3, 
   2}, {2, 2}}, {{2, 5}}} *)
POSTED BY: Daniel Lichtblau
Wilson Kan
Wilson Kan, WOLFRAM
Posted 7 years ago

It sounds like you are actually solving an integer partition problem. For your example adding to 10:

IntegerPartitions[10, \[Infinity], {2, 3, 4}]
POSTED BY: Wilson Kan

Thank you so much. This is the best and most efficient solution I was looking for.
POSTED BY: Manjunath Babu

If you only need one solution, then I suggest doing it as an integer programming problem, with binary variables describing whether or not a number is included in the sum.

POSTED BY: Frank Kampas
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract