Velocity Reviews > Java > Look for recursive algorithm

# Look for recursive algorithm

jacksu
Guest
Posts: n/a

 06-15-2006
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.

Rajah
Guest
Posts: n/a

 06-15-2006

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?

Daniel Dyer
Guest
Posts: n/a

 06-15-2006
On Thu, 15 Jun 2006 23:40:48 +0100, jacksu <(E-Mail Removed)> 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.
>
> Thanks.

Take a look at this thread:

Dan.

--
Daniel Dyer
http://www.dandyer.co.uk

jacksu
Guest
Posts: n/a

 06-15-2006

Rajah wrote:
>
> 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.

Patricia Shanahan
Guest
Posts: n/a

 06-15-2006
jacksu wrote:
> Rajah wrote:
>>
>> 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

jacksu
Guest
Posts: n/a

 06-15-2006

Patricia Shanahan wrote:
> jacksu wrote:
> > Rajah wrote:
> >>
> >> 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

Rajah
Guest
Posts: n/a

 06-15-2006
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?)

jacksu
Guest
Posts: n/a

 06-15-2006

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.

Red Orchid
Guest
Posts: n/a

 06-16-2006
"jacksu" <(E-Mail Removed)> wrote or quoted in
Message-ID: <(E-Mail Removed). com>:

> 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[i] = sum(c[i]);
}
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[i];
}
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[i]) {

t[idx++] = a[i];
}
}
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
Guest
Posts: n/a

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

Red Orchid wrote:
> "jacksu" <(E-Mail Removed)> wrote or quoted in
> Message-ID: <(E-Mail Removed). com>:
>
> > 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[i] = sum(c[i]);
> }
> 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[i];
> }
> 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[i]) {
>
> t[idx++] = a[i];
> }
> }
> 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.