算法-全排列和全组合

发表于 | 分类于 ，

全排列

问题描述

  • 输入一个字符串，求字符串包含元素（含重复，比如aab的情况）的所有排列可能。

  • 例如：输入abc,所有排列组合包括: abc, acb, bac, bca, cab, cba。

递归解法

  • 思路：如果输入为abcdef，则首先确定排列的第一个字母，有6中可能，如果选定a,则其后接bcdef的全排列，明显适用于递归结题。结题思路为第一个字母分别选定所有可能的情况，然后对剩下的字母进行递归。递归终止条件为选定的字母的下标为字符串长度-1。

  • 实现

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
public class AllSort {
    private static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Permutation(str.toCharArray(), str.length(), 0);
        System.out.println(list.toString());
    }
    private static void Permutation(char[] chars, int strLen, int curIndex) {
        //如果到最后一个数，将排好的加入到list中
        if (curIndex == strLen - 1) {
            list.add(new String(chars));
        } else {
            for (int i = curIndex; i <= strLen - 1; i++) {
                //去重，避免相同数字的交换造成最终结果存在重复
                if (i == curIndex || chars[i] != chars[curIndex]) {
                    //依次交换开头字母与后面的进行递归
                    Swap(chars, i, curIndex);
                    Permutation(chars, strLen, curIndex + 1);
                    Swap(chars, i, curIndex);
                }
            }
        }
    }
    private static void Swap(char[] chars, int i, int curIndex) {
        char tmp = chars[i];
        chars[i] = chars[curIndex];
        chars[curIndex] = tmp;
    }
}

字典序法

  • 思想：将输入排序，如输入为1234，则其最小值为1234，然后下一次加入的值为除了1234以外，1,2,3,4组成的最小的值。获取方法为从末尾找第一个从右向左不递增的数a，然后找到从末尾开始从右向左第一个大于a的数，并将这两个数交换次序。然后将原来a的位置之后的字符串反序。也就是说1234，的下一个为1243，在下一个为1324..直到字符串从右向左递增为止。

实现：

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
public class AllSort {
    private static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        PermutationWithDictionary(str.toCharArray(), str.length());
        System.out.println(list.toString());
    }
    private static void Swap(char[] chars, int i, int curIndex) {
        char tmp = chars[i];
        chars[i] = chars[curIndex];
        chars[curIndex] = tmp;
    }
    private static void PermutationWithDictionary(char[] chars, int strLen) {
        //对字符数组进行排序
        Arrays.sort(chars);
        while (true) {
            int j;
            int index = 0;
            //找到从右向左第一个不是非递增元素
            for (j = strLen - 2; j >= 0; j--) {
                if (chars[j] < chars[j+1]){
                    index = j;
                    break;
                } else if (j == 0){
                    return;
                }
            }
            //与从右向左第一个大于这个元素的元素交换
            for (j = strLen - 1; j >= 0; j--) {
                if (chars[j] > chars[index]) {
                    break;
                }
            }
            //交换这两个值
            Swap(chars, index, j);
            //对非递增元素位置后面的数组进行逆序排序
            Reverse(chars, index+1);
            list.add(new String(chars));
        }
    }
    private static void Reverse(char[] chars, int index) {
        int k = index, j = chars.length-1;
        while (k < j) {
            Swap(chars,k,j);
            k++;
            j--;
        }
    }
}

全组合

  • 题目描述：输入一个字符串，求字符的所有组合。如abc,则输出可能为a,b,c,ab,ac,bc,abc。
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
public class AllCombine {
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        combinetion(str.toCharArray(), str.length());
        System.out.println(list.toString());
    }
    private static void combinetion(char[] chars, int length) {
       if (chars == null || length == 0)
           return;
        List<Character> array = new ArrayList<>();
        //n中情况分别考虑
        for (int i = 1; i <= length; i++) {
            combine(chars, 0, i, array);
        }
    }
    /**
     * 从字符数组中index以后挑选number个数加入list
     * @param chars 输入的字符数组
     * @param index 开始字符下标
     * @param number
     * @param array
     */
    private static void combine(char[] chars, int index, int number, List<Character> array) {
        if (number == 0) {
            //递归终止条件，判断是为了去重
            if (!list.contains(array.toString())) {
                list.add(array.toString());
            }
            return;
        }
        if (index == chars.length) {
            return;
        }
        //取当前元素，并考察递归选取n-1个元素的情况
        array.add(chars[index]);
        combine(chars, index+1, number - 1, array);
        array.remove((Character) chars[index]);
        //不取当前元素，考察后面选取n个元素
        combine(chars, index+1, number, array);
    }
}
  • 基于位图：假定元素有n个，则最终结果组合为2^n-1个，我们使用位操作方法：假设元素原本为123，则1表示取该元素，0表示不取该元素。000是没有意义是，则选取的对应如下：
    001,010,100,011,101,110,111->a,b,c,bc,ac,ab,abc。
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
public class AllCombine1 {
    static ArrayList<String> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        combinetion(str.toCharArray());
        System.out.println(list.toString());
    }
    private static void combinetion(char[] chars) {
        if (chars == null || chars.length == 0)
            return;
        int len = chars.length;
        //n=2^len
        int n = 1<<len;
        for (int i = 1; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < len; j++) {
                int temp = i;
                if ((temp & (1<<j)) != 0)
                    sb.append(chars[j]);
            }
            list.add(sb.toString());
        }
    }
}
Donate comment here