0

我有一系列 N 个布尔值。他们中的一些人依赖于其他人。例如，如果 N[0] 为假，则所有其他人也必须为假。如果 N[0] 为真，则 N[1] 可以为真或假。如果 N[1] 为假，则 N[2] 必须为假，但所有其他布尔值仍然可以为真或假。

我想要一个程序向我展示序列的所有可能排列，但我不知道如何在不写出一系列if/then语句的情况下做到这一点。有人建议我可以使用枚举，但根据我对枚举工作原理的理解，我仍然会得到一长串的if/then陈述，而且它只适用于这个单一的问题。几天来我一直在考虑这个问题，试图弄清楚如何构建更动态的东西。伪代码看起来像这样：

public List<string> permutations (int N, int[][] dependencies)
{
     Create boolean array of size N;
     Set array[0] to false;
     Check dependencies on array[0], flip other values accordingly -- in this case, the permutation is complete. All values are 0.
     Set array[0] to true;
     Check dependencies...
     Set array[1] to false;
     Check...
     Set array[1] to true;
     ...
}

它可能有一个循环：

foreach (bool b in array)
{
     b = false;
     Check dependencies and set values
     b = true;
     Check dependencies and set values
}

希望这个问题在这一点上很清楚。除此之外if/then还有其他设置看门人的方法吗？或者嵌套/级联if/then语句是处理这个问题的正确方法吗？

编辑

针对规则是什么的问题，这是我的问题的一部分。这里的规则可以是动态的吗？我可以采用任何 N 个布尔值序列，将其中一些标记为依赖项，或者标记为门，然后提出所有排列吗？这是一组可能的规则

  1. 如果元素 B 依赖于元素 A，那么只要 A 为假，元素 B 就为假。
  2. 如果元素 B 依赖于元素 A 并且元素 A 为真，则 B 可以为真或假。
  3. 依赖关系可以是一对一或一对多。如果元素 B 依赖于元素 A，则元素 C 也可能依赖于元素 A。元素 C 不必依赖于元素 B。

考虑这种情况——（A：B，C，D，E，F；F：G，H）（意味着BE依赖于A，GH依赖于F。如果A为假，则一切都是假的。如果A为真，BF可以为真或假，然后我们开始下一关。如果F为假，GH为假。如果F为真，则GH可以为真或假。

所以我的输出应该是从 AH=false 到 AH=true 的所有可能的值组合。

4

1 回答 1

1

蛮力方式：

public List<Boolean[]> validPermutations (int N, Dependency[] rules){
    List<Boolean[]> list = new ArrayList<Boolean[]>();
    boolean[] perm = new boolean[N];//the permutation to test. initially all false
    for(int pcount = 1; pcount <= Math.pow(2, N)); p++){
        boolean valid = true;
        for(Dependency d : rules){
            if(!d.isSatisfied(perm)){
                valid = false;
                break;
            }
        }
        if(valid) list.add(perm);
        //now "increment" the boolean array to the next permutation
        //it will take on all 2^N possibilites over the course of the for loop
        boolean notDoneShifting = true;
        int i = 0;
        while(notDoneShifting){
            notDoneShifting = perm[i];
            perm[i] = !perm[i];
            i++;
        }
    }
}

如您所见，您只需为每种依赖项编写一次 if/else 测试。这就是循环和其他控制语句的用途！

一个更有效的算法（或者可能不是，现在我认为它）将存储一个大小为 2^N 的表，以确定每个排列是否可能。然后，您将逐个检查依赖项，并为每个标记不可能排除它所排除的可能性。（类似于素筛）您必须在此处概括循环以修复某些索引并迭代其余索引。例如“如果元素 A 为假，则元素 B 为假”...表中索引的第 B 位（即表中的位置）为 1 且第 A 位为 0 的每个条目都应标记为关闭.

于 2013-09-06T22:50:14.823 回答