Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Look for recursive algorithm (http://www.velocityreviews.com/forums/t302381-look-for-recursive-algorithm.html)

 jacksu 06-15-2006 10:40 PM

Look for recursive algorithm

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 06-15-2006 10:53 PM

Re: Look for recursive algorithm

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 06-15-2006 11:00 PM

Re: Look for recursive algorithm

On Thu, 15 Jun 2006 23:40:48 +0100, jacksu <jacksuyu@gmail.com> 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 06-15-2006 11:01 PM

Re: Look for recursive algorithm

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 06-15-2006 11:04 PM

Re: Look for recursive algorithm

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 06-15-2006 11:07 PM

Re: Look for recursive algorithm

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 06-15-2006 11:14 PM

Re: Look for recursive algorithm

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 06-15-2006 11:17 PM

Re: Look for recursive algorithm

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 06-16-2006 12:55 AM

Re: Look for recursive algorithm

"jacksu" <jacksuyu@gmail.com> wrote or quoted in

> 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 06-16-2006 04:39 AM

Re: Look for recursive algorithm

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

Red Orchid wrote:
> "jacksu" <jacksuyu@gmail.com> wrote or quoted in
>
> > 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.

All times are GMT. The time now is 03:44 PM.