6.2.3 Enumerating Permutations

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

/*

A permutation is an ordered list consisting of $n$ (not necessarily distinct) elements.

- `next_permutation_(lo, hi)` is analogous to `std::next_permutation(lo, hi)`, taking two
  BidirectionalIterators as a range [`lo`, `hi`) for which the function tries to rearrange to the
  next lexicographically greater permutation. The function returns true if such a permutation
  exists, or false if the range is already in descending order (in which case the values are
  unchanged). This implementation requires an ordering on the set of possible elements defined by
  the `<` operator on the iterator's value type.
- `next_permutation(a)` is analogous to `next_permutation()`, except that it takes a vector instead
  of a range.
- `next_permutation(x)` returns the next lexicographically greater permutation of the binary digits
  of the integer `x`, that is, the lowest integer greater than `x` with the same number of 1-bits.
  This can be used to generate combinations of a set of $n$ items by treating each 1 bit as whether
  to "take" the item at the corresponding position.
- `permutation_by_rank(n, r)` returns the permutation of the integers in the range $[0, n)$ which is
  lexicographically ranked $r$, where $r$ is a 0-based rank in the range $[0, n!)$.
- `rank_by_permutation(a)` returns an integer representing the 0-based rank of permutation `a`,
  which must be a permutation of the integers $[0, n)$.
- `permutation_cycles(a)` returns the decomposition of the permutation `a` into cycles. A
  permutation cycle is a subset of a permutation whose elements are consecutively swapped, relative
  to a sorted set. For example, $\{3, 1, 0, 2\}$ decomposes to $\{0, 3, 2\}$ and $\{1\}$, meaning
  that starting from the sorted order $\{0, 1, 2, 3\}$, the 0-th value is replaced by the 3rd, the
  3rd by the 2nd, and the 2nd by the 0-th ($0 \to 3 \to 2 \to 0$).

Time Complexity:
- O(n^2) per call to `next_permutation_(lo, hi)`, where $n$ is the distance between `lo` and `hi`.
- O(n^2) per call to `next_permutation(a)`, `permutation_by_rank(n, r)`, and
  `rank_by_permutation(a)`.
- O(1) per call to `next_permutation(x)`.
- O(n) per call to `permutation_cycles()`.

Space Complexity:
- O(1) auxiliary for `next_permutation_()` and `next_permutation()`.
- O(n) auxiliary heap space for `permutation_by_rank()`, `rank_by_permutation()`, and
  `permutation_cycles()`.

*/

#include <algorithm>
#include <cstdint>
#include <numeric>
#include <vector>

template<class It>
bool next_permutation_(It lo, It hi) {
  if (lo == hi) {
    return false;
  }
  It i = lo;
  if (++i == hi) {
    return false;
  }
  i = hi;
  --i;
  while (true) {
    It j = i;
    if (*--i < *j) {
      It k = hi;
      while (!(*i < *--k)) {
      }
      std::iter_swap(i, k);
      std::reverse(j, hi);
      return true;
    }
    if (i == lo) {
      std::reverse(lo, hi);
      return false;
    }
  }
}

template<class T>
bool next_permutation(std::vector<T> &a) {
  int n = static_cast<int>(a.size());
  for (int i = n - 2; i >= 0; i--) {
    if (a[i] < a[i + 1]) {
      for (int j = n - 1;; j--) {
        if (a[i] < a[j]) {
          std::swap(a[i++], a[j]);
          for (j = n - 1; i < j; i++, j--) {
            std::swap(a[i], a[j]);
          }
          return true;
        }
      }
    }
  }
  return false;
}

int64_t next_permutation(int64_t x) {
  int64_t s = x & -x, r = x + s;
  return r | (((x ^ r) >> 2) / s);
}

std::vector<int> permutation_by_rank(int n, int64_t x) {
  std::vector<int64_t> factorial(n);
  std::vector<int> values(n), res(n);
  factorial[0] = 1;
  for (int i = 1; i < n; i++) {
    factorial[i] = i * factorial[i - 1];
  }
  std::iota(values.begin(), values.end(), 0);
  for (int i = 0; i < n; i++) {
    int pos = x / factorial[n - 1 - i];
    res[i] = values[pos];
    std::copy(values.begin() + pos + 1, values.end(), values.begin() + pos);
    x %= factorial[n - 1 - i];
  }
  return res;
}

int64_t rank_by_permutation(const std::vector<int> &a) {
  int n = static_cast<int>(a.size());
  std::vector<int64_t> factorial(n);
  factorial[0] = 1;
  for (int i = 1; i < n; i++) {
    factorial[i] = i * factorial[i - 1];
  }
  int64_t res = 0;
  for (int i = 0; i < n; i++) {
    int v = a[i];
    for (int j = 0; j < i; j++) {
      if (a[j] < a[i]) {
        v--;
      }
    }
    res += v * factorial[n - 1 - i];
  }
  return res;
}

using cycles = std::vector<std::vector<int>>;

cycles permutation_cycles(const std::vector<int> &a) {
  int n = static_cast<int>(a.size());
  std::vector<bool> visit(n);
  cycles res;
  for (int i = 0; i < n; i++) {
    if (!visit[i]) {
      int j = i;
      std::vector<int> curr;
      do {
        curr.push_back(j);
        visit[j] = true;
        j = a[j];
      } while (j != i);
      res.push_back(std::move(curr));
    }
  }
  return res;
}

/*** Example Usage and Output:

Permutations of [0, 4):
{0,1,2,3} {0,1,3,2} {0,2,1,3} {0,2,3,1} {0,3,1,2} {0,3,2,1} {1,0,2,3} {1,0,3,2}
{1,2,0,3} {1,2,3,0} {1,3,0,2} {1,3,2,0} {2,0,1,3} {2,0,3,1} {2,1,0,3} {2,1,3,0}
{2,3,0,1} {2,3,1,0} {3,0,1,2} {3,0,2,1} {3,1,0,2} {3,1,2,0} {3,2,0,1} {3,2,1,0}

Permutations of 2 zeros and 3 ones:
00111 01011 01101 01110 10011 10101 10110 11001 11010 11100

Decomposition of {3,1,0,2} into cycles:
{0,3,2} {1}

***/

#include <bitset>
#include <cassert>
#include <iostream>
using namespace std;

template<class It>
void print_range(It lo, It hi) {
  cout << "{";
  for (; lo != hi; ++lo) {
    cout << *lo << (lo == hi - 1 ? "" : ",");
  }
  cout << "} ";
}

int main() {
  {
    const int n = 4;
    vector<int> a{0, 1, 2, 3}, b = a, c = a;
    cout << "Permutations of [0, " << n << "):" << endl;
    int count = 0;
    do {
      print_range(a.begin(), a.end());
      assert(b == a);
      assert(c == a);
      vector<int> d = permutation_by_rank(n, count);
      assert(d == a);
      assert(rank_by_permutation(a) == count);
      count++;
      if (count == 8 || count == 16) {
        cout << endl;
      }
      std::next_permutation(b.begin(), b.end());
      next_permutation(c);
    } while (next_permutation(a));
    cout << endl;
  }
  {  // Permutations of binary digits.
    const int n = 5;
    cout << "\nPermutations of 2 zeros and 3 ones:" << endl;
    int lo = bitset<5>(string("00111")).to_ulong();
    int hi = bitset<6>(string("100011")).to_ulong();
    do {
      cout << bitset<n>(lo).to_string() << " ";
    } while ((lo = next_permutation(lo)) != hi);
    cout << endl;
  }
  {  // Decomposition into cycles.
    vector<int> a{3, 1, 0, 2};
    cout << "\nDecomposition of {3,1,0,2} into cycles:" << endl;
    cycles c = permutation_cycles(a);
    for (const auto &cycle : c) {
      print_range(cycle.begin(), cycle.end());
    }
    cout << endl;
  }
  return 0;
}