Logic of Dependencies: Is if/then the only/best way?

Question

I have a sequence of N boolean values. Some of them are dependent on others. For example, if N[0] is false, all the others must also be false. If N[0] is true, then N[1] can be true or false. If N[1] is false, N[2] must be false, but all other booleans can still be true or false.

I want a program to show me all possible permutations of the sequence, but I have no idea how to do that without writing out a series of if/then statements. Someone suggested that I could use enums, but based on my understanding of how enums work, I'd still end up with a long series of if/then statements, and it would only apply to this single problem. I've been thinking about this for a few days, trying to figure out how I would structure something more dynamic. The pseudo code would look something like this:

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;
     ...
}

It could have a loop:

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

Hopefully the question is clear at this point. Besides if/then are there other ways of setting a gatekeeper? Or are nested/cascading if/then statements the right way to handle this?

EDIT

In response to the question of what the rules are, that's part of my question. Can the rules here be dynamic? Can I take any sequence of N boolean values, flag some of them as dependencies, or as gates maybe, and then come up with all the permutations? Here's a possible set of rules

If element B is dependent on element A, then element B is false as long as A is false.
If element B is dependent on element A and element A is true, then B can be either true or false.
Dependencies can be one-to-one or one-to-many. If element B is dependent on element A, element C may also be dependent on element A. Element C does not have to be dependent on element B.

Consider this scenario -- (A: B, C, D, E, F; F: G, H) (meaning that B-E are dependent on A, and G-H are dependent on F. If A is false, everything is false. If A is true, B-F can be true or false, and then we start the next level. If F is false, G-H are false. If F is true, then G-H can be either true or false.

So my output should be every possible combination of values from A-H=false to A-H=true.

It's really hard to come up with an answer if you don't tell us what all the "rules" are — Sam I am says Reinstate Monica, Sep 06 '13 at 19:50
I agree with @SamIam, I have no way of knowing what the logic is that determines if a certain value is true or false if you don't define the rules. — Paccc, Sep 06 '13 at 19:51
Have you read about Moore and Mealy state machines? Some background reading about how they operate may help you approach the problem. This kind of state machine logic is I think what you're trying to define with your if / else logic. Wish I could tell you more about them, but my electronics degree is too long ago! This answer may help though: http://stackoverflow.com/questions/133214/is-there-a-typical-state-machine-implementation-pattern — Kris C, Sep 06 '13 at 20:39
And this one: http://stackoverflow.com/questions/1647631/c-state-machine-design?lq=1 — Kris C, Sep 06 '13 at 20:45
This has nothing to do with permutations or combinations. If I understand correctly, you're looking for either a way to generate the truth table of a propositional formula, or only the true rows of it. — Fred Foo, Sep 06 '13 at 20:45
Based on the description of "I want a program to show me all possible permutations of the sequence," and each input from the sequence along with some internal rule seeming to affect the next output value ("A Mealy machine is a finite-state machine whose output values are determined both by its current state and the current inputs"). I may have mis-interpreted the question based on the description though — Kris C, Sep 06 '13 at 21:17
Do you want something that, given a set of rules, provides you with all of the possible valid combinations? Or do you want something that, given a set of rules and a combination of values, will tell you if those values are valid based on the rules? — Jim Mischel, Sep 06 '13 at 21:59
@JimMischel, I want the former. I want all possible valid combinations based on dependencies. The question might not be clear enough. I will work on refining it. — tmoore82, Sep 06 '13 at 22:21

score 1 · Accepted Answer · answered Sep 06 '13 at 22:50

Brute force way:

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++;
        }
    }
}

As you can see, you only need to write the the if/else testing once for each kind of dependency. This is what loops and other control statements are for!

A more efficient algorithm (or perhaps Not, now that I think on it) would store a table of size 2^N for whether each permutation is possible. Then you step through the dependencies one by one, and for each mark impossible the eventualities that it excludes. (Analagous to a prime sieve) You would have to generalize the loop here in order to fix certain indices and iterate over the rest. For example "element B is false if element A is false"...every entry in the table where the B'th bit of the index (i.e. position in table) is 1 and the A'th bit is 0 should be marked off.

Logic of Dependencies: Is if/then the only/best way?

1 Answers1