Most efficient way to list all oriented cycles given n elements in Python

Question

I have a list of elements which can be quite big (100+ elements): elements = [a, b, c, d, e, f, g...].

and I need to build the list of all possible directed cycles, considering that the sequences [a,b,c,d,e], [b,c,d,e,a], [c,d,e,a,b], [d,e,a,b,c], [e,a,b,c,d] are considered identical since they are different representations of the same directed cycle. Only the starting point differs.

Also, since direction matters, [a,b,c,d,e] and [e,d,c,b,a] are different.

I am looking for all the oriented cycles of all lengths, from 2 to len(elements). What's the most pythonic way to do it leveraging the optimization of built-in permutations, combinations, etc ?.

Answer 1

Maybe I'm missing something, but this seems straightforward to me:

def gen_oriented_cycles(xs):
    from itertools import combinations, permutations
    for length in range(2, len(xs) + 1):
        for pieces in combinations(xs, length):
            first = pieces[0],  # 1-tuple
            for rest in permutations(pieces[1:]):
                yield first + rest

Then, e.g.,

for c in gen_oriented_cycles('abcd'):
    print c

displays:

('a', 'b')
('a', 'c')
('a', 'd')
('b', 'c')
('b', 'd')
('c', 'd')
('a', 'b', 'c')
('a', 'c', 'b')
('a', 'b', 'd')
('a', 'd', 'b')
('a', 'c', 'd')
('a', 'd', 'c')
('b', 'c', 'd')
('b', 'd', 'c')
('a', 'b', 'c', 'd')
('a', 'b', 'd', 'c')
('a', 'c', 'b', 'd')
('a', 'c', 'd', 'b')
('a', 'd', 'b', 'c')
('a', 'd', 'c', 'b')

Is that missing some essential property you're looking for?

EDIT

I thought it might be missing this part of your criteria:

Also, since direction matters, [a,b,c,d,e] and [e,d,c,b,a] are different.

but on second thought I think it meets that requirement, since [e,d,c,b,a] is the same as [a,e,d,c,b] to you.

Answer 2

Is there any good reason to have a canonical representation in memory of this? It's going to be huge, and possibly whatever use case you have for this may have a better way of dealing with it.

It looks like for your source material, you would use any combination of X elements, not necessarily even homogeneous ones? (i.e. you would have (a,e,g,x,f) etc.). Then, I would do this as a nested loop. The outer one would select by length, and select subsets of the entire list to use. The inner one would construct combinations of the subset, and then throw out matching items. It's going to be slow no matter how you do it, but I would use a dictionary with a frozenset as the key (of the items, for immutability and fast lookup), and the items to be a list of already-detected cycles. It's going to be slow/long-running no matter how you do it, but this is one way.

First, you need a way to determine if two tuples (or lists) represent the same cycle. You can do that like this:

def match_cycle(test_cycle, ref_cycle):
    try: 
        refi = ref_cycle.index(test_cycle[0])
        partlen = len(ref_cycle) - refi
        return not (any(test_cycle[i] - ref_cycle[i+refi] for i in range(partlen)) or 
           any(test_cycle[i+partlen] - ref_cycle[i] for i in range(refi)))
    except:
        return False

Then, the rest.

def all_cycles(elements):
    for tuple_length in range(2, len(elements)):
        testdict = defaultdict(list)
        for outer in combinations(elements, tuple_length):
            for inner in permutations(outer):
                testset = frozenset(inner)
                if not any(match_cycle(inner, x) for x in testdict[testset]):
                    testdict[testset].append(inner)
                    yield inner

This produced 60 items for elements of length 5, which seems about right and looked OK from inspection. Note that this is going to be exponential though.... length(5) took 1.34 ms/loop. length(6) took 22.1 ms. length(7) took 703 ms, length(8) took 33.5 s. length(100) might finish before you retire, but I wouldn't bet on it.

there might a better way, and probably is, but in general the number of subsets in 100 elements is pretty large, even when reduced some for cycles. So this is probably not the right way to approach whatever problem you are trying to solve.

Answer 3

This may work:

import itertools
import collections

class Cycle(object):
    def __init__(self, cycle):
        self.all_possible = self.get_all_possible(cycle)
        self.canonical = self.get_canonical(self.all_possible)

    def __eq__(self, other):
        return self.canonical == other.canonical

    def __hash__(self):
        return hash(self.canonical)

    def get_all_possible(self, cycle):
        output = []
        cycle = collections.deque(cycle)
        for i in xrange(len(cycle)):
            cycle.rotate(1)
            output.append(list(cycle))
        return output

    def get_canonical(self, cycles):
        return min(map(tuple, cycles), key=lambda item: hash(item))

    def __repr__(self):
        return 'Cycle({0})'.format(self.canonical)

def list_cycles(elements):
    output = set()
    for i in xrange(2, len(elements) + 1):
        output.update(set(map(Cycle, itertools.permutations(elements, i))))
    return list(output)

def display(seq):
    for cycle in seq:
        print cycle.canonical
        print '\n'.join('  ' + str(item) for item in cycle.all_possible)

def main():
    elements = 'abcdefghijkl'
    final = list_cycles(elements)
    display(final)


if __name__ == '__main__':
    main()

It creates a class to represent any given cycle, which will be hashed and checked for equality against a canonical representation of the cycle. This lets a Cycle object be placed in a set, which will automatically filter out any duplicates. Unfortunately, it's not going to be highly efficient, since it generates every single possible permutation first.

Answer 4

This should give you the right answer with cycles with length 2 to len(elements). Might not be the fastest way to do it though. I used qarma's hint of rotating it to always start with the smallest element.

from itertools import permutations

def rotate_min(l):
    '''Rotates the list so that the smallest element comes first '''
    minIndex = l.index(min(l))
    rotatedTuple = l[minIndex:] + l[:minIndex]
    return rotatedTuple


def getCycles(elements):
    elementIndicies = tuple(range(len(elements)))  #tupple is hashable so it works with set
    cyclesIndices = set()
    cycles = []

    for length in range(2, len(elements)+1):
        allPermutation = permutations(elementIndicies, length)
        for perm in allPermutation:
            rotated_perm = rotate_min(perm)
            if rotated_perm not in cyclesIndices:
                #If the cycle of indices is not in the set, add it.
                cyclesIndices.add(rotated_perm)
                #convert indicies to the respective elements and append
                cycles.append([elements[i] for i in rotated_perm])

    return cycles