Как найти все возможные перестановки с сочетаниями?

Question

[Alexey Balashov]

Есть список "валютных пар"

tickersList

• BTC_USD
  
• BTC_EUR
  
• BTC_RUB
  
• BTC_UAH
  
• BTC_PLN
  
• BCH_BTC
  
• BCH_USD
  
• BCH_RUB
  
• BCH_ETH
  
• DASH_BTC
  
• DASH_USD
  
• DASH_RUB
  
• ETH_BTC
  
• ETH_LTC
  
• ETH_USD
  
• ETH_EUR
  
• ETH_RUB
  
• ETH_UAH
  
• ETH_PLN
  
• ETC_BTC
  
• ETC_USD
  
• ETC_RUB
  
• LTC_BTC
  
• LTC_USD
  
• LTC_EUR
  
• LTC_RUB
  
• ZEC_BTC
  
• ZEC_USD
  
• ZEC_EUR
  
• ZEC_RUB
  
• XRP_BTC
  
• XRP_USD
  
• XRP_RUB
  
• XMR_BTC
  
• XMR_USD
  
• XMR_EUR
  
• BTC_USDT
  
• ETH_USDT
  
• USDT_USD
  
• USDT_RUB
  
• USD_RUB
  
• DOGE_BTC
  
• WAVES_BTC
  
• WAVES_RUB
  
• KICK_BTC
  
• KICK_ETH
  

ВыходнаяВалюта_ВходнаяВалюта
На примере пары BTC_USD:
Покупка/продажа BTC за USD

Задача:
Найти все возможные цепочки пар заканчивающиеся и начинающиеся на одной "валюте" и имеющие все возможные сочетания из списка выше. Все цепочки сочетаний разного уровня комбинаций.

Для примера разберем пару BTC_USD:
Входная валюта USD.
Мы можем получить такую цепочку:
BTC_USD=>BCH_BTC=>BCH_USD

Первые мысли.
1. вложенные циклы с проверкой
2. рекурсия
3. комбинаторика через перестановки и сочетания

Буду признателен за код на C#, или другой "сишный" пример решения.

Answer 1

[Александр]

Построить граф и решать задачу коммивояжера, с модификацией на то, что вам не нужно обходить все вершины и нужны все решения.

Comments

[Alexey Balashov]

Спасибо за подсказку.

Нашел библиотеку QuickGraph

Возникли два вопроса:
1. Какой тип топологии графа использовать
Adjacency Graph
Bidirectional Graph
Bidirectional Matrix Graph
Undirected Graph

2. Алгоритм обхода, который покажет все пути, где in=out.

Answer 2

[Ерлан Ибраев]

Третий вариант это 1 или 2. :-)