1

首先，我不是以英语为母语的人，所以请原谅我的一些错误和错误。

我想改组一个 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 可以放在任何地方
  • 改组后的 List 可能是这样的：0, 3, 6, 5, 2, 1, 4

好吧，我认为仅此而已。

如果我想创建多个 if 语句，我的主要问题是找出有效链接它们的正确方法（以便考虑每个 if 语句）。

4

2 回答 2

1

改组方法不好，原因有两个：

  1. 可能没有解决方案，因此您的程序将随机播放直到所有时间结束。
  2. 随着元素数量的变化，这将变得非常耗时。

我建议另一种解决方案：

  • 我们得到一组数字（可以用一个列表表示）
  • 如果给定的数字可以扩展我们目前的结果列表，我们需要一个返回 true 的布尔函数canFollow。（您给出的规则将允许使用两个数字的更简单的函数，但对于更复杂的条件，例如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])

（请注意，result + i 是 result with i appended and given 的缩写 - i 是在没有 i 的情况下给出的，但请确保在不破坏原始结果和给出的情况下构造它。）

如果您需要所有解决方案，可以通过将有效结果添加到一些以空开头的列表来轻松更改。

于 2014-01-06T12:03:50.550 回答
0

假设您要求所有可能的结果都同样可能，那么唯一简单的方法就是暴力创建所有组合，然后从中随机选择。所有的组合都是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;
}
于 2014-01-06T12:09:29.107 回答