algorithm - 依赖逻辑 : Is if/then the only/best way?

Question

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

我想要一个程序来显示序列的所有可能排列，但如果不写出一系列 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 个 bool 值的任意序列，将其中一些标记为依赖项，或者标记为门，然后得出所有排列？这是一组可能的规则

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)(意思是 B-E 依赖于 A，G-H 依赖于 F。如果 A 为假，则一切都是假。如果 A 为真，B-F 可以为真或假，然后我们开始下一个级别。如果 F 为假，G-H 为假。如果 F 为真，则 G-H 可以为真或假。

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

Answer 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 的表来确定每个排列是否可能。然后，您逐一检查依赖关系，并针对每个标记为不可能的情况排除它所排除的可能性。 (类似于 prime sieve )您必须在此处概括循环以修复某些索引并迭代其余索引。例如“如果元素 A 为假，则元素 B 为假”...表中索引的第 B 位(即表中的位置)为 1 且第 A 位为 0 的每个条目都应标记为关闭.