疯狂java


您现在的位置: 疯狂软件 >> 新闻资讯 >> 正文

n个不同元素中任取m个元素


 

   * 全排列: 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

  * [1,n],[1,n-1],[1,n-2]……[1]

  *

  */

  public class WholeArray {

  //组合数

  private static int totalTime=0;

  /**

  * m*(m-1)*……*1的实现

  * @param numbers

  * @param numbersTemp

  * @param marks

  * @param m

  */

  public static void printWholeArray(String[] numbers, String[] numbersTemp,

  boolean marks[], int m) {

  for (int j = 0; j < marks.length; j++) {

  if (!marks[j]) {

  break;

  }

  if(j==marks.length-1 && marks[j]){

  // marks数组里都标志位true了,完成一次全排列,输出一组排列

  //printArray(numbersTemp);

  totalTime++;

  break;

  }

  }

  /*if(m==0){

  return;

  }*/

  /*boolean flag = false;*/

  for (int j = 0; j < marks.length; j++) {

  if (!marks[j]) {//如果[1,n]或[1,n-1]或[1,n-2]……或[1]中没有使用过的选择

  numbersTemp[numbers.length - m] = numbers[j];

  marks[j] = true;//标志为已用

  // 处理剩余的i-1个数的全排列

  printWholeArray(numbers, numbersTemp, marks, m - 1);

  /*flag = false;*/

  marks[j] = false;//标志为未用

  }/*else if(j==marks.length-1 && marks[j] && flag){

  // marks数组里都标志位true了,完成一次全排列,输出一组排列

  printArray(numbersTemp);

  totalTime++;

  break;

  }*/

  }

  }

  /**

  * 输出数组numbers的全排列

  *

  * @param numbers

  */

  public static void printWholeArray(String[] numbers) {

  if (numbers == null || numbers.length == 0) {

  return;

  } else {

  String numbersTemp[] = new String[numbers.length];// 可变的输出数组

  boolean marks[] = new boolean[numbers.length];// 标记当前元素是否被使用

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

  numbersTemp[i] = numbers[i];

  marks[i] = false;

  }

  printWholeArray(numbers, numbersTemp, marks, numbers.length);

  }

  }

  /**

  * 输出全排列

  * @param numbers

  */

  public static void printArray(String[] numbers) {

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

  System.out.print(numbers[i] + " ");

  }

  System.out.println();

  }

  public static void main(String[] args) {

  int count = 5;//5*4*3*2*1

  String numbers[] = new String[count];

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

  numbers[i] = i + 1 + "";

  }

  printWholeArray(numbers);

  System.out.println("共有:"+totalTime+"个组合");

  }

  }