distribution algorithm question

Discussion in 'C Programming' started by Koen, Aug 11, 2003.

  1. Koen

    Koen Guest

    Hi,

    I am looking for an algorithm that figures out which numbers from a
    given set add up to another number. I am sure this has been done
    before, but I have no idea how such a calculation is called, which
    kind of limits my further searching.

    An example. The set contains the numbers 1-2-3-4-5. Now the algorithm
    should calculate all possible combinations of these numbers that add
    up to 10. Each number can be used more than one time or not at all.

    possible solutions are:

    10 x 1
    5 x 2
    3 x 2 + 4
    1 + 4 + 5
    2 + 3 + 5
    1 + 2 + 3 + 4

    etc.


    In this case it's pretty easy to do it on paper, but when the numbers
    become larger (>1000) it would be nice to have a program to do this.


    Any suggestions how to do this and/or where to start looking ?


    thanks,

    - Koen.
     
    Koen, Aug 11, 2003
    #1
    1. Advertising

  2. Koen wrote:

    > Hi,
    >
    > I am looking for an algorithm that figures out which numbers from a
    > given set add up to another number. I am sure this has been done
    > before, but I have no idea how such a calculation is called, which
    > kind of limits my further searching.

    Are you talking addition or multiplication or both?
    The above paragraph talks about addition, but the solutions show
    multiplication.

    >
    > An example. The set contains the numbers 1-2-3-4-5. Now the algorithm
    > should calculate all possible combinations of these numbers that add
    > up to 10. Each number can be used more than one time or not at all.

    Again, you state addition, but the example shows multiplication.
    What is exact definition of the problem?


    >
    > possible solutions are:
    >
    > 10 x 1
    > 5 x 2
    > 3 x 2 + 4
    > 1 + 4 + 5
    > 2 + 3 + 5
    > 1 + 2 + 3 + 4
    >
    > etc.

    Let us see, the first solution is invalid according to the given rules.
    "10 x 1" is not a solution because the number "10" is not a member of
    the set [1,2,3,4,5].

    According to your problem definition, the first three solutions:
    10 x 1
    5 x 2
    3 x 2 + 4
    are all invalid solutions since they involve multiplication.

    >
    >
    > In this case it's pretty easy to do it on paper, but when the numbers
    > become larger (>1000) it would be nice to have a program to do this.

    As I've been thinking about this problem, it is not easy.
    The given solution set does not match the problem definition.
    The number of solutions involving mulitiplication is not a finitie
    set, given the rule that any number may be used more than once and
    the rule of multiplication by 1.

    Addition, on the other hand, is a finite set, as long a zero is not
    within the set. The rule of addition with zero provides an infinite
    quantity of terms for a solution.



    > Any suggestions how to do this and/or where to start looking ?

    Yes, get your problem definition correct before proceeding.
    Start looking at:
    combinatorics
    recursion
    linked list
    stack
    Identity Theorum for Multiplication
    Identity Theorum for Addition
    Programming loop constructs.
    Greatest Common Factor (GCF)
    Lowest Common Denominator (LCD)
    logarithms (sp?)
    Series expansion

    If this is homework, slap your instructor and say "bad assignment"
    then ramble off the Identity Theorums and say this is a never
    ending waste of computer cycles (the same as an infinite loop).

    >
    >
    > thanks,
    >
    > - Koen.


    I would first start out with either multiplication or addition and
    get them working. The multiplication with addition adds more
    complexity to the function (as well as combinations).

    Since "Each number can be used more than one time",
    how does one know when to stop?
    For example,
    5 x 2
    5 x 2 x 1
    5 x 2 x 1 x 1
    5 x 2 x 1 x 1 x 1 ...

    --
    Thomas Matthews
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.raos.demon.uk/acllc-c /faq.html
     
    Thomas Matthews, Aug 11, 2003
    #2
    1. Advertising

  3. "Koen" <> wrote in message
    news:...
    | I am looking for an algorithm that figures out which numbers from a
    | given set add up to another number. I am sure this has been done
    | before, but I have no idea how such a calculation is called, which
    | kind of limits my further searching.
    |
    | An example. The set contains the numbers 1-2-3-4-5. Now the algorithm
    | should calculate all possible combinations of these numbers that add
    | up to 10. Each number can be used more than one time or not at all.
    .....
    | In this case it's pretty easy to do it on paper, but when the numbers
    | become larger (>1000) it would be nice to have a program to do this.
    .....
    | Any suggestions how to do this and/or where to start looking ?

    Not really a question about C... but anyway:

    A somewhat similar classic is the "knapsack problem".
    A classic approach to solve this type of thing is "Dynamic programming".
    (NB: this is not about dynamic code generation, 'programming' is
    to be taken in a mathematical sense).

    Googling for these terms should take you in the right direction.


    I hope this helps,
    Ivan
    --
    http://www.post1.com/~ivec
     
    Ivan Vecerina, Aug 11, 2003
    #3
  4. Thomas Matthews wrote:
    >
    > Koen wrote:
    >
    > > Hi,
    > >
    > > I am looking for an algorithm that figures out which numbers from a
    > > given set add up to another number. I am sure this has been done
    > > before, but I have no idea how such a calculation is called, which
    > > kind of limits my further searching.

    > Are you talking addition or multiplication or both?
    > The above paragraph talks about addition, but the solutions show
    > multiplication.
    >
    > >
    > > An example. The set contains the numbers 1-2-3-4-5. Now the algorithm
    > > should calculate all possible combinations of these numbers that add
    > > up to 10. Each number can be used more than one time or not at all.

    > Again, you state addition, but the example shows multiplication.
    > What is exact definition of the problem?
    >
    > >
    > > possible solutions are:
    > >
    > > 10 x 1
    > > 5 x 2
    > > 3 x 2 + 4
    > > 1 + 4 + 5
    > > 2 + 3 + 5
    > > 1 + 2 + 3 + 4
    > >
    > > etc.

    > Let us see, the first solution is invalid according to the given rules.
    > "10 x 1" is not a solution because the number "10" is not a member of
    > the set [1,2,3,4,5].
    >
    > According to your problem definition, the first three solutions:
    > 10 x 1
    > 5 x 2
    > 3 x 2 + 4
    > are all invalid solutions since they involve multiplication.
    >
    > >
    > >
    > > In this case it's pretty easy to do it on paper, but when the numbers
    > > become larger (>1000) it would be nice to have a program to do this.

    > As I've been thinking about this problem, it is not easy.
    > The given solution set does not match the problem definition.
    > The number of solutions involving mulitiplication is not a finitie
    > set, given the rule that any number may be used more than once and
    > the rule of multiplication by 1.
    >
    > Addition, on the other hand, is a finite set, as long a zero is not
    > within the set. The rule of addition with zero provides an infinite
    > quantity of terms for a solution.
    >
    > > Any suggestions how to do this and/or where to start looking ?

    > Yes, get your problem definition correct before proceeding.
    > Start looking at:
    > combinatorics
    > recursion
    > linked list
    > stack
    > Identity Theorum for Multiplication
    > Identity Theorum for Addition
    > Programming loop constructs.
    > Greatest Common Factor (GCF)
    > Lowest Common Denominator (LCD)
    > logarithms (sp?)
    > Series expansion
    >
    > If this is homework, slap your instructor and say "bad assignment"
    > then ramble off the Identity Theorums and say this is a never
    > ending waste of computer cycles (the same as an infinite loop).
    >
    > >
    > >
    > > thanks,
    > >
    > > - Koen.

    >
    > I would first start out with either multiplication or addition and
    > get them working. The multiplication with addition adds more
    > complexity to the function (as well as combinations).
    >
    > Since "Each number can be used more than one time",
    > how does one know when to stop?
    > For example,
    > 5 x 2
    > 5 x 2 x 1
    > 5 x 2 x 1 x 1
    > 5 x 2 x 1 x 1 x 1 ...
    >
    > --
    > Thomas Matthews
    > C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    > alt.comp.lang.learn.c-c++ faq:
    > http://www.raos.demon.uk/acllc-c /faq.html



    Aw, come on!
    It seems obvious that the original posting
    10x1
    is just a shorthand for saying "1+1+1+1+1+1+1+1+1+1"
    and was not meant to say that multiplication was part of the deal.
    --
    Fred L. Kleinschmidt
    Associate Technical Fellow
    Boeing Common User Interface Services
     
    Fred L. Kleinschmidt, Aug 11, 2003
    #4
  5. Koen

    Koen Guest

    In article <3f37daa6$>,
    "Ivan Vecerina" <> wrote:

    > A somewhat similar classic is the "knapsack problem".
    > A classic approach to solve this type of thing is "Dynamic programming".
    > (NB: this is not about dynamic code generation, 'programming' is
    > to be taken in a mathematical sense).
    >
    > Googling for these terms should take you in the right direction.
    >
    >
    > I hope this helps,
    > Ivan



    Thanks Ivan for a grown-up response ;) I will look into the knapsack
    problem.

    - Koen.
     
    Koen, Aug 12, 2003
    #5
  6. Koen

    Koen Guest

    In article <NjQZa.20323$>,
    Thomas Matthews <> wrote:

    > Are you talking addition or multiplication or both?
    > The above paragraph talks about addition, but the solutions show
    > multiplication.


    > If this is homework, slap your instructor and say "bad assignment"
    > then ramble off the Identity Theorums and say this is a never
    > ending waste of computer cycles (the same as an infinite loop).


    Sorry Thomas, I don't understand your replies. I am glad another reader
    gave a more mature reply and pointed me in the correct direction (my
    problem is similar to the 'knapsack problem').


    have a nice day,

    - Koen.
     
    Koen, Aug 12, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Ahmed Moustafa
    Replies:
    0
    Views:
    797
    Ahmed Moustafa
    Nov 15, 2003
  2. Replies:
    1
    Views:
    4,596
    Jack Klein
    Jan 12, 2005
  3. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,512
    Mike Treseler
    Jun 23, 2006
  4. Deepak
    Replies:
    1
    Views:
    1,209
    Mike Wahler
    Jan 11, 2005
  5. Ulterior
    Replies:
    9
    Views:
    323
    Jerry Coffin
    Jun 23, 2007
Loading...

Share This Page