改編ArrayList直到條件滿足（Java）

Question

首先，我不是英語母語的人，所以請原諒我一些錯誤和錯誤。

我想洗牌ArrayList（沒有問題），但洗牌後列表必須滿足某些條件。 我的第一個方法是創建if語句並在每次他們都是真實時洗牌。但是有這麼多的條件，我不知道如何正確地鏈接它們。

例子： 我有這些整數一個ArrayList：

0, 1, 2, 3, 4, 5, 6 

條件洗牌後：

• 偶數不能跟偶數，除非它是6
• 6可以放在任何地方。
• 另外例如0不能隨後用1，所以下一個可能的數目將 是3,5，或6。（
• 同樣爲例如1 1只能隨後0,4或6

ArrayList中的每個元素都應該只列出一次，這就是爲什麼我認爲洗牌會是創建新列表的最簡單方式。

我是否錯誤？是否有更簡單的方法？編程... 在此先感謝您的任何回答或建議。

編輯：這裏是所有條件：

• 該列表具有帶有偶數開始（由6優選不，但這並不重要）
• 偶數不能再接再偶數
• 一個數字可以（1不能跟着2，只有0,4或6）
• 如前所述：6可以放在任何地方
• 混洗列表可能是這樣的： 0，3，6，5，2，1，4

嗯，我認爲就是這樣。

如果我想創建多個if語句，我的主要問題是找出有效鏈接它們的正確方法（以便考慮每個if語句）。

Answer 1

的洗牌方法是不行的，原因有二：

1. 可能沒有甲腎上腺素的解決方案，因此，你的程序將洗牌，直到所有的時間結束。
2. 隨着元素數量的變化，這將非常耗時。

我建議另一種解決方案：

• 我們給出了一組數字（可以用列表來表示）
• 我們需要一個布爾函數canFollow返回true，如果給定數量的可擴展我們迄今爲止的結果列表。 （你給的規則將允許一個更簡單的函數，它接受兩個數字，但對於更復雜的情況像5 can be followed by 8 only when not preceded by 6更普遍的功能是可行的。）
• 一旦你有了這個，你可以構建一個解決方案：用空開始了名單。雖然給定的集合不是空的，但從中獲取一個元素，並檢查它是否可以跟隨結果。如果是這樣，重複，直到給定的集合是空的，在這種情況下，你有一個解決方案。否則，請嘗試下一個數字：

在僞代碼：

List<Int> brute(List<Int> result, List <Int> given) { 
    if (given is empty) return result; 
    foreach i in given 
     if i can follow result 
      r = brute(result + i, given - i) 
      if r != null return r 
    return null 
} 
solution = brute([], [1,2,3,4,5,6]) 

（請注意，結果+我是短期的結果和我追加並給予 - 我沒有我給出，但要確保你構建此不destryoing原來的結果，並給出）。

如果你需要的所有解決方案，這可以很容易地通過增加有效結果的一些列表開始是空的改變。

Answer 2

假設你有一個要求，即所有可能的結果是等可能的，那麼唯一的簡單的方法將是窮舉創建所有組合，然後從該隨機選擇。所有組合都是7! == 7*6*5*4*3*2*1 == 5040組合，其實並不是很多。對於更大的數字，我不會推薦這種方法。

List<int[]> valid = new ArrayList<>(5040); 

recursiveBuild(valid, new int[] {}, new int[] { 0,1,2,3,4,5,6)); 

其中recursiveBuild是：

void recursiveBuild(List<int[]> valid, int[] soFar, int[] remaining) { 

    if (remaining.length == 0) { 
     // Check the whole thing is valid - can maybe skip this check 
     // if the character-by-character check covers everything 
     if (isValid(soFar)) { 
      valid.add(soFar); 
     } 
    } else { 
     for (int i=0;i<remaining.length;i++) { 
      int[] newSoFar = new int[soFar.length+1]; 
      for (int j=0;j<soFar.length;j++) { 
       newSoFar[j]=soFar[j]; 
      } 
      newSoFar[newSoFar.length-1]=remaining[i]; 

      int[] newRemaining = new int[remaining.length-1]; 
      for (int j=0;j<newRemaining.length;j++) { 
       if (j>=i) { 
        newRemaining = remaining[j+1]; 
       } else { 
        newRemaining = remaining[j]; 
       } 
      } 

      // Only continue if the new character added is valid 
      if (isValid(newSoFar, newSoFar.length-1) 
       recursiveBuild(valid, newSoFar, newReamining); 
     } 
    } 
} 

爲了解決你上市我會用一個變型的策略模式的實際問題，確定每個規則作爲自己的對象（在Java中8個倒閉將使該更詳細）：

interface CheckCondition { 
    boolean passesCondition(int index, int[] arr); 
} 


CheckCondition[] conditions = new CheckCondition[] { 
    new CheckCondition() { 
     @override 
     public boolean passesCondition(int index, int[] arr) { 
      // The list has to start with an even number 
      return index!=0 || arr[index]%2==0; 
     } 
    }, 
    new CheckCondition() { 
     @override 
     public boolean passesCondition(int index, int[] arr) { 
      // an even number can't follow an even number, unless it's 6. 
      return index==0 || arr[index]==6 || arr[index]%2==1 || arr[index-1]%2==1; 
     } 
    }, 
    new CheckCondition() { 
     @override 
     public boolean passesCondition(int index, int[] arr) { 
      // a number can't be followed by the next closest one unless its 6 
      return index==0 || arr[index]!=arr[index-1]-1 || arr[index]==6; 
     } 
    }, 
}; 

現在用這些規則來檢查的有效性：

boolean isValid(int[] arr, int index) { 
    for (CheckCondition c: conditions) 
     if (!c.passesCondition(arr.length-1, arr) 
      return false; 
    return true; 
} 

boolean isValid(int[] arr) { 
    for (int i=0;i<arr.length;i++) { 
     if (!isValid(arr, i); 
      return false; 
    } 
    return true; 
}