我有一个n个布尔值的序列。他们中的一些人依赖于其他人。例如，如果n[0]为false，则所有其他项也必须为false。如果n[0]为真，则n[1]可以为真或假。如果N[1]为false，则N[2]必须为false，但所有其他布尔值仍然可以为true或false。
我想要一个程序来显示序列的所有可能的排列，但是我不知道如何在不写出一系列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语句是处理这个问题的正确方法吗？编辑
在回答规则是什么的问题时，这是我问题的一部分。这里的规则是动态的吗？我可以取n个布尔值的任何序列，将其中一些标记为依赖项，或者标记为门，然后给出所有的排列吗？这里有一套可能的规则
如果元素b依赖于元素a，那么只要a为false，元素b就为false。
如果元素B依赖于元素A并且元素A为true，那么B可以为true或false。
依赖项可以是一对一或一对多。如果元素B依赖于元素A，则元素C也可能依赖于元素A。元素C不必依赖于元素B。
考虑这个场景--（A:B，C，D，E，F；F:G，H）（意思是B-E依赖于A，G-H依赖于F。如果A为false，那么一切都是false如果a为真，b-f可以为真或假，然后我们开始下一个级别。如果F为假，G-H为假如果f是真的，那么g-h可以是真的，也可以是假的。
所以我的输出应该是从a-h=false到a-h=true的所有可能值的组合。
最佳答案
暴力方式：
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大小的表，以确定每个置换是否可能。然后你一步一步地通过依赖关系，对于每个标记不可能，它排除的不可能（analagous to aprime sieve）您必须在这里泛化循环，以便修复某些索引并在其余索引上迭代。例如“如果元素A为假，则元素B为假”…表中索引的第B位（即表中的位置）为1且第A位为0的每个条目都应标记为“假”。