0
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ I think much can be gained here by properly stating the problem. Given $(a_1, b_1), \dots, (a_n, b_n)$, what exactly is the desired output? $\endgroup$ – Raphael Dec 19 '17 at 16:27
  • 2
    $\begingroup$ I'm also unable to understand your problem. $\endgroup$ – Yuval Filmus Dec 19 '17 at 21:40
  • $\begingroup$ Why is 2-3 connection not considered duplicate in your example? $\endgroup$ – Albert Hendriks Dec 19 '17 at 23:01
  • $\begingroup$ @YuvalFilmus I have added an edit, please check it out. Let me know if any additional details are needed. $\endgroup$ – Alex Dec 20 '17 at 11:47
  • $\begingroup$ @AlbertHendriks please check an edit $\endgroup$ – Alex Dec 20 '17 at 12:34
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, I never looked at this problem that way! I can't wait to try that algorithm out. This is a perfect starting point, thank you! $\endgroup$ – Alex Dec 20 '17 at 12:41
  • $\begingroup$ Regarding Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. As I meantioned in my initial question - I do not necessary need to build chains with more than 2 conversions in it (i.e. 12 - 23 - 34 is maximum). So this should not be a problem. However, I expect some problems with duplicate conversions. I think duplicates will need to be cleared up afterwards as the last step. $\endgroup$ – Alex Dec 20 '17 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.