# Combinations Algorithm

Bhuvnesh Phadnis

Greenhorn

Posts: 14

posted 5 years ago

I have a few Lists of Strings. for example:

List<String> AList contains {"a1","a2","a3","a4"}

List<String> BList contains {"b1","b2","b3"}

List<String> CList contains {"c1","c2","c3","c4","c5"}

List<String> DList contains {"d1","d2"}

so on and so forth. The number of lists is variable and number of Strings in the list is also variable. I want to write a code that returns ALL POSSIBLE combinations under the following conditions:

1) each set contains at least two elements. In this example the each set will contain 2 to 5 elements. - example: {"a1","b1"} or {"c2","b3","d2"}

2) each element in a set is from different lists - example: {"c1","c4"} or {"b1","b2","a4"} both are invalid.

3) each set has unique combination of elements - example: {"a3", "d2", "b4"} is equivalent to {"d2", "a3", "b4"} hence if {"a3", "d2", "b4"} is returned in the results {"d2", "a3", "b4"} should not be returned.

Please help.

Regards,

B Phadnis

List<String> AList contains {"a1","a2","a3","a4"}

List<String> BList contains {"b1","b2","b3"}

List<String> CList contains {"c1","c2","c3","c4","c5"}

List<String> DList contains {"d1","d2"}

so on and so forth. The number of lists is variable and number of Strings in the list is also variable. I want to write a code that returns ALL POSSIBLE combinations under the following conditions:

1) each set contains at least two elements. In this example the each set will contain 2 to 5 elements. - example: {"a1","b1"} or {"c2","b3","d2"}

2) each element in a set is from different lists - example: {"c1","c4"} or {"b1","b2","a4"} both are invalid.

3) each set has unique combination of elements - example: {"a3", "d2", "b4"} is equivalent to {"d2", "a3", "b4"} hence if {"a3", "d2", "b4"} is returned in the results {"d2", "a3", "b4"} should not be returned.

Please help.

Regards,

B Phadnis

posted 5 years ago

You can generate combinations selecting one from each list with a recursive approach (Excluding your first condition; I don't know how you can get a list of 5 elements from 4 lists without duplicates).

create a method that accepts a list of lists and returns the combinations as list of lists.

For example, {{1, 2}, {3, 4, 5}} to {{1, 3}, {1, 4}, {1, 5}, {2, 3}, {2,4}, {2,5}}

Turning this into Java statements is straightforward.

Here is the code (Hope you would try your own and would require this only to compare with your solution )

**Problem:**create a method that accepts a list of lists and returns the combinations as list of lists.

For example, {{1, 2}, {3, 4, 5}} to {{1, 3}, {1, 4}, {1, 5}, {2, 3}, {2,4}, {2,5}}

**Algorithm with pseudo code**Turning this into Java statements is straightforward.

Here is the code (Hope you would try your own and would require this only to compare with your solution )

- Marimuthu Madasamy

posted 5 years ago

Marimuthu, please LetThemDoTheirOwnHomework. In other words, don't provide full solutions. Your pseudo code should be enough help. I removed the other code.

SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6 - OCEJPAD 6

How To Ask Questions How To Answer Questions

Bhuvnesh Phadnis

Greenhorn

Posts: 14

posted 5 years ago

Thank you Marimuthu Madasamy and Rob Prime. I never expect anyone to spoon-feed me the solution. I completely agree with Rob Prime. My intention here is to initiate a discussion or get some pointers or some hints. Again, thank you for your inputs.

I must say that the solution suggested by Marimuthu Madasamy isn't the complete solution but definitely points to the right direction and is much appreciated. The suggested solution gives sets of 2 which is fine. I mean linear (like {"a1","b3","c2"} or{"b1","c3","d2"}) and paired combinations are easy. The real difficulty is to get a solution like {"a1","b3","d2"} . How to get a combination of more than two with elements from at least one list missing?

I am sure I am not the first one to come across this problem. So if someone has seen this or done this or read about this, please post some pointers. I would like to know if there is any material to study for this.

Thank you,

B Phadnis

I must say that the solution suggested by Marimuthu Madasamy isn't the complete solution but definitely points to the right direction and is much appreciated. The suggested solution gives sets of 2 which is fine. I mean linear (like {"a1","b3","c2"} or{"b1","c3","d2"}) and paired combinations are easy. The real difficulty is to get a solution like {"a1","b3","d2"} . How to get a combination of more than two with elements from at least one list missing?

I am sure I am not the first one to come across this problem. So if someone has seen this or done this or read about this, please post some pointers. I would like to know if there is any material to study for this.

Thank you,

B Phadnis