用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列

用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连 

 

这道笔试题相当的出名，我也有幸遇到了。确切的说这是一道算法题，像我这种离散，数据结构都半吊子的人实在拿它没撤，回来小发愤了一下，找到了多个不同的实现算法

第一个：

package com.audition;
//排序组合算法
public class PermutationAlgo {
  private int count = 0;
  
  public void calculate(){
    String eleStr = "122345";
    depthSearch(eleStr, "");
    System.out.println("符合条件的总结果数为:"+count+"条");
  }
  
  /**
   * @param eleStr - 待分配字符组成的串
   * @param rstStr - 已分配字符组成的串
   */
  public void depthSearch(String eleStr, String rstStr) {
    if (eleStr.length() == 0) {
      count++;
      System.out.println(rstStr);
      return;
    }
    for (int i = 0; i < eleStr.length(); i++) {
      String currEle = eleStr.substring(i, i + 1); //取出当前位的值
      if (rstStr.length() == 2 && "4".equals(currEle)) continue; //剪掉第三位为4的分支
      if (rstStr.endsWith("3") && "5".equals(currEle)) continue; //剪掉"35"相连的分支
      if (rstStr.endsWith("5") && "3".equals(currEle)) continue; //剪掉"53"相连的分支
      if (eleStr.substring(0, i).indexOf(currEle) != -1) continue; //剪掉同一位上字符重复的分支(此题即剪掉重复的2)
      depthSearch(eleStr.substring(0, i) + eleStr.substring(i + 1), rstStr + currEle); //用剩余的合法串继续递归
    }
  }
  
  public static void main(String[] args) {
    new PermutationAlgo().calculate();
  }
}

 第二个

package com.audition;

public class PermutationAlgo2 {
	private static int count = 0;
	    public static void main(String[] args) {
	        // 本题的思路是先用 1,3,4,5 进行全排列
	        // 后边再将另外两个 2 往里插入，并判断是否符合要求
	        int[] arr = { 1, 3, 4, 5 };
	        printCom(arr, 0);
	        System.out.printf("符合要求的排列共有 %d 种", count);
	    }
	
	    public static void printCom(int[] arr, int index) {
	        if (index == arr.length - 1) {
	            insertTwo(arr, 0);
	            return;
	        }
	        printCom(arr, index + 1);
	        for (int i = index + 1; i < arr.length; i++) {
	            arr[index] ^= arr[i];
	            arr[i] ^= arr[index];
	            arr[index] ^= arr[i];
	            printCom(arr, index + 1);
	            arr[index] ^= arr[i];
	            arr[i] ^= arr[index];
	            arr[index] ^= arr[i];
	        }
	    }
	
	    // 将 2 在符合要求的情况下插入数组
	    private static void insertTwo(int[] arr, int index) {
	        if (index == arr.length + 1)
	            return;
	        for (int i = index + 1; i < arr.length + 2; i++) {
	            int[] tar = new int[arr.length + 2];
	            tar[i] = 2;
	            tar[index] = 2;
	            innerInsert(arr, tar);
	        }
	        insertTwo(arr, index + 1);
	    }
	
	    private static void innerInsert(int[] arr, int[] tar) {
	        int index = 0;
	        int indexArr = 0;
	        while (index < tar.length) {
	            if (tar[index] == 0) {
	                if ((index > 0 && tar[index - 1] + arr[indexArr] == 8)
	                        || (index == 2 && arr[indexArr] == 4))
	                    return;
	                tar[index] = arr[indexArr++];
	            }
	            index++;
	        }
	        count++;
	        System.out.printf("[%d]", count);
	        for (int i = 0; i < tar.length; i++) {
	            System.out.print(tar[i] + " ");
	        }
	        if(count % 5 == 0){
	            System.out.println();
	        }
	    }
	
}

 第三个

package com.audition;

/**
 * 用1、2、2、3、4、5这六个数字，用java写一个程序，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"
 * 不能相连。
 * 
 * 
 * @author Administrator
 * 
 */
public class PermutationAlgo3 {
	private int[] numbers = new int[] { 1, 2, 2, 3, 4, 5 };
	public int n;
	private String lastResult = "";

	private boolean validate(String s) {
		if (s.compareTo(lastResult) <= 0)
			return false;
		if (s.charAt(2) == '4')
			return false;
		if (s.indexOf("35") >= 0 || s.indexOf("53") >= 0)
			return false;
		return true;
	}

	public void list(String index, String result) {
		for (int i = 0; i < numbers.length; i++) {
			if (index.indexOf(i + 48) < 0) {
				String s = result + String.valueOf(numbers[i]);
				if (s.length() == numbers.length) {
					if (validate(s)) {
						System.out.println(s);
						lastResult = s;
						n++;
					}
					break;
				}
				list(index + String.valueOf(i), s);
			}
		}
	}
	

	public static void main(String[] args) {
		PermutationAlgo3 algo3 = new PermutationAlgo3();
		algo3.list("", "");
		System.out.println("总数：" + algo3.n);
	}
}

 运行结果都是198个

 

 

评论

2 楼 xiangxuehai_jiaer 2011-10-15  

idea:

1 楼 hyj1254 2011-07-14  

用排列组合算出来是198

(6!-5!-5*(4!)+3*(3!)*2)/2