排列组合问题

1、使用移位法实现

思路是给定一个数组，其下标表示1到m个数，数组元素的值为1表示其下标代表的数被选中，为0则没选中。首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端（只有第一位变为0才需要移动，否则其左边的1本来就在最左端，无需移动）。当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求5中选3的组合：

1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5

实现：

package com.huawei;

public class Combine {

    public static void main(String[] args) {
        int[] array = new int[] { 1, 2, 3, 4, 5 };
        int m = array.length;
        int n = 3;

        // 初始化移位法需要的数组
        byte[] bits = new byte[m];
        for (int i = 0; i < bits.length; i++) {
            bits[i] = i < n ? (byte) 1 : (byte) 0;
        }

        boolean find = false;
        do {
            // 找到10，换成01
            printCombination(array, bits);
            find = false;
            for (int i = 0; i < m - 1; i++) {
                if (bits[i] == 1 && bits[i + 1] == 0) {
                    find = true;
                    bits[i] = 0;
                    bits[i + 1] = 1;
                    // 如果第一位为0，则将第i位置之前的1移到最左边，如为1则第i位置之前的1就在最左边，无需移动
                    if (bits[0] == 0) {
                        // O(n)复杂度使1在前0在后
                        for (int k = 0, j = 0; k < i; k++) {
                            if (bits[k] == 1) {
                                byte temp = bits[k];
                                bits[k] = bits[j];
                                bits[j] = temp;
                                j++;
                            }
                        }
                    }
                    break;
                }
            }
        } while (find);

    }

    private static void printCombination(int[] array, byte[] bits) {
        for (int i = 0; i < bits.length; i++) {
            if (bits[i] == (byte) 1) {
                System.out.print(" " + array[i] + " ");
            }
        }
        System.out.println(";");
    }
}

2、递归实现

package com.huawei;

import java.util.ArrayList;
import java.util.List;

public class Combination {

    public static void print(List list) {
        for (Object o : list) {
            System.out.print(o);
        }
        System.out.println();
    }

    //每次开始都是将第一个数加入到current_choice集合中，如果集合元素个数等于n则需要将最后一个删除掉
    //之后再进行添加，同时还有一个i的限制条件。
    public static void combination(int n, int position, List str_list,
            List current_choice) {
        
        for (int i = position; i < str_list.size(); i++) {
            current_choice.add((Object) str_list.get(i));
            if (current_choice.size() == n) {
                print(current_choice);
            } else {
                combination(n, i + 1, str_list, current_choice);
            }
            current_choice.remove(current_choice.size() - 1);
        }
    }

    public static void main(String[] args) {
        List str_list = new ArrayList();
        str_list.add("1");
        str_list.add("2");
        str_list.add("3");
        str_list.add("4");
        str_list.add("5");
        List current_choice = new ArrayList();
        combination(3, 0, str_list, current_choice);
    }

}

3、回溯法实现

未完待续。。。