CODEWITHSUNDEEP
algorithmpermutation
zmbq
zmbq

Reputation: 39023

Algorithms for enumeration all permutations given a cycle structure

I need to enumerate on all permutations of size N, but with specific cycle sizes - cycles of length 1 (that is, stationary points), 2 and K (a parameter). I need to go over all permutations with such cycles - there can be more than one cycle of each size if N is large enough.

I tried to look for such algorithms in the literature but couldn't. I would appreciate any pointers to such algorithms.

Upvotes: 2

Views: 297

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

I think that this problem falls into the gap of being neither hard nor elegant to solve. No matter. There's a recursive strategy that accepts a multiset of cycle sizes, loops over cycle sizes, includes one fixed element and the appropriate number of others, and recurses on the remaining elements.

Lightly tested, unoptimized Python 3:

import itertools

def enumerate_perms(cycle_sizes, elements):
    assert isinstance(cycle_sizes, list)
    assert all(isinstance(cycle_size, int) for cycle_size in cycle_sizes)
    assert all(cycle_size >= 1 for cycle_size in cycle_sizes)
    assert isinstance(elements, list)
    assert len(elements) == sum(cycle_sizes)
    if not elements:
        yield {}
        return
    for cycle_size in set(cycle_sizes):
        remaining_cycle_sizes = cycle_sizes[:]
        remaining_cycle_sizes.remove(cycle_size)
        for others_tuple in itertools.permutations(elements[1:], cycle_size - 1):
            remaining_elements = elements[1:]
            for other in others_tuple:
                remaining_elements.remove(other)
            others = list(others_tuple)
            others.append(elements[0])
            for subperm in enumerate_perms(remaining_cycle_sizes, remaining_elements):
                for i in range(cycle_size):
                    subperm[others[i - 1]] = others[i]
                yield subperm

print(list(enumerate_perms([2, 2, 1], [1, 2, 3, 4, 5])))

Upvotes: 2

Related Questions