Velocity Reviews > Java > Look for recursive algorithm

# Look for recursive algorithm

Piotr Kobzda
Guest
Posts: n/a

 06-16-2006
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
10715086071862673209484250490600018105614048117055 33607443750388370351051124936122493198378815695858 12759467291755314682518714528569231404359845775746 98574803934567774824230985421074605062371141877954 18215304647498358194126739876755916554394607706291 45711964776865421676604298316526243868372056680683 76
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
Guest
Posts: n/a

 06-16-2006
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
> 10715086071862673209484250490600018105614048117055 33607443750388370351051124936122493198378815695858 12759467291755314682518714528569231404359845775746 98574803934567774824230985421074605062371141877954 18215304647498358194126739876755916554394607706291 45711964776865421676604298316526243868372056680683 76
> 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