How to generate permutations by decreasing cycles?

Question

Here are two related SO questions 1 2 that helped me formulate my preliminary solution.

The reason for wanting to do this is to feed permutations by edit distance into a Damerau-Levenshtein NFA; the number of permutations grows fast, so it's a good idea to delay (N-C) cycle N permutations candidates until (N-C) iterations of the NFA.

I've only studied engineering math up to Differential Equations and Discrete Mathematics, so I lack the foundation to approach this task from a formal perspective. If anyone can provide reference materials to help me understand this problem properly, I would appreciate that!

Through brief empirical analysis, I've noticed that I can generate the swaps for all C cycle N permutations with this procedure:

1. Generate all 2-combinations of N elements (combs)
2. Subdivide combs into arrays where the smallest element of each 2-combination is the same (ncombs)
3. Generate the cartesian products of the (N-C)-combinations of ncombs (pcombs)
4. Sum pcombs to get a list of the swaps that will generate all C cycle N permutations (swaps)

The code is here.

My Python is a bit rusty, so helpful advice about the code is appreciated (I have the feeling that lines 17, 20, and 21 should be combined. I'm not sure if I should be making lists of the results of itertools.(combinations|product). I don't know why line 10 can't be ncombs += ... instead of ncombs.append(...)).

My primary question is how to solve this question properly. I did the rounds on my own due diligence by finding a solution, but I am sure there's a better way. I've also only verified my solution for N=3 and N=4, is it really correct?

The ideal solution would be functionally identical to heap's algorithm, except it would generate the permutations in decreasing cycle order (by the minimum number of swaps to generate the permutation, increasing).

Answer 1

This is far from Heap's efficiency, but it does produce only the necessary cycle combinations restricted by the desired number of cycles, k, in the permutation. We use the partitions of k to create all combinations of cycles for each partition. Enumerating the actual permutations is just a cartesian product of applying each cycle n-1 times, where n is the cycle length.

Recursive Python 3 code:

from math import ceil

def partitions(N, K, high=float('inf')):
  if K == 1:
    return [[N]]
  result = []
  low = ceil(N / K)
  high = min(high, N-K+1)
  for k in range(high, low - 1, -1):
    for sfx in partitions(N-k, K - 1, k):
      result.append([k] + sfx)
  return result

print("partitions(10, 3):\n%s\n" % partitions(10, 3))

def combs(ns, subs):
  def g(i, _subs):
    if i == len(ns):
      return [tuple(tuple(x) for x in _subs)]

    res = []
    cardinalities = set()

    def h(j):
      temp = [x[:] for x in _subs]
      temp[j].append(ns[i])
      res.extend(g(i + 1, temp))

    for j in range(len(subs)):
      if not _subs[j] and not subs[j] in cardinalities:
        h(j)
        cardinalities.add(subs[j])

      elif _subs[j] and len(_subs[j]) < subs[j]:
        h(j)

    return res

  _subs = [[] for x in subs]

  return g(0, _subs)

A = [1,2,3,4]
ns = [2, 2]
print("combs(%s, %s):\n%s\n" % (A, ns, combs(A, ns)))
A = [0,1,2,3,4,5,6,7,8,9,10,11]
ns = [3, 3, 3, 3]
print("num combs(%s, %s):\n%s\n" % (A, ns, len(combs(A, ns))))

def apply_cycle(A, cycle):
  n = len(cycle)
  last = A[ cycle[n-1] ]
  for i in range(n-1, 0, -1):
    A[ cycle[i] ] = A[ cycle[i-1] ]
  A[ cycle[0] ] = last

def permutations_by_cycle_count(n, num_cycles):
  arr = [x for x in range(n)]

  cycle_combs = []
  for partition in partitions(n, num_cycles):
    cycle_combs.extend(combs(arr, partition))

  result = {}

  def f(A, cycle_comb, i):
    if i == len(cycle_comb):
      result[cycle_comb].append(A)
      return

    if len(cycle_comb[i]) == 1:
      f(A[:], cycle_comb, i+1)

    for k in range(1, len(cycle_comb[i])):
      apply_cycle(A, cycle_comb[i])
      f(A[:], cycle_comb, i+1)

    apply_cycle(A, cycle_comb[i])

  for cycle_comb in cycle_combs:
    result[cycle_comb] = []
    f(arr, cycle_comb, 0)

  return result

result = permutations_by_cycle_count(4, 2)

print("permutations_by_cycle_count(4, 2):\n")

for e in result:
  print("%s: %s\n" % (e, result[e]))

Output:

partitions(10, 3):
[[8, 1, 1], [7, 2, 1], [6, 3, 1], [6, 2, 2], [5, 4, 1], [5, 3, 2], [4, 4, 2], [4, 3, 3]]

# These are the cycle combinations
combs([1, 2, 3, 4], [2, 2]):
[((1, 2), (3, 4)), ((1, 3), (2, 4)), ((1, 4), (2, 3))]

num combs([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], [3, 3, 3, 3]):
15400

permutations_by_cycle_count(4, 2):

((0, 1, 2), (3,)): [[2, 0, 1, 3], [1, 2, 0, 3]]

((0, 1, 3), (2,)): [[3, 0, 2, 1], [1, 3, 2, 0]]

((0, 2, 3), (1,)): [[3, 1, 0, 2], [2, 1, 3, 0]]

((1, 2, 3), (0,)): [[0, 3, 1, 2], [0, 2, 3, 1]]

((0, 1), (2, 3)): [[1, 0, 3, 2]]

((0, 2), (1, 3)): [[2, 3, 0, 1]]

((0, 3), (1, 2)): [[3, 2, 1, 0]]