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
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?

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:

http://groups.google.com/group/comp....9747b6b02e8ab1

Dan.

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

jacksu
Guest
Posts: n/a

 06-15-2006

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.

Patricia Shanahan
Guest
Posts: n/a

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

jacksu
Guest
Posts: n/a

 06-15-2006

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

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.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post vamsi C Programming 21 03-09-2009 10:53 PM n00m C++ 12 03-13-2008 03:18 PM seberino@spawar.navy.mil Python 9 10-07-2006 03:34 AM index Java 18 05-11-2006 12:23 PM alexey.pyatovskiy@gmail.com C++ 0 02-15-2005 06:03 AM

Advertisments