Look for recursive algorithm

Discussion in 'Java' started by jacksu, Jun 15, 2006.

  1. jacksu

    jacksu Guest

    Say i have int array, want to know all the sum combination, ignore
    orders.

    say [1, 2, 3]
    have

    [1, 2 ,3]
    [3, 3]
    [1, 5]
    [4, 2]
    [6]

    How to write efficient java program to do so? The array size from 2 to
    1000.

    Thanks.
     
    jacksu, Jun 15, 2006
    #1
    1. Advertising

  2. jacksu

    Rajah Guest

    Can you provide a little more info?

    Based on the sample, I'm guessing that you want to sum the elements of
    a vector, call the sum s, and then generate the set of all vectors of
    non-negative integers that add up to s, where the number of elements is
    less than or equal to the number of elements in the original vector. Is
    that what you're thinking? (You didn't list [1, 1, 1, 1, 1, 1], for
    example.) Also, are you doing this for a programming assignment?
     
    Rajah, Jun 15, 2006
    #2
    1. Advertising

  3. jacksu

    Daniel Dyer Guest

    Daniel Dyer, Jun 16, 2006
    #3
  4. jacksu

    jacksu Guest

    Rajah wrote:
    > Can you provide a little more info?
    >
    > Based on the sample, I'm guessing that you want to sum the elements of
    > a vector, call the sum s, and then generate the set of all vectors of
    > non-negative integers that add up to s, where the number of elements is
    > less than or equal to the number of elements in the original vector. Is
    > that what you're thinking? (You didn't list [1, 1, 1, 1, 1, 1], for
    > example.) Also, are you doing this for a programming assignment?


    actually I need a set of sums of elements in the original array, [1, 1,
    1, 1, 1, 1] may not be able to express what I want. Let say the arr is

    [37, 15, 12]

    I expected to get 6 arrays back:
    [64]
    [49, 15]
    [37, 27]
    [52, 12]
    [37, 15, 12]

    Thanks.
     
    jacksu, Jun 16, 2006
    #4
  5. jacksu wrote:
    > Rajah wrote:
    >> Can you provide a little more info?
    >>
    >> Based on the sample, I'm guessing that you want to sum the elements of
    >> a vector, call the sum s, and then generate the set of all vectors of
    >> non-negative integers that add up to s, where the number of elements is
    >> less than or equal to the number of elements in the original vector. Is
    >> that what you're thinking? (You didn't list [1, 1, 1, 1, 1, 1], for
    >> example.) Also, are you doing this for a programming assignment?

    >
    > actually I need a set of sums of elements in the original array, [1, 1,
    > 1, 1, 1, 1] may not be able to express what I want. Let say the arr is
    >
    > [37, 15, 12]
    >
    > I expected to get 6 arrays back:
    > [64]
    > [49, 15]
    > [37, 27]
    > [52, 12]
    > [37, 15, 12]
    >
    > Thanks.
    >


    Are you required to use recursion?

    Patricia
     
    Patricia Shanahan, Jun 16, 2006
    #5
  6. jacksu

    jacksu Guest

    Patricia Shanahan wrote:
    > jacksu wrote:
    > > Rajah wrote:
    > >> Can you provide a little more info?
    > >>
    > >> Based on the sample, I'm guessing that you want to sum the elements of
    > >> a vector, call the sum s, and then generate the set of all vectors of
    > >> non-negative integers that add up to s, where the number of elements is
    > >> less than or equal to the number of elements in the original vector. Is
    > >> that what you're thinking? (You didn't list [1, 1, 1, 1, 1, 1], for
    > >> example.) Also, are you doing this for a programming assignment?

    > >
    > > actually I need a set of sums of elements in the original array, [1, 1,
    > > 1, 1, 1, 1] may not be able to express what I want. Let say the arr is
    > >
    > > [37, 15, 12]
    > >
    > > I expected to get 6 arrays back:
    > > [64]
    > > [49, 15]
    > > [37, 27]
    > > [52, 12]
    > > [37, 15, 12]
    > >
    > > Thanks.
    > >

    >
    > Are you required to use recursion?
    >
    > Patricia


    no, any algorithm which is efficient and readable will be great.

    Thanks
     
    jacksu, Jun 16, 2006
    #6
  7. jacksu

    Rajah Guest

    Another thought... do you want to generate
    1, 2, 3
    1, 3, 2
    2, 1, 3
    2, 3, 1
    3, 1, 2
    3, 2, 1

    Or just the last triplet? (In other words, is the permutation of the
    series important?)
     
    Rajah, Jun 16, 2006
    #7
  8. jacksu

    jacksu Guest

    Rajah wrote:
    > Another thought... do you want to generate
    > 1, 2, 3
    > 1, 3, 2
    > 2, 1, 3
    > 2, 3, 1
    > 3, 1, 2
    > 3, 2, 1
    >
    > Or just the last triplet? (In other words, is the permutation of the
    > series important?)


    No, I don't need permutation. And I don't know two thing could link
    together.
     
    jacksu, Jun 16, 2006
    #8
  9. jacksu

    Red Orchid Guest

    "jacksu" <> wrote or quoted in
    Message-ID: <>:

    > Say i have int array, want to know all the sum combination, ignore
    > orders.
    >
    > say [1, 2, 3]
    > have
    >
    > [1, 2 ,3]
    > [3, 3]
    > [1, 5]
    > [4, 2]
    > [6]
    >


    I think that the following computations is required for both
    efficient and inefficient algorithms.

    - nCk : Combination of different k of n things without repetition.
    (3C3, 3C2, 3C1 in the above case)
    - Sum of each array.
    - Remove duplicate value.


    the codes may be like :

    <java_pseudocode>
    (untested)

    int n = ...;


    for (int k = 1; k <= n; k++) {

    int[] s = nSk(n, k);

    ...... // do something
    }



    /**
    * 'nSk' returns the sum array of nCk.
    */
    int[] nSk(int n, int k) {

    int[][] c = nCk(n, k);
    int[] s = new int[c.length];

    for (int i = 0; i < c.length; i++) {

    s = sum(c);
    }
    return removeDuplicate(s);
    }


    int[][] nCk(int n, int k) {

    // select some proper algorithm in your environment.
    }


    int sum(int[] a) {

    int s = 0;

    for (int i = 0; i < a.length; i++) {

    s += a;
    }
    return s;
    }


    int[] removeDuplicate(int[] a) {

    Arrays.sort(a);

    int[] t = new int[a.length];
    int idx = 0;

    t[idx++] = a[0];

    for (int i = 1; i < a.length; i++) {

    if (a[i - 1] != a) {

    t[idx++] = a;
    }
    }
    int[] r = new int[idx];
    System.arraycopy(t, 0, r, 0, idx);
    return r;
    }
    </java_pseudocode>

















    > How to write efficient java program to do so? The array size from 2 to
    > 1000.
    >
    > Thanks.
     
    Red Orchid, Jun 16, 2006
    #9
  10. jacksu

    jacksu Guest

    Hmm, I think whatI need iswhat you mentioned nck, other part are pretty
    striaght forward.any moresuggestion? Thanks

    Red Orchid wrote:
    > "jacksu" <> wrote or quoted in
    > Message-ID: <>:
    >
    > > Say i have int array, want to know all the sum combination, ignore
    > > orders.
    > >
    > > say [1, 2, 3]
    > > have
    > >
    > > [1, 2 ,3]
    > > [3, 3]
    > > [1, 5]
    > > [4, 2]
    > > [6]
    > >

    >
    > I think that the following computations is required for both
    > efficient and inefficient algorithms.
    >
    > - nCk : Combination of different k of n things without repetition.
    > (3C3, 3C2, 3C1 in the above case)
    > - Sum of each array.
    > - Remove duplicate value.
    >
    >
    > the codes may be like :
    >
    > <java_pseudocode>
    > (untested)
    >
    > int n = ...;
    >
    >
    > for (int k = 1; k <= n; k++) {
    >
    > int[] s = nSk(n, k);
    >
    > ...... // do something
    > }
    >
    >
    >
    > /**
    > * 'nSk' returns the sum array of nCk.
    > */
    > int[] nSk(int n, int k) {
    >
    > int[][] c = nCk(n, k);
    > int[] s = new int[c.length];
    >
    > for (int i = 0; i < c.length; i++) {
    >
    > s = sum(c);
    > }
    > return removeDuplicate(s);
    > }
    >
    >
    > int[][] nCk(int n, int k) {
    >
    > // select some proper algorithm in your environment.
    > }
    >
    >
    > int sum(int[] a) {
    >
    > int s = 0;
    >
    > for (int i = 0; i < a.length; i++) {
    >
    > s += a;
    > }
    > return s;
    > }
    >
    >
    > int[] removeDuplicate(int[] a) {
    >
    > Arrays.sort(a);
    >
    > int[] t = new int[a.length];
    > int idx = 0;
    >
    > t[idx++] = a[0];
    >
    > for (int i = 1; i < a.length; i++) {
    >
    > if (a[i - 1] != a) {
    >
    > t[idx++] = a;
    > }
    > }
    > int[] r = new int[idx];
    > System.arraycopy(t, 0, r, 0, idx);
    > return r;
    > }
    > </java_pseudocode>
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    >
    > > How to write efficient java program to do so? The array size from 2 to
    > > 1000.
    > >
    > > Thanks.
     
    jacksu, Jun 16, 2006
    #10
  11. jacksu

    Piotr Kobzda Guest

    jacksu wrote:

    > Say i have int array, want to know all the sum combination, ignore
    > orders.
    >
    > say [1, 2, 3]
    > have
    >
    > [1, 2 ,3]
    > [3, 3]
    > [1, 5]
    > [4, 2]
    > [6]
    >
    > How to write efficient java program to do so? The array size from 2 to
    > 1000.


    Assuming I understand your needs well, the expected result may consist of:
    i) each k-combination without repetitions of n-elements input array;
    where k changes from 0 to n-2 (inclusive), with a single additional
    element which is a sum of n-k elements not contained in combination; and
    ii) an input array itself.

    See results (r) of applying this algorithm to your example array:

    n: 3

    // applying i):

    k: 0
    r: [] + (6) = [6]

    k: 1
    r: [1] + (5) = [1, 5]
    r: [2] + (4) = [2, 4]
    r: [3] + (3) = [3, 3]

    // applying ii):

    r: [1, 2, 3]


    Notice that using above algorithm you will need iterative combination
    series generator. This is because in expected case of 1000 elements
    input array the result will consist of
    10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668068376
    distinct arrays, which will probably not fit into your machine memory.

    An example of iterative combinations generator you can find here:
    http://mindprod.com/jgloss/combination.html


    Regards,
    piotr
     
    Piotr Kobzda, Jun 16, 2006
    #11
  12. jacksu

    jacksu Guest

    Thanks.!
    Piotr Kobzda wrote:
    > jacksu wrote:
    >
    > > Say i have int array, want to know all the sum combination, ignore
    > > orders.
    > >
    > > say [1, 2, 3]
    > > have
    > >
    > > [1, 2 ,3]
    > > [3, 3]
    > > [1, 5]
    > > [4, 2]
    > > [6]
    > >
    > > How to write efficient java program to do so? The array size from 2 to
    > > 1000.

    >
    > Assuming I understand your needs well, the expected result may consist of:
    > i) each k-combination without repetitions of n-elements input array;
    > where k changes from 0 to n-2 (inclusive), with a single additional
    > element which is a sum of n-k elements not contained in combination; and
    > ii) an input array itself.
    >
    > See results (r) of applying this algorithm to your example array:
    >
    > n: 3
    >
    > // applying i):
    >
    > k: 0
    > r: [] + (6) = [6]
    >
    > k: 1
    > r: [1] + (5) = [1, 5]
    > r: [2] + (4) = [2, 4]
    > r: [3] + (3) = [3, 3]
    >
    > // applying ii):
    >
    > r: [1, 2, 3]
    >
    >
    > Notice that using above algorithm you will need iterative combination
    > series generator. This is because in expected case of 1000 elements
    > input array the result will consist of
    > 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668068376
    > distinct arrays, which will probably not fit into your machine memory.
    >
    > An example of iterative combinations generator you can find here:
    > http://mindprod.com/jgloss/combination.html
    >
    >
    > Regards,
    > piotr
     
    jacksu, Jun 16, 2006
    #12
    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. index
    Replies:
    18
    Views:
    2,638
    opalinski from opalpaweb
    May 11, 2006
  2. inhahe
    Replies:
    3
    Views:
    2,508
    Diez B. Roggisch
    Jan 28, 2005
  3. n00m
    Replies:
    12
    Views:
    1,144
  4. vamsi
    Replies:
    21
    Views:
    2,154
    Keith Thompson
    Mar 9, 2009
  5. Replies:
    4
    Views:
    216
Loading...

Share This Page