Generating all permutations excluding cyclic rotations in Python
Question: I need to create a (practice) program for currency arbitrage that detects
profitable "loops" given a series of exchange rates. So there might be
different values for USD->JPY, JPY->USD, USD->EUR, and so on. In order to
detect profitability, however, I first need to enumerate all possible loops --
USD->JPY->EUR->USD is one example, but USD->EUR->JPY->USD is a distinct
example using the same currencies since it may hit different exchange rates.

If I ignore the last part of the loop, which will always be the same as the
origin, it seems to be the case that every currency can only exist at most
once in the "best" loop, as if a currency exists more than once it would
actually be two different loops (at least one of which would still be
profitable).

Similarly, I can ignore loops that are just translations of already tested
loops: USD->JPY->ASD is the same as JPY->ASD->USD.

So, given input like _[USD,JPY,EUR,ASD]_ I need something that would return:

    
    
    (USD,JPY,EUR,ASD)
    (USD,JPY,ASD,EUR)
    (USD,EUR,ASD,JPY)
    (USD,EUR,JPY,ASD)
    (USD,ASD,EUR,JPY)
    (USD,ASD,JPY,EUR)
    


Answer: This solution uses the yield from syntax introduced in Python 3.3. Like the
built-in itertools.permutations(), this:

  * Is a generator and does not require storing anything
  * Will yield an empty tuple if passed length 0
  * Assumes every item in the permuted object is itself unique



    
    
    from itertools import permutations
    def unique_cyclic_permutations(thing, length):
        if length == 0:
            yield (); return
        for x in permutations(thing[1:], length - 1):
            yield (thing[0],) + x
        if length < len(thing):
            yield from unique_cyclic_permutations(thing[1:], length)
    

The algorithm works by choosing a pivot, fixing it at the beginning, and then
permuting the rest of the objects. In the case of a non-full length
permutation, there will also be some permutations that don't include the pivot
object at all. In this case, the generator recursively calls itself while
excluding the original pivot.

