Look for recursive algorithm

J

jacksu

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.
 
R

Rajah

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

jacksu

Rajah said:
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.
 
P

Patricia Shanahan

jacksu said:
Rajah said:
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
 
J

jacksu

Patricia said:
jacksu said:
Rajah said:
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
 
R

Rajah

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

jacksu

Rajah said:
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.
 
R

Red Orchid

Message-ID: said:
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>
 
J

jacksu

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

Red said:
Message-ID: said:
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.
 
P

Piotr Kobzda

jacksu said:
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
 
J

jacksu

Thanks.!
Piotr said:
jacksu said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top