List all possible combinations of enabled utilities with dependencies?-CodePudding

I have a list of 23 utilities that can be in a state of either enabled or disabled. I've ordered them from 0-22.

Some of these utilities are dependent on others, meaning they cannot be enabled without one or multiple dependency utilities first being enabled. I've put the indices of each utility's dependencies in a list for each utility; for example, if utilities 0-1 had no dependencies, but utility 2 had dependencies on utilities 0 and 9, the full dependency list would look something like: [ [], [], [0, 9], ... ]

What I want to do is devise an algorithm (pseudocode is fine, implementation does not matter) for generating a list of all possible 23-bit bitvectors---each bit in each bitvector with an index that we could label 0-22 corresponding to a single utility, each bitvector itself representing a possible combination of the status of all 23 utilities---that ignores combinations where the dependency requirements provided by the dependency list (described above) would not be satisfied. For example (assume right-to-left numbering):

[
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 ],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1 ],
//skip[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 ] this would not be included (2 enabled, but 0 and/or 9 are not. See prev. example of dependency list)
    ...
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]

CodePudding user response：

First step, get rid of all circular dependencies. If A depends on B depends on C depends on A, all will be on/off together. So we can transfer all dependencies to A, then fill B and C at the last step. This is a question of identifying all connected components in a graph, which we can use Kosaraju's algorithm for to do efficiently.

Second step, do a topological sort by dependencies of the remaining list. This will put the remaining utilities into a list where each only depends on ones you looked at before.

And now we can use recursion down that list. The first utility can be 0 or 1. Each subsequent utility is 0 only if some dependency is not satisfied, else it can be 0 or 1. And then for the ones eliminated due to being part of circular dependencies, fill them in with whatever value the one kept has.