Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Look for recursive algorithm

Reply
Thread Tools

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.

 
Reply With Quote
 
 
 
 
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?

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
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.

 
Reply With Quote
 
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
 
Reply With Quote
 
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

 
Reply With Quote
 
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?)

 
Reply With Quote
 
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.

 
Reply With Quote
 
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.


 
Reply With Quote
 
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.


 
Reply With Quote
 
 
 
Reply

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Recursive functions Vs Non-recursive functions - performance aspect vamsi C Programming 21 03-09-2009 10:53 PM
Two recursive calls inside of a recursive function n00m C++ 12 03-13-2008 03:18 PM
Recursive descent algorithm able to parse Python? seberino@spawar.navy.mil Python 9 10-07-2006 03:34 AM
how to use recursive algorithm to determine all of the arrangements? index Java 18 05-11-2006 12:23 PM
Re: Recursive combinations algorithm alexey.pyatovskiy@gmail.com C++ 0 02-15-2005 06:03 AM



Advertisments