Computing With Permutations, Inverses, Cycles, and More!

In this entry, we bring together ideas we’ve been developing about permutations, their sign, cycles, as well as the run time complexity of the algorithms which compute them. We begin by providing a C++ implementation of a function which will break down a permutation into disjoint cycles. Its runtime complexity is in \(O(n)\), for a permutation on \(\{0, 1, 2, …, n-1 \}\).

We begin by implementing a ceiling function, int32_t ceil(int32_t num, int32_t denom), which will return \(\left\lceil \frac{ \text{num} }{ \text{denom} }\right\rceil\).

1
2
3
4
5

int32_t ceil(int32_t num, int32_t denom)
{
  if (denom == 0) return INT32_MIN;
  return (num % denom ? 1 : 0) + (num / denom);
}

Next we provide two functions. The first checks whether the \(i^{th}\) bit of an array of uint64_ts is equal to 1. The second function sets the \(i^{th}\) bit of that array to 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int16_t check_visited(uint64_t* visited, int64_t i)
{
  if (!visited) return 0;
  int16_t r = i % sizeof(uint64_t);
  int64_t q = i / sizeof(uint64_t);

  return (visited[q] & (1 << r)) ? 1 : 0;
}

void set_visited(uint64_t* visited, int64_t i)
{
  if (!visited) return;
  // The bit has already been set //
  if (check_visited(visited, i)) return;

  int16_t r = i % sizeof(uint64_t);
  int64_t q = i / sizeof(uint64_t);

  visited[q] ^= (1 << r);
}

Now, as promised, we provide the function which breaks the permutation down into disjoint cycles.

disjoint_cycles()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

void disjoint_cycles(int64_t* permutation, int64_t length,
  int64_t** &cycles, int64_t* &lengths, int64_t &num_cycles)
{
  if (!permutation)
  {
    return;
  }
  int32_t s = sizeof(uint64_t); // this should be 64, but let's make sure. //
  int32_t c = ceil(length, s);

  num_cycles = 0;
  int64_t i, j, k;

  uint64_t visited[c];

  for(i = 0; i < c; i++)
  {
    visited[i] = (uint64_t)0;
  }

  // Loop (a)
  for (i = 0; i < length; i++)
  {
    if (check_visited(visited, i)) continue;
    j = i;
    while (!check_visited(visited, j))
    {
      set_visited(visited, j);
      j = permutation[j];
    }
    num_cycles++;
  }

  cycles = new int64_t*[num_cycles];
  lengths = new int64_t[num_cycles];

  // now, unset everything //
  for (i = 0; i < c; i++)
  {
    visited[i] = (uint64_t)0;
  }

  num_cycles = 0;
  // Loop (b)
  for (i = 0; i < length; i++)
  {
    if (check_visited(visited, i))
      continue;
    j = i;
    (lengths)[num_cycles] = 0;
    while (!check_visited(visited, j))
    {
      set_visited(visited, j);
      (lengths)[num_cycles]++;
      j = permutation[j];
    }
    (num_cycles)++;
  }

  for (i = 0; i < c; i++)
  {
    visited[i] = (uint64_t)0;
  }

  for (i = 0; i < num_cycles; i++)
  {
    cycles[i] = new int64_t[(lengths)[i]];
  }

  num_cycles = 0;
  // Loop (c)
  for (i = 0; i < length; i++)
  {
    if (check_visited(visited, i))
      continue;
    j = i;
    k = 0; // index into this cycle //
    while (!check_visited(visited, j))
    {
      set_visited(visited, j);
      cycles[num_cycles][k] = j;
      j = permutation[j];
      k++;
    }
    num_cycles++;
  }
}

You’ll notice that disjoint_cycles() has three similar for loops. They’re labeled loops (a), (b), and (c) in the comments.

Loop (a) calculates the number of cycles, which we need to determine how large the cycles and lengths arrays should be before we can allocate them properly.

Loop (b) calculates the length of each cycle. When we have all of those values, we allocate the memory for each loop.

Loop (c) sets the values of each loop.

Each loop executes in \(O(n)\) steps, because the for loop visits an index i with check_visited equal to 1 at most once. Similarly, the while loop will visit a j with check_visited equal to 1 at most once. At each iteration of each loop, if check_visited equals 0, it is set to 1 before the next iteration.

Notice that, as we mentioned in More Math of Permutations, if \(\sigma\) is a k-cycle, then \(\text{Sign}(\sigma) = (-1)^{k-1} \). Therefore we can use the output of disjoint_cycles, to determine \(\text{Sign}(\text{permutation}) \) by calculating \[ \prod\limits_{i = 0}^{\text{num_cycles}-1} (-1)^{\text{lengths}[i] - 1} \tag{1}\label{1}\]

That product will take \(O(\text{num_cycles})\) steps to complete, which will be in \(O(n)\), where \(n\) equals the length of permutation. Since disjoint_cycles also runs in \(O(n)\) steps, the overall cost of computing the \(\text{Sign}(\text{permutation})\) takes \(O(n)\) steps to complete.

This is much better than calculating \(\text{Sign}(\text{permutation})\) using the definition. Recall from More Math of Permutations that if we let \(\sigma\) denote the permutation, then

\[\text{Sign}(\sigma) = \prod\limits_{i > j} \frac{\sigma(i) - \sigma(j)}{i - j} \tag{2}\label{2}\]

Since that product runs over every pair \( (i,j)\), where \(i > j\), we have to compute \( \frac{n(n-1)}{2}\) products in the numerator and the denominator to evaluate it. This means that the calculation takes \(O(n^2)\) steps to complete. We have achieved a significant speedup!

Next we show how we can use the disjoint cycle breakdown of a permutation to compute its inverse. First we need a few simple observations. Notice that if \( \sigma = \tau_1 \circ \tau_2\), then \(\sigma^{-1} = \tau_2^{-1} \circ \tau_1^{-1} \).

We’ve shown that the set of all permutations on a set forms a group under function composition. We’ve also shown by the cancellations mini-lemma in More Introductory Group Theory that \(\sigma \circ \rho = \sigma \circ \tau\) implies that \(\rho = \tau\).

Now, notice that \(\tau_1 \circ \tau_2 \circ (\tau_2^{-1} \circ \tau_1^{-1})\) equals \(\tau_1 \circ (\tau_2 \circ \tau_2^{-1}) \circ \tau_1^{-1} = \text{id}\). By the cancellations mini-lemma, that means that \( (\tau_1 \circ \tau_2)^{-1} = \tau_2^{-1} \circ \tau_1^{-1}\).

Also notice that if \(\tau_1\) and \(\tau_2\) are disjoint, so that each keeps fixed what the other changes, then we have \( \tau_1 \circ \tau_2 = \tau_2 \circ \tau_1\), because \(\tau_1\)’s actions can’t affect \(\tau_2\)’s actions, and vice versa. This means that if \(\sigma\) is broken into disjoint cycles as \(\tau_1 \circ … \circ \tau_k\), then \(\sigma^{-1}\) is equal to \(\tau_1^{-1} \circ … \circ \tau_k^{-1} \).

The inverse of a cycle is extremely easy to calculate. You simply read it “backwards”. This allows us to easily and quickly compute the inverse of the original permutation. Here’s our implementation in C++

permutation_inverse()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

void permutation_inverse(int64_t* permutation, int64_t length, int64_t* &inverse)
{
  if(!permutation || !inverse) return;

  int64_t* lengths;
  int64_t** cycles;
  int64_t num_cycles;

  int64_t i, j, l, from, to;

  disjoint_cycles(permutation, length, cycles, lengths, num_cycles);

  // allocate the output
  inverse = new int64_t[length];

  for (i = 0; i < num_cycles; i++)
  {
    l = lengths[i];
    to = cycles[i][l-1]; // l >= 1, so this is o.k.
    from = cycles[i][0];
    inverse[from] = to;
    for (j = 1; j < l; j++)
    {
      from = cycles[i][j];
      to = cycles[i][j-1];
      inverse[from] = to;
    }
  }

  // clean up!
  delete lengths;
  for (i = 0; i < num_cycles; i++)
  {
    delete cycles[i];
  }
  delete cycles;
}

With this, we’ll end the entry. Bye!