use*_*040 1 python boolean subset discrete-mathematics
我有一组变量S,并在S上定义了一个布尔函数f,如下所示:
˚F(X 1,X 2,... X Ñ)= TRUE当且仅当˚F(X 我,X Ĵ)= TRUE∀1≤I≤ Ñ ∀1≤Ĵ≤ Ñ,Ñ > 1,否则为False.
f(a,b)是已知的,f(a,a)是S中的真∀a,b .
我很感激在设计快速算法方面提供了一些帮助,该算法可以返回S的所有子集,其中f返回True.
例如,令S = [a,b,c]和f(a,b)= f(b,c)= f(a,c)= True.然后该算法应返回[[a,b],[a,c],[b,c],[a,b,c]].
我想到了四种改进强力搜索的策略:
1)f的参数顺序无关紧要.
2)使用f(a,a)为真且f(x i,x j)= f(x j,x i)的事实,因此只有i <j需要检查.
2)使用f(x 1,x 2,... x n +1)= f(x 1,x 2,... x n)∧(f(x i,x n +1)∀的事实1≤I≤ ñ)其中∀表示迭代结合.
3)注意2)暗示如果f(x 1,x 2,... x n)返回False,那么f(x 1,x 2,... x n +Δ)也会这样做,可能会减少解空间.
4)对于某些i,j ,f(x i,x j)为假时尽快返回False .
如果你想编写一些代码,如果你能在python中给它,我将不胜感激.
非常感谢.