大厂面试：排列与组合傻傻分不清楚

一、概念

以a、b、c三个字符来举例。

1）排列：全排列即字符不能重复，第一位有3种选择，第二位有2种选择，第三位有1种选择，所以最后有3*2*1=6种结果。

2）组合：组合不要求三个字符都必须加入结果。

求所有组合也就是abc各个位是否选取的问题，第一位2种可能，第二位2种可能，以此类推，一共有2^n种可能。用0表示不取，1表示选取，这样可以用110这样的形式表示ab。

abc一共的表示形式从0到2^3-1。然后按位与运算，如果结果为1就输出当前位，为0则不输出。

二、代码

1）排列

public class Permutation {

    public static void main(String[] args) {

        char[] array = {'a','b','c'};

        backtrace(array, 0, array.length);

    }

    public static void backtrace(char[] array, int start, int len){

        if(start == len-1){

            for(int i=0; i<array.length; ++i)

                System.out.print(array[i]);

            System.out.println();

            return;

        }

        for(int index=start; index<len; ++index){

//交换start与index位置对应的值

            swap(array, start, index);

//继续回溯

            backtrace(array, start+1, len);

//将交换复原

            swap(array,start,index);

        }

    }

    //交换array字符数组中索引为i和j位置的元素

    private static void swap(char[] array, int i, int j) {

        if (i != j) {

            char t = array[i];

            array[i] = array[j];

            array[j] = t;

        }

    }

}

2）组合

public class Combination {

    public static void main(String[] args) {

        //待组合的元素

        char[] array = {'a','b','c'};

        //调用获取组合结果函数

        combination(array);

    }

//求组合结果

    public static void combination(char[] array) {

        int len = array.length;

//临时变量从0到nbits-1

        int nbits = 1 << len;

        for (int i = 0; i < nbits; ++i) {

            int t;

            for (int j = 0; j < len; j++) {

                t = 1 << j;

                //若t和i的字符相与不为0，则取j位置的字符

                if ((t & i) != 0) {

                    System.out.print(array[j]);

                }

            }

            System.out.println();

        }

    }

}

---

致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。