Permutation to Index

N 筆資料的所有排列一共 N! 種。

一個階乘進位數字，可以代表一個排列。

Lehmer code 又稱 Cantor expansion ：右方數字個數，階乘，作為數量級。右方較小的、尚未出現的數字個數，作為位數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 5;                 // 定義陣列長度為 5
int a[N] = {4, 1, 5, 2, 3};     // 輸入的排列
int c[N+1];                      // 樹狀數組，用於計算比當前數字小的數字個數

int permutation_to_index() {
    int fac = 1;                 // 階乘值，用於計算康托展開
    int n = 0;                   // 最終的索引結果
    
    for (int i=1; i<=N; ++i) {
        // 計算比當前位置數字小的數字個數
        int sum = 0;
        for (int x=a[N-i]; x; x-=x&-x) 
            sum += c[x];
            
        n += fac * sum;          // 將結果乘上對應的階乘值
        fac *= i;                // 更新階乘值
        
        // 在樹狀數組中標記已經處理過的數字
        for (int x=a[N-i]; x<=N; x+=x&-x) 
            ++c[x];
    }
    return n;
}

Index to Permutation

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
const int N = 5;
const int lgN = log2(N);
int a[N] = {1, 2, 3, 4, 5}; // sorted
int c[N+1];	// binary indexed tree

void index_to_permutation(int n)
{
	memset(c, 0, sizeof(c));

	int fac = 1;
	for (int i=1; i<N; i++) fac *= i;

	for (int i=1; i<=N; i++)
	{
		int digit = n / fac;
		n %= fac;
		if (N-i) fac /= (N-i);

		// binary search
		int ans = 0;
		for (int k=1<<lgN; k; k>>=1)
		{
			if (ans+k >= N) continue;
			int sum = 0;
			for (int x=ans+k; x; x-=x&-x) sum += c[x];
			if (ans+k - sum <= digit) ans += k;
		}

		for (int x=ans+1; x<=N; x+=x&-x) c[x]++;
		cout << a[ans];
	}
}

enumerate 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
int a[5];
bool used[5];

void print(int N)
{
	for (int i=0; i<N; ++i) cout << a[i];
	cout << '\n';
}

void backtrack(int n, int N)
{
	if (n == N) {print(N); return;}

	for (int i=0; i<N; i++)
		if (!used[i])
		{
			used[i] = true;
			a[n] = i;
			backtrack(n+1, N);
			used[i] = false;
		}
}

void enumerate_permutations(int N)
{
	for (int i=0; i<N; i++) used[i] = false;
	backtrack(0, N);
}