In this thread I am seeking for an advice or a starting point on how to solve the following riddle. I need to come up with an algorithm which will generate all possible combinations, but I don't know where to start. In this example let's assume that we have 3 value pairs
1 2 2 3 3 1
The aim of a riddle is to make as much UNIQUE pair connections as possible. So the first KeyValuePair can connect on value 2 of second KeyValuePair, whereas second KeyValuePair can connect on number 3 of third KeyValuePair. Start and End key can not be the same. Here is a graphical representation of the expected result:
Valid combinations: 1 2 (1 - 2 connection) 2 3 (2 - 3 connection) 3 1 (3 - 1 connection) 1 2, 2 3 (1 - 3 connection) 1 2, 3 1 (2 - 3 connection) 2 3, 3 1 (2 - 1 connection) Invalid combinations: 3 1, 1 2 (3 - 2 connection, duplicate) 2 3, 1 2 (3 - 1 connection, duplicate) 3 1, 2 3 (1 - 2 connection, duplicate) 1 2, 2 3, 3 1 (connection: 1 - 1, not unique, 'Start' and 'End' key can not be the same)
I hope I did not miss anything :). A graphical representation of joining would be:
Pair 4 1 was added for the sake of demonstration. In a real world application I expect there to be 100+ pairs. Therefore an algorithm must be efficient. Also (sorry if this is too much) I will need to make sure that there are no more than 3 pairs in a chain (therefore above image is not entirely correct)! But this requirement can be ignored right now, for the sake of simplicity. How to design an algorithm like this?
Based on comment replies I think I need to provide additional explanation of the real use-case for this algorithm. In reality there will be currencies instead of numbers. So
EUR/USD is 1 - 2,
USD/RUR is 2 - 3,
RUR/EUR 3 - 1, in that case (
EUR/USD - USD/RUR) is also 3 - 1, but fundamentally it is different kind of conversion! What we are searching here is basically how every currency can be converted to any other currency. For that same reason
= EUR/EUR) is not a valid case. Hope that explains it a bit better.