An algorithm to generate all connectible pair combinations 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?

EDIT:
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/USD - USD-RUR - RUR/EUR (= EUR/EUR) is not a valid case. Hope that explains it a bit better.
Model the whole thing as a directed graph.


Currences are nodes.
Conversions are edges.
Conversion factors are edge weights.


So, in your example, you'd have nodes EUR and USD, and edges from EUR to USD with weight 2  resp. from USD to EUR with weight 1/2.

Now, every (directed) path from one currency to another represents a potential series of conversions, and the total conversion factor is the product of all traversed edge weights.

Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. Furthermore, finding the "longest" path may be NP-hard.