Translating the language used in the question into boolean expressions, we have:
"A depends on B" => "(a and b) or (not a)"
and
"B conflicts with A" => "(b and not a) or (not b)"
Thus, a simple way to write this (in Python 3) is by generating the cartesian product (to give all the possible alternatives) and then selecting only the cases for which the constraints are satisfied. For simplicity, I'm using indices instead of letters for the input, so y[0]
is equivalent to A
, etc. I've translated the output into letters, however.
For n nodes, this approach will generate and test all 2^n possible cases. See below for a more complicated but potentially more efficient approach.
import itertools
bbb = (True,False)
def resolve(n,test):
return [x for x in itertools.product(bbb,repeat=n) if test(x)]
def dependsOn(a,b):
return (a and b) or (not a)
def conflictsWith(b,a):
return (b and not a) or (not b)
letters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
def pr(d):
for dd in d:
s = [letters[i] for i in range(len(dd)) if dd[i] ]
if (len(s) > 0):
print(s,end = " ")
print()
pr(list(resolve(2,lambda y:
dependsOn(y[0],y[1]) and
conflictsWith(y[1],y[0])
)))
pr(list(resolve(2,lambda y:
dependsOn(y[0],y[1]) and
dependsOn(y[1],y[0])
)))
pr(list(resolve(4,lambda y:
dependsOn(y[0],y[1]) and
dependsOn(y[0],y[3]) and
dependsOn(y[1],y[2]) and
conflictsWith(y[3],y[1]) and
conflictsWith(y[3],y[2])
)))
pr(list(resolve(4,lambda y:
conflictsWith(y[0],y[1]) and
conflictsWith(y[1],y[2]) and
conflictsWith(y[2],y[3]) and
conflictsWith(y[3],y[0])
)))
This gives the results:
['B']
['A', 'B']
['B', 'C'] ['C'] ['D']
['A', 'C'] ['A'] ['B', 'D'] ['B'] ['C'] ['D']
... for the four test cases.
For more information, you could look at the Wikipedia entry on truth tables.
(EDIT)
A more efficient approach for problems with many nodes and many constraints would be to build the list of nodes progressively and then only continue building from each partial list if that partial list complies with the constraints, at least to the extent that it has been populated so far. We could do that by replacing the resolve
function above with the following version and by replacing the dependsOn
and conflictsWith
functions to match:
import queue
# The following constraint functions return True if the constraint is met
# or if one or more of the elements relating to the constraint is None
def dependsOn(a,b):
if (a != None) and (b != None):
return (a and b) or (not a)
else:
return True
def conflictsWith(b,a):
if (a != None) and (b != None):
return (b and not a) or (not b)
else:
return True
def resolve(n,test):
result = []
testCount = 0
# initialise the list with all None
lst = [None] * n
q = queue.Queue()
q.put(lst)
while not q.empty():
lst = list(q.get())
testCount += 1
if test(lst):
# the list complies with the constraints, at least
# as far as it is populated
if lst[-1] != None:
# we have a fully-populated list
result.append(lst)
else:
i = lst.index(None)
lst[i] = True
q.put(list(lst))
lst[i] = False
q.put(list(lst))
print ("testCount = %d" % testCount)
return result
This gives the same results for the four test cases. However, for the third and fourth test cases, the value of testCount
is 21 and 23 respectively. That is more than the total number of tests required for the cartesian product solution (which is 16 for n=4) but, for cases where there are many more nodes and many more constraints, this approach avoids testing subsets of nodes that can't possibly contain a solution and therefore could easily require many fewer tests than the cartesian product solution. Of course, in the worst-case scenario with few or no constraints, this approach can require a maximum of 2^(n+1) - 1 tests. That does, in fact, happen for the first two test cases, for which testCount
is 7 using this algorithm.
Note that the implementation shown here is crude and could certainly be optimised for speed.