Mixing
Finding nth term in a series
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
You are given a list of sets of numbers (nested) to derive a sequence such that :
- Exactly 1 number must be selected from each of the sets
- The sequence is arranged in the ascending order of the sum of these numbers
- No 2 terms of the sequence can be the same (must not repeat)
All the numbers are positive and they are unique within each set
Need the most efficient way to get the nth term of the sequence
Consider the following example:
Given:
[[1, 2, 5] ,
[12, 15, 19, 30, 54],
[55, 90, 97, 23, 54]]
Sequence (Output):
[1, 12, 23] (sum = 36 (min possible))
[2, 12, 23] (sum = 37)
[1, 15, 23] (sum = 39)
[2, 15, 23] (sum = 40)
[5, 12, 23] (sum = 40)
[1, 19, 23] (sum = 43)
[5, 15, 23] (sum = 43)
and so on...
My current approach is brute forcing (getting the product of the sets) and then sorting them, but obviously it is not O(polynomial).
Is there a more efficient approach to this?
(edit): Note that the output is ordered and the different sets may have same numbers (see the 54 is common in the above example)
combinatorics optimization algorithms computational-complexity
asked Jul 23 at 7:49
coolsidd
164
 |Â
show 2 more comments
up vote
1
down vote
favorite
You are given a list of sets of numbers (nested) to derive a sequence such that :
- Exactly 1 number must be selected from each of the sets
- The sequence is arranged in the ascending order of the sum of these numbers
- No 2 terms of the sequence can be the same (must not repeat)
All the numbers are positive and they are unique within each set
Need the most efficient way to get the nth term of the sequence
Consider the following example:
Given:
[[1, 2, 5] ,
[12, 15, 19, 30, 54],
[55, 90, 97, 23, 54]]
Sequence (Output):
[1, 12, 23] (sum = 36 (min possible))
[2, 12, 23] (sum = 37)
[1, 15, 23] (sum = 39)
[2, 15, 23] (sum = 40)
[5, 12, 23] (sum = 40)
[1, 19, 23] (sum = 43)
[5, 15, 23] (sum = 43)
and so on...
My current approach is brute forcing (getting the product of the sets) and then sorting them, but obviously it is not O(polynomial).
Is there a more efficient approach to this?
(edit): Note that the output is ordered and the different sets may have same numbers (see the 54 is common in the above example)
combinatorics optimization algorithms computational-complexity
asked Jul 23 at 7:49
coolsidd
164
Are the numbers in each set unique and different from numbers in the other set?
– Satish Ramanathan
Jul 23 at 7:53
@SatishRamanathan No...not necessary only the ones inside a set are
– coolsidd
Jul 23 at 7:54
In which case the sequence may have a repeat if picked from two sets having the same number !!. Would that be allowed?
– Satish Ramanathan
Jul 23 at 7:55
@SatishRamanathan the output is ordered so they wil still be unique
– coolsidd
Jul 23 at 7:57
An easy example is $[[0,1,2],[0,3,6],[0,9,18]]$ so you get all numbers in base-3.
– Empy2
Jul 23 at 8:13
 |Â
show 2 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
You are given a list of sets of numbers (nested) to derive a sequence such that :
- Exactly 1 number must be selected from each of the sets
- The sequence is arranged in the ascending order of the sum of these numbers
- No 2 terms of the sequence can be the same (must not repeat)
All the numbers are positive and they are unique within each set
Need the most efficient way to get the nth term of the sequence
Consider the following example:
Given:
[[1, 2, 5] ,
[12, 15, 19, 30, 54],
[55, 90, 97, 23, 54]]
Sequence (Output):
[1, 12, 23] (sum = 36 (min possible))
[2, 12, 23] (sum = 37)
[1, 15, 23] (sum = 39)
[2, 15, 23] (sum = 40)
[5, 12, 23] (sum = 40)
[1, 19, 23] (sum = 43)
[5, 15, 23] (sum = 43)
and so on...
My current approach is brute forcing (getting the product of the sets) and then sorting them, but obviously it is not O(polynomial).
Is there a more efficient approach to this?
(edit): Note that the output is ordered and the different sets may have same numbers (see the 54 is common in the above example)
combinatorics optimization algorithms computational-complexity
asked Jul 23 at 7:49
coolsidd
164
You are given a list of sets of numbers (nested) to derive a sequence such that :
- Exactly 1 number must be selected from each of the sets
- The sequence is arranged in the ascending order of the sum of these numbers
- No 2 terms of the sequence can be the same (must not repeat)
All the numbers are positive and they are unique within each set
Need the most efficient way to get the nth term of the sequence
Consider the following example:
Given:
[[1, 2, 5] ,
[12, 15, 19, 30, 54],
[55, 90, 97, 23, 54]]
Sequence (Output):
[1, 12, 23] (sum = 36 (min possible))
[2, 12, 23] (sum = 37)
[1, 15, 23] (sum = 39)
[2, 15, 23] (sum = 40)
[5, 12, 23] (sum = 40)
[1, 19, 23] (sum = 43)
[5, 15, 23] (sum = 43)
and so on...
My current approach is brute forcing (getting the product of the sets) and then sorting them, but obviously it is not O(polynomial).
Is there a more efficient approach to this?
(edit): Note that the output is ordered and the different sets may have same numbers (see the 54 is common in the above example)
combinatorics optimization algorithms computational-complexity
asked Jul 23 at 7:49
coolsidd
164
edited Jul 23 at 8:00
asked Jul 23 at 7:49
coolsidd
164
asked Jul 23 at 7:49
coolsidd
164
asked Jul 23 at 7:49
coolsidd
164
164
Are the numbers in each set unique and different from numbers in the other set?
– Satish Ramanathan
Jul 23 at 7:53
@SatishRamanathan No...not necessary only the ones inside a set are
– coolsidd
Jul 23 at 7:54
In which case the sequence may have a repeat if picked from two sets having the same number !!. Would that be allowed?
– Satish Ramanathan
Jul 23 at 7:55
@SatishRamanathan the output is ordered so they wil still be unique
– coolsidd
Jul 23 at 7:57
An easy example is $[[0,1,2],[0,3,6],[0,9,18]]$ so you get all numbers in base-3.
– Empy2
Jul 23 at 8:13
 |Â
show 2 more comments
Are the numbers in each set unique and different from numbers in the other set?
– Satish Ramanathan
Jul 23 at 7:53
@SatishRamanathan No...not necessary only the ones inside a set are
– coolsidd
Jul 23 at 7:54
In which case the sequence may have a repeat if picked from two sets having the same number !!. Would that be allowed?
– Satish Ramanathan
Jul 23 at 7:55
@SatishRamanathan the output is ordered so they wil still be unique
– coolsidd
Jul 23 at 7:57
An easy example is $[[0,1,2],[0,3,6],[0,9,18]]$ so you get all numbers in base-3.
– Empy2
Jul 23 at 8:13
Are the numbers in each set unique and different from numbers in the other set?
– Satish Ramanathan
Jul 23 at 7:53
Are the numbers in each set unique and different from numbers in the other set?
– Satish Ramanathan
Jul 23 at 7:53
@SatishRamanathan No...not necessary only the ones inside a set are
– coolsidd
Jul 23 at 7:54
@SatishRamanathan No...not necessary only the ones inside a set are
– coolsidd
Jul 23 at 7:54
In which case the sequence may have a repeat if picked from two sets having the same number !!. Would that be allowed?
– Satish Ramanathan
Jul 23 at 7:55
In which case the sequence may have a repeat if picked from two sets having the same number !!. Would that be allowed?
– Satish Ramanathan
Jul 23 at 7:55
@SatishRamanathan the output is ordered so they wil still be unique
– coolsidd
Jul 23 at 7:57
@SatishRamanathan the output is ordered so they wil still be unique
– coolsidd
Jul 23 at 7:57
An easy example is $[[0,1,2],[0,3,6],[0,9,18]]$ so you get all numbers in base-3.
– Empy2
Jul 23 at 8:13
An easy example is $[[0,1,2],[0,3,6],[0,9,18]]$ so you get all numbers in base-3.
– Empy2
Jul 23 at 8:13
 |Â
show 2 more comments
1 Answer
1
active
oldest
votes
up vote
1
down vote
accepted
Turns out it is a np-complete problem. A specific case for 2 sets of equal length is a famous problem called X+Y problem
https://en.wikipedia.org/wiki/X_%2B_Y_sorting
Also a similar problem has been answered here https://cs.stackexchange.com/questions/46910/efficiently-finding-k-smallest-elements-of-cartesian-product
It seems that the best way to solve it is to use breadth first search.
Currently it cannot be solved in polynomial time and theorectically it may be possible to solve it with complexity O(n^m) where m is the no. of sets and n is the max length of the set. Currently this remains an open problem in computer science and mathematics.
answered Jul 23 at 17:37
coolsidd
164
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Turns out it is a np-complete problem. A specific case for 2 sets of equal length is a famous problem called X+Y problem
https://en.wikipedia.org/wiki/X_%2B_Y_sorting
Also a similar problem has been answered here https://cs.stackexchange.com/questions/46910/efficiently-finding-k-smallest-elements-of-cartesian-product
It seems that the best way to solve it is to use breadth first search.
Currently it cannot be solved in polynomial time and theorectically it may be possible to solve it with complexity O(n^m) where m is the no. of sets and n is the max length of the set. Currently this remains an open problem in computer science and mathematics.
answered Jul 23 at 17:37
coolsidd
164
add a comment |Â
up vote
1
down vote
accepted
Turns out it is a np-complete problem. A specific case for 2 sets of equal length is a famous problem called X+Y problem
https://en.wikipedia.org/wiki/X_%2B_Y_sorting
Also a similar problem has been answered here https://cs.stackexchange.com/questions/46910/efficiently-finding-k-smallest-elements-of-cartesian-product
It seems that the best way to solve it is to use breadth first search.
Currently it cannot be solved in polynomial time and theorectically it may be possible to solve it with complexity O(n^m) where m is the no. of sets and n is the max length of the set. Currently this remains an open problem in computer science and mathematics.
answered Jul 23 at 17:37
coolsidd
164
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Turns out it is a np-complete problem. A specific case for 2 sets of equal length is a famous problem called X+Y problem
https://en.wikipedia.org/wiki/X_%2B_Y_sorting
Also a similar problem has been answered here https://cs.stackexchange.com/questions/46910/efficiently-finding-k-smallest-elements-of-cartesian-product
It seems that the best way to solve it is to use breadth first search.
Currently it cannot be solved in polynomial time and theorectically it may be possible to solve it with complexity O(n^m) where m is the no. of sets and n is the max length of the set. Currently this remains an open problem in computer science and mathematics.
answered Jul 23 at 17:37
coolsidd
164
Turns out it is a np-complete problem. A specific case for 2 sets of equal length is a famous problem called X+Y problem
https://en.wikipedia.org/wiki/X_%2B_Y_sorting
Also a similar problem has been answered here https://cs.stackexchange.com/questions/46910/efficiently-finding-k-smallest-elements-of-cartesian-product
It seems that the best way to solve it is to use breadth first search.
Currently it cannot be solved in polynomial time and theorectically it may be possible to solve it with complexity O(n^m) where m is the no. of sets and n is the max length of the set. Currently this remains an open problem in computer science and mathematics.
answered Jul 23 at 17:37
coolsidd
164
answered Jul 23 at 17:37
coolsidd
164
answered Jul 23 at 17:37
coolsidd
164
answered Jul 23 at 17:37
coolsidd
164
164
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2860111%2ffinding-nth-term-in-a-series%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Are the numbers in each set unique and different from numbers in the other set?
– Satish Ramanathan
Jul 23 at 7:53
@SatishRamanathan No...not necessary only the ones inside a set are
– coolsidd
Jul 23 at 7:54
In which case the sequence may have a repeat if picked from two sets having the same number !!. Would that be allowed?
– Satish Ramanathan
Jul 23 at 7:55
@SatishRamanathan the output is ordered so they wil still be unique
– coolsidd
Jul 23 at 7:57
An easy example is $[[0,1,2],[0,3,6],[0,9,18]]$ so you get all numbers in base-3.
– Empy2
Jul 23 at 8:13