[算法]交换回溯算法求一维数组的全排列的算法

求一维数组的全排列组合，相比昨天的二维数组，算法相对
要简单得多，运用数据交换和简单的回溯算法即可实现要求，原题为CG最近JAVA考
试题。

原题如下：
求一维数组char a[] = {’1′,’2′,’2′,’3′,’4′,’5′}的所有排列组合，如122345
234512等，要求4不在第三位，5、3不能连在一起，JAVA语言实现算法，写出main
函数即可。

解体思路，任意两个字符交换即可得到新的数组，拼接输出即可，最后还原到原来
的数组，还原的过程即回溯过程。

参考算法(JAVA语言)

public static void main(String[] args) {

    char a[] = {'1','2','2','3','4','5'};
    int i , j;
    //双重循环，交换数据

    for(i = 0 ; i < a.length ; i ++){ //第一个数下标

        for(j = 0 ; j < a.length ; j ++) { //第二个数下标

            //交换

            char temp = a[i] ;
            a[i] = a[j];
            a[j] = temp;
            String s = String.valueOf(a);
            //判断输出

            if( s.charAt(2) != '4' //4不出现在第三位

             && s.indexOf("53") == -1 //不存在53

             && s.indexOf("35") == -1) { //不存在35

             //输出

                System.out.println(s);
            }
            //还原

            temp = a[i] ;
            a[i] = a[j];
            a[j] = temp;
        }
    }
}



1. package com.sw.suanfa.first.ten;
   2.
   3. import java.util.ArrayList;
   4. import java.util.List;
   5.
   6. /**
   7. * 用java语言实现，一个组数：122345这6个数，打印出它所有可能的组合；要求4不能在第3位，3和5不能相连。
   8. * 我的做法：首先，我确定用递归实现。
   9. * 其次，不排除任何条件，打出所有的组合。
  10. * 在递归中增加了preNum，和level参数，可方便的对条件【4不能在第3位，3和5不能相连】进行过滤。
  11. * 在递归正增加了intList，便于排除重复。比如122345这个串中有2个2.则按照以上的算法会出现重复的情况。
  12. * 这里用了一个intList主要是利用其方法indexOf,实际也可以通过数组循环的方式来查找，这里为了方便就用了list。
  13. *
  14. * @author songwei
  15. * @date 2010.3.24
  16. *
  17. */
  18. public class ComposeArray {
  19.
  20. public static void main(String[] args) {
  21. int len = 6;
  22. int[] numArray = {1,2,2,3,4,5};
  23. int[] currentArray = new int[len];
  24. getNextNumber(0,1,numArray,currentArray);
  25.
  26. }
  27.
  28. /**
  29. *
  30. * @param preNum 前一个数值
  31. * @param level 当前层数
  32. * @param numArray 当前层中能够选择的数值集合
  33. * @param currentArray 正在操作的数组，当这个数组中的所有值均覆值后，则为条件允许情况下的一个数值集合。
  34. */
  35. private static void getNextNumber(int preNum,int level,int[] numArray,int[] currentArray){
  36. List<Integer> intList = new ArrayList<Integer>();
  37. for(int i=0;i<numArray.length;i++){
  38. int currentNum = numArray[i];
  39. if(intList.indexOf(Integer.valueOf(currentNum))>-1) continue ;
  40. intList.add(currentNum);
  41.
  42. //4不能在第3位出现

  43. if(level == 3 && currentNum == 4) continue ;
  44. if(level != 1){
  45. //3和5不能相连

  46. if((currentNum ==5 && preNum == 3) || (currentNum ==3 && preNum == 5)){
  47. continue ;
  48. }
  49. }
  50. currentArray[level-1] = currentNum ;
  51. int nextLevel = level +1 ;
  52. if(level == currentArray.length){
  53. OutArray(currentArray);
  54. return ;
  55. }else{
  56. getNextNumber(currentNum,nextLevel,createNewArray(numArray,i),currentArray);
  57. }
  58. }
  59. }
  60.
  61. /**
  62. * 创建一个新的数组，这个数组为该次排列中，下一个level可以出现的数值集合。
  63. * @param oldArray
  64. * @param orderNumber
  65. * @return
  66. */
  67. private static int[] createNewArray(int[] oldArray,int orderNumber){
  68. if(oldArray.length<=1) return null ;
  69. int newLen = oldArray.length-1 ;
  70. int[] newArray =new int[newLen];
  71. int newOrderNumber = 0 ;
  72. for(int i=0;i<oldArray.length;i++){
  73. if(i == orderNumber) continue ;
  74. newArray[newOrderNumber] = oldArray[i];
  75. newOrderNumber ++ ;
  76. }
  77. return newArray;
  78. }
  79.
  80. private static void OutArray(int[] array){
  81. for(int i=0;i<array.length;i++){
  82. System.out.print(array[i]);
  83. }
  84. System.out.println("");
  85. }
  86. }