Noob
0%

Permutation(排列相关的算法)

发表于 更新于 分类于 ，

All Permutations(Recursive)

该算法采用DFS递归的方法，每次从当前元素出发，依次与它后面的元素交换，到序列结尾时表示完成一次全排列，输出结果。注意，每次递归返回后再把元素交换回来，否则会出现重复序列。该算法时间复杂度为O(n!)，序列不是递增的。例如对“123”全排列的结果为：123 132 213 231 321 312。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void swap(StringBuilder sb, int i, int j) {
        char c = sb.charAt(i);
        sb.setCharAt(i, sb.charAt(j));
        sb.setCharAt(j, c);
}
public void nextPermutation(StringBuilder sb, int start) {
    if(start == sb.length())
        println(sb);
    for (int i = start; i < sb.length(); ++i) {
        swap(sb, start, i);
        nextPermutation(sb, start + 1);
        swap(sb, start, i);
    }
}

Next permutation

以[2, 4, 5, 3, 1]为例，算法思路：

  1. 从右向左扫描，找到第一个非递增数（4）
    1. 从右向左扫描，找到第一个比这个数大的数（5）
    2. 交换这两个数，[2, 5, 4, 3, 1]
    3. 排列从交换起始位至最后一个元素，[2, 5, 1, 3, 4]
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
private void swap(StringBuilder sb, int i, int j) {
    char c = sb.charAt(i);
    sb.setCharAt(i, sb.charAt(j));
    sb.setCharAt(j, c);
}

private void reverse(StringBuilder sb, int start, int end) {
    int mid = (end - start + 1) / 2;
    for(int i = 0; i < mid; ++i) {
        char c = sb.charAt(start + i);
        sb.setCharAt(start + i, sb.charAt(end - i));
        sb.setCharAt(end - i, c);
    }
}

public String nextPermutation(StringBuilder sb, int cnt, int k) {
    while(cnt < k) {
        ++cnt;
        int i = sb.length() - 1;
        while(i - 1 >= 0 && sb.charAt(i) <= sb.charAt(i - 1))
            --i;
        if(i <= 0) {
            reverse(sb, 0, sb.length() - 1);
            continue;
        }
        int j = sb.length() - 1;
        while(j > i - 1 && sb.charAt(j) <= sb.charAt(i - 1) )
            --j;
        swap(sb, j, i - 1);
        reverse(sb, i, sb.length() - 1);
    }
    return new String(sb);
}

Kth Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public String getPermutation(int n, int k) {
    StringBuilder init = new StringBuilder();
    StringBuilder result = new StringBuilder();
    int total = 1;
    for(int i = 1; i <= n; ++i) {
        total *= i;
        init.append(i);
    }
    for(int i = n; i >= 1; --i) {
        total /= i;
        int index = (k - 1) / total;
        k = k - index * total;
        result.append(init.charAt(index));
        init.deleteCharAt(index);
    }
    return new String(result);
}