带条件的排列组合算法分析

算法说明：

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

  

算法代码：

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();
  }
}

 

 

算法分析：

因为是排列组合所以用递归

因为有条件所以递归时要剪枝

可用公式算出合法的排列数，以验证结果：

 

  (A⁶₆ - A⁵₅ - 2·A⁵₅ + 2·C¹₃·A³₃)/2 = 198

 

  第一项为全排列的数量

  第二项为"4"在第三位的数量

  第三项为"3"与"5"相连的数量

  第四项加回二三项重复减去的数量

  因为排列中有两个相同的字符"2"，且在各个位置出现的概率相同，故需将整个结果除2修正

 

此题本身并不难，因为在论坛上看到很多人对排列组合的算法缺乏一般的解题思路，因而贴出，希望能给大家带来帮助。

评论

2 楼 王书兴 2010-12-29  

似乎有问题吧 ，字符串中的数字是按顺序取的，并没有进行排列啊

1 楼 yangguo 2010-09-26  

引用

  if (eleStr.substring(0, i).indexOf(currEle) != -1) continue; //剪掉同一位上字符重复的分支(此题即剪掉重复的2) 

为什么这样能剪掉重复？