改编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; 
}