CODEWITHSUNDEEP
algorithmlogic
tmoore82
tmoore82

Reputation: 1875

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

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

  1. If element B is dependent on element A, then element B is false as long as A is false.
  2. If element B is dependent on element A and element A is true, then B can be either true or false.
  3. 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.

Upvotes: 0

Views: 347

Answers (1)

Michael S
Michael S

Reputation: 1865

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.

Upvotes: 1

Related Questions