What is the more elegant way of finding combinations in a list?

Question

I came up with this algorithm to find triplets of pairs (I call them trairs), the criteria is that all 3 elements (coins), and only the 3, must be present in all 3 pairs.

However, it is probably possible to solve the same problem in a more elegant way. For instance, I am indexing all the loops, which makes it look extra complicated. Also, there is a break there that makes me uncomfortable!

The input data is pairs, it is a list of str:
Eg. pairs = ['BCH/BTC','BCH/ETH','DASH/USD','BTC/USDT','ETH/BTC']

The wanted output is a list of list of strings:
Eg. trair = [['BCH/BTC','BCH/ETH','ETH/BTC]]

def find_trairs(exchange):
    ''' Find possible triplets of pairs (trairs) that can be traded for unbalance.

    Example of trairs:
    'ETC/BTC' 'ETC/ETH' 'ETH/BTC'
    'BCH/BTC' 'BCH/EUR' 'BTC/EUR'

    '''
    exchange_pairs = exchange.symbols #loads all pairs from the exchange.
    pairs = list(filter(lambda x: not '.d' in x, exchange_pairs)) #filters off 
    #the darkpool pairs.

    pair = ['', '', '']
    coin = ['', '', '']
    trair = []

    #Semi-optimized loop to look for triplece of pairs.
    #Example:['BCH/BTC', 'BCH/EUR', 'BTC/EUR']
    for i in range(len(pairs)-3):
        #not all coins are 3 digits long, we must find the slash that separetes
        #each coin in order to have a robust algorithm.
        slash_position = pairs[i].find('/') 
        coin[0] = pairs[i][0:slash_position]
        coin[1] = pairs[i][slash_position+1:]
        for j in range(i+1, len(pairs)-2):
            if (coin[0] in pairs[j]):
                slash_position = pairs[j].find('/') 
                coin[2] = pairs[j][slash_position+1:]
                for k in range(j+1, len(pairs)-1):
                    if coin[1] in pairs[k] and coin[2] in pairs[k]:
                        trair.append([pairs[i], pairs[j], pairs[k]])
                        break

    return trair

Any hints or comments?

Answer 1

Use itertools permutations, with filtering the results, and elimination of duplicates:

import itertools

currency_pairs = ['BCH/BTC', 'BCH/ETH', 'DASH/USD', 'BTC/USDT', 'ETH/BTC']
set_triplets = set()
for triplet in itertools.permutations(currency_pairs, 3):
    c1, c2 = triplet[0].split('/')
    if (c1 in triplet[1] or c1 in triplet[2]) and (c2 in triplet[1] or c2 in triplet[2]):
        set_triplets.add(tuple(sorted(triplet)))
for triplet in set_triplets:
    print(triplet)

output:

('BCH/ETH', 'BTC/USDT', 'ETH/BTC') 
('BCH/BTC', 'BCH/ETH', 'BTC/USDT')
('BCH/BTC', 'BCH/ETH', 'ETH/BTC')

Please note that the ordering of the currency pairs in a triplet is lexicographically ascending, do not expect the first pair to always be the link between the two others.

Answer 2

You can use

coins = set('/'.join(pairs).split('/'))

to get a set of all possible coins on the exchange. Then you can get all possible subsets of len 3 of that using itertools.combinations with

triples = combinations(coins, 3)

You can get your "trairs" by taking the combinations of len 2 from your triples.

trairs = [{frozenset(pair) for pair in combinations(triple, 2)}
          for triple in triples]

The result is a list of 3-item sets where each item is a frozenset representing a coin pair.

---

The exchange may not support all possible pairs directly. If so, you can add an additional filter step to remove the invalid "trairs".

pairset = set(frozenset(pair.split('/')) for pair in pairs)
trairs = [trair for trair in trairs if trair <= pairset]

The <= checks if trair is a subset of pairset.

---

The list of sets of frozensets matches the structure of the problem better so it may suffice for your needs, but it's not exactly the output form specified.

You could convert the frozensets back to strings and the triples to lists using

[['/'.join(pair) for pair in trair] for trair in trairs]]

Sets are effectively unordered, but it's not clear from the question if this matters, since buying e.g. BTC/ETH is the same as selling ETH/BTC etc. and it's not clear what use other orderings of the same triple are. So you could instead leave the triples as sets and use the alphabetized pairings like this.

[{'/'.join(sorted(pair)) for pair in trair} for trair in trairs]]