# Look for recursive algorithm

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

1. ### jacksuGuest

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

2. ### RajahGuest

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

3. ### Daniel DyerGuest

Daniel Dyer, Jun 16, 2006
4. ### jacksuGuest

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.

jacksu, Jun 16, 2006
5. ### Patricia ShanahanGuest

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

Patricia Shanahan, Jun 16, 2006
6. ### jacksuGuest

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

jacksu, Jun 16, 2006
7. ### RajahGuest

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
8. ### jacksuGuest

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
9. ### Red OrchidGuest

"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
10. ### jacksuGuest

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
11. ### Piotr KobzdaGuest

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
12. ### jacksuGuest

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