Blog Moved

Future posts related to technology are directly published to LinkedIn

Tuesday, September 18, 2007

Simple looking Complex problem

Approximately a decade back, after spending nearly two years on an optimization problem, I have ended up with the following problem. This is a variation of combination algorithm.

Assume that there are 'm' groups with each group will have 'nelem(i)' elements where i = 1 to m and nelem(i) > 0 (zero)

The problem is to find out all the possible combinations picking exactly one element from each group. [each element in a group is distinct and imagine it is numbered 1, 2, ... nelem(i)]

It looks very simple in the first look but takes time to solve this problem. If you are a programmer try to solve it for yourself. Just try to write an algorithm for this and you will realize the complexity of this problem.

So, there are certain things look very simple when you first see them. Only when coming to implement the solution the real complexity will appear.

Example output 1:
Number of Groups : 4
Number of Elements in Group 1 : 3
Number of Elements in Group 2 : 2
Number of Elements in Group 3 : 1
Number of Elements in Group 4 : 2
G1:1 G2:1 G3:1 G4:1
G1:1 G2:1 G3:1 G4:2
G1:1 G2:2 G3:1 G4:1
G1:1 G2:2 G3:1 G4:2
G1:2 G2:1 G3:1 G4:1
G1:2 G2:1 G3:1 G4:2
G1:2 G2:2 G3:1 G4:1
G1:2 G2:2 G3:1 G4:2
G1:3 G2:1 G3:1 G4:1
G1:3 G2:1 G3:1 G4:2
G1:3 G2:2 G3:1 G4:1
G1:3 G2:2 G3:1 G4:2

Example Output 2:
Number of Groups : 3
Number of Elements in Group 1 : 5
Number of Elements in Group 2 : 3
Number of Elements in Group 3 : 2
G1:1 G2:1 G3:1
G1:1 G2:1 G3:2
G1:1 G2:2 G3:1
G1:1 G2:2 G3:2
G1:1 G2:3 G3:1
G1:1 G2:3 G3:2
G1:2 G2:1 G3:1
G1:2 G2:1 G3:2
G1:2 G2:2 G3:1
G1:2 G2:2 G3:2
G1:2 G2:3 G3:1
G1:2 G2:3 G3:2
G1:3 G2:1 G3:1
G1:3 G2:1 G3:2
G1:3 G2:2 G3:1
G1:3 G2:2 G3:2
G1:3 G2:3 G3:1
G1:3 G2:3 G3:2
G1:4 G2:1 G3:1
G1:4 G2:1 G3:2
G1:4 G2:2 G3:1
G1:4 G2:2 G3:2
G1:4 G2:3 G3:1
G1:4 G2:3 G3:2
G1:5 G2:1 G3:1
G1:5 G2:1 G3:2
G1:5 G2:2 G3:1
G1:5 G2:2 G3:2
G1:5 G2:3 G3:1
G1:5 G2:3 G3:2

I have posed this problem to several programming experts. Still I did not get a better solution yet!
Post a Comment