【每天算法2】：用java語言實作，一個組數：122345這6個數，列印出它所有可能的組合；要求4不能在第3位，3和5不能相連。

一個組數：122345這6個數，列印出它所有可能的組合；要求4不能在第3位，3和5不能相連。

我在實作這個算法的時候，按照len不固定的方式，利用遞歸方式進行處理。

感覺我的算法複雜度還是挺高的。過程中，不斷的建立新的數組列别。

如果你有更好的算法，請發上來，可以好好學習下。

package com.sw.suanfa.first.ten;

import java.util.ArrayList;

import java.util.List;

/**

* 用java語言實作，一個組數：122345這6個數，列印出它所有可能的組合；要求4不能在第3位，3和5不能相連。

* 我的做法：首先，我确定用遞歸實作。

* 其次，不排除任何條件，打出所有的組合。

* 在遞歸中增加了preNum，和level參數，可友善的對條件【4不能在第3位，3和5不能相連】進行過濾。

* 在遞歸正增加了intList，便于排除重複。比如122345這個串中有2個2.則按照以上的算法會出現重複的情況。

* 這裡用了一個intList主要是利用其方法indexOf,實際也可以通過數組循環的方式來查找，這裡為了友善就用了list。

*

* @author songwei

* @date 2010.3.24

*

*/

public class ComposeArray {

public static void main(String[] args) {

int len = 6;

int[] numArray = {1,2,2,3,4,5};

int[] currentArray = new int[len];

getNextNumber(0,1,numArray,currentArray);

}

/**

*

* @param preNum 前一個數值

* @param level 目前層數

* @param numArray 目前層中能夠選擇的數值集合

* @param currentArray 正在操作的數組，當這個數組中的所有值均覆值後，則為條件允許情況下的一個數值集合。

*/

private static void getNextNumber(int preNum,int level,int[] numArray,int[] currentArray){

List<Integer> intList = new ArrayList<Integer>();

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

int currentNum = numArray[i];

if(intList.indexOf(Integer.valueOf(currentNum))>-1) continue ;

intList.add(currentNum);

//4不能在第3位出現

if(level == 3 && currentNum == 4) continue ;

if(level != 1){

//3和5不能相連

if((currentNum ==5 && preNum == 3) || (currentNum ==3 && preNum == 5)){

continue ;

}

}

currentArray[level-1] = currentNum ;

int nextLevel = level +1 ;

if(level == currentArray.length){

OutArray(currentArray);

return ;

}else{

getNextNumber(currentNum,nextLevel,createNewArray(numArray,i),currentArray);

}

}

}

/**

* 建立一個新的數組，這個數組為該次排列中，下一個level可以出現的數值集合。

* @param oldArray

* @param orderNumber

* @return

*/

private static int[] createNewArray(int[] oldArray,int orderNumber){

if(oldArray.length<=1) return null ;

int newLen = oldArray.length-1 ;

int[] newArray =new int[newLen];

int newOrderNumber = 0 ;

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

if(i == orderNumber) continue ;

newArray[newOrderNumber] = oldArray[i];

newOrderNumber ++ ;

}

return newArray;

}

private static void OutArray(int[] array){

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

System.out.print(array[i]);

}

System.out.println("");

}

}

今天的任務又完成了。看明天了。剛找了一道題，看着比較麻煩，不知道明天能不能寫出來！嘿

明天的題目:

有一個二維Vector，每個元都是字元串（或者其他對象），如下面這個三行，每行元素不固定的二維Vector  V。

                      A、B、C、D

                      H、I、J、K、M

                      X、Y、Z

      求出滿足以下條件的所有Vector D（一定是所有可能的情況）：

1.此Vector D的元素包含V的所有元素，且每個元素僅出現一次

2. 此Vector D中包含在V[1]中的元素之間的順序不能發生改變，即A、B、C、D之間的順序不發生改變，同理，V[2]、V[3]。都不發生改變。對于本例，也就是說，在結果D中，A、B、C、D的先後順序不變，H、I、J、K、M的先後順序不變，X、Y、Z的先後順序不變。結果D的幾種可能的情況是：

            1：A、B、C、D、H、I、J、K、M、X、Y、Z

            2：H、I、A、B、C、X、D、J、K、Y、Z、M

            3：A、H、I、X、Y、Z、B、C、J、K、M、D等等

随便找了一道，不仔細看了，好好工作了。明天再仔細觀摩一下。