Combination Generator

Thread view:

Scott Dudley - 28 Jun 2005 15:32 GMT

I need an algorithm that will, provided a set of decimal numbers,
identify any combination thereof that add up to N. The size of the set
(array, list, etc.) is unknown.

Seems I recall seeing code for a combination generator in one of my
algorithm books (Sedgwick?) that would fit the bill. Unfortunately, I'm
faced with a challenge at work and my books are at home.

Thanks.

Reply to this Message

Roedy Green - 28 Jun 2005 16:16 GMT

>Seems I recall seeing code for a combination generator in one of my
>algorithm books (Sedgwick?) that would fit the bill. Unfortunately, I'm
>faced with a challenge at work and my books are at home.

see http://mindprod.com/jgloss/combination.html

Signature

Bush crime family lost/embezzled $3 trillion from Pentagon.
Complicit Bush-friendly media keeps mum. Rumsfeld confesses on video.
http://www.infowars.com/articles/us/mckinney_grills_rumsfeld.htm

Canadian Mind Products, Roedy Green.
See http://mindprod.com/iraq.html photos of Bush's war crimes

Reply to this Message

Gordon Beaton - 28 Jun 2005 16:23 GMT

> I need an algorithm that will, provided a set of decimal numbers,
> identify any combination thereof that add up to N. The size of the
> set (array, list, etc.) is unknown.

This is a knapsack problem, a one-dimensional special case of bin
packing. You'll find lots of information, analysis and example code if
you google. AFAIK the problem is NP-complete.

Here's a good heuristic however, from memory:

Choose the largest of your remaining elements that fits in N, and
reduce N accordingly. Repeat until either N is 0, or there are no more
elements that are small enough.

/gordon

Signature

[ do not email me copies of your followups ]
g o r d o n + n e w s @ b a l d e r 1 3 . s e

Reply to this Message

bugbear - 28 Jun 2005 17:24 GMT

> I need an algorithm that will, provided a set of decimal numbers,
> identify any combination thereof that add up to N. The size of the set
[quoted text clipped - 3 lines]
> algorithm books (Sedgwick?) that would fit the bill. Unfortunately, I'm
> faced with a challenge at work and my books are at home.

http://www.nuigalway.ie/mat/algorithms/knapsack.html

BugBear

Reply to this Message

Combination Generator

Free Magazines