from heapq import heappush, heappop
def cost(s, lists):
prod = 1
for ith, x in zip(s, lists):
prod *= x[ith]
return prod
def successor(s, lists):
successors = []
for k, (i, x) in enumerate(zip(s, lists)):
if i < len(x) - 1:
t = list(s)
t[k] += 1
successors.append(tuple(t))
return successors
def sorted_product(initial_state, lists):
fringe = []
explored = set()
heappush(fringe, (-cost(initial_state, lists), initial_state))
while fringe:
best = heappop(fringe)[1]
yield best
for s in successor(best, lists):
if s not in explored:
heappush(fringe, (-cost(s, lists), s))
explored.add(s)
if __name__ == '__main__':
lists = ((0.7, 0.2, 0.1),
(0.6, 0.3, 0.1),
(0.5, 0.25, 0.25),
(0.4, 0.35, 0.25),
(0.35, 0.35, 0.3))
init_state = tuple([0]*len(lists))
for s in sorted_product(init_state, lists):
s_output = [x[i] for i, x in zip(s, lists)]
v = cost(s, lists)
print '%s %s \t%s' % (s, s_output, cost(s, lists))
所以，如果你有A（A1，...，An）和B（B1，...，Bn）。
当且仅当
A1 * ... * An < B1 * ... * Bn时，A < B
我假设每个值都是正数，因为如果我们允许负数，那么：
(-50，-100，1)>（1，2，3）
因为-50 *（-100）* 1 = 5000> 6 = 1 * 2 * 3
即使没有负值，问题仍然相当复杂。您需要一个解决方案，其中包括一个深度为k的数据结构。如果（A1，...，Ak）<（B1，...，Bk），则我们可以假设在其他维度上，（A1，...，Ak，...，An）的组合可能小于（B1，...，Bk，...，Bn）的组合。因此，无论何时这不成立，情况都会打破概率，因此这些将是规则的例外情况。数据结构应包含：
class Rule {
int k;
int[] smallerCombinationIndexes;
int[] biggerCombinationIndexes;
List<Rule> exceptions;
}
每当你发现一个规则的例外时，这个例外都是基于先前的知识产生的。显然，复杂性大大增加了，问题在于你有规则的例外，还有例外的例外等等。当前的方法会告诉你，如果你取两个随机点 A 和 B，A 是否小于 B，它还会告诉你，如果你取 (A1, ..., Ak) 和 (B1, ..., Bk) 的组合，那么在哪些关键索引处 (A1, ..., Ak) 和 (B1, ..., Bk) 的比较结果会改变。根据你确切的需求，这个想法可能已经足够，或者需要扩展。所以你的问题的答案是：是的，你可以扩展懒惰算法来处理更多的维度，但你需要处理规则的例外才能实现这一点。