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

一、概念

以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等编程技术的技巧经验分享。

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