给定改变对象属性的函数，计算对象属性的“闭包”

Question

我有一个对象obj和一些函数

    def func1(obj):
    #...

    def func2(obj):
    #...

    def func3(obj):
    #...

每个都会更改obj属性的值。

我希望我的输入类似于

obj = MyObject()
obj.attr=22

这应该传递给一个名为closure()的函数，用于计算上述函数的所有可能应用，例如func1(func2(obj))，func3(func1(func1(obj)))等，直到某个停止条件（例如不超过20个函数组合）。

输出应该是所有可能的输出列表以及通往那里的所有路径。 因此，如果说假设obj.attr=22，104和93是一种可能的最终输出，并且有两种方法可以到达104，而到达93则有一种方法。 那么

print closure(obj)

应该是这样的。

[22, 64, 21, 104] #first path to 104 through , func1(obj),func1(func1(obj)), func1(func1(func3(obj)))

[22, 73, 104] #second path to 104 through , func3(obj),func3(func2(obj)), 

[22, 11, 93] #the only path to arrive at 94

我该如何实现这个功能？如评论中建议的那样，最好使用树来实现，但是虽然我尝试了两天，几乎没有任何进展（我是 Python/编程新手）！

我的示例非常简单，我们可以直接使用 func(22) 而不是 func(obj)，但我需要处理的示例更加复杂，我一定需要使用对象，所以这只是一个最小的工作示例。

由于每个函数应用都将包含一个测试，以判断它是否可以应用于当前状态（属性）的 obj，因此该树可能不是完全的 n 叉树。在某些情况下，测试将失败，使得 obj 的属性未改变。

- user47574

---

看起来你想要一个树形结构，其中每个节点是一个状态，并且通过函数进行分支（每个函数接受一个状态并创建一个新的节点/状态）。这在人工智能和其他领域中非常常见，并且在这里可能很有用。要追踪发生了什么，只需在达到所需状态后向根节点遍历即可。哦，如果可能的话，请使用广度优先搜索（BFS）算法。 - Reut Sharabani

如果您使用深度优先搜索（DFS）并且具有无限的函数应用路径...即使存在“解决方案”，您也永远不会找到任何有意义的东西。但是，如果存在解决方案，则DFS保证找到它（但您需要付出内存代价，而不像DFS那样是恒定内存）。您还可以使用迭代式DFS（谷歌一下）来确保它停止。 - Reut Sharabani

DFS 保证 = BFS 保证 * :) - Reut Sharabani

最终输出应该是什么？所有可能的输出列表？通往所需输出的路径？这条路径是否需要包含最少数量的函数？ - c2huc2hu

@user3080953 请查看我的编辑。 - user47574

Answer 1

这是一个简单的示例，旨在找到一个数字（goal）是否为另一个数字（inital_state）的前任，当应用Collatz猜想中的规则时。

在您的示例中，obj是state，而[func1，func2，...]是我的示例中的functions。 此版本将返回通向最终输出的路径，并最小化函数应用数量。 您可以通过删除目标测试并在循环结束后返回prev_states来列出所有状态。

from collections import deque

def multiply_by_two(x):
    return x * 2

def sub_one_div_three(x):
    if (x - 1) % 3 == 0:
        return (x - 1) // 3
    else:
        return None # invalid


functions = [multiply_by_two, sub_one_div_three]

# find the path to a given function
def bfs(initial_state, goal):
    initial_path = []
    states = deque([(initial_state, initial_path)])     # deque of 2-tuples: (state, list of functions to get there)
    prev_states = {initial_state}                       # keep track of previously visited states to avoid infinite loop

    while states:
        # print(list(map(lambda x: x[0], states)))      # print the states, not the paths. useful to see what's going on
        state, path = states.popleft()

        for func in functions:
            new_state = func(state)

            if new_state == goal:                       # goal test: if we found the state, we're done
                return new_state, path + [func]

            if (new_state is not None and           # check that state is valid
                new_state not in prev_states):      # and that state hasn't been visited already
                states.append((new_state, path + [func]))
            prev_states.add(new_state)              # make sure state won't be added again
    else:
        raise Exception("Could not get to state")

print(functions)
print(bfs(1, 5))

# prints (5, [<function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function multiply_by_two at 0x000002E746727F28>, <function sub_one_div_three at 0x000002E7493C9400>]). You can extract the path from here.

- c2huc2hu

---

我目前正在努力理解代码（请容忍我，因为我是初学者），以便我可以根据自己的需求进行调整。看起来你的bfs函数不仅计算给定图的bfs，而且直接创建了图，对吗？这是标准的设计选择吗？还是有可能先单独创建一个树类/对象，其中每个节点都是形式为func3(func1(func(2(...))))的列表，然后使用bfs遍历它？至少在概念上，这就是我会做的方式。 - user47574

你说得对，我没有显式地计算图/树。如果你需要在图上执行更多的操作，缓存它是有意义的，但如果这是你唯一需要的操作，那么没有必要显式构建它。 - c2huc2hu

我看到了您有关使用对象而不是int的编辑。要解决这个问题，您需要使状态可哈希（实现“__hash__”），并使“func（state）”返回一个对象，而不是修改“state”。 - c2huc2hu

Answer 2

听起来很有趣，让我们分步骤来解决。

1. 找出可能的函数组合。

2. 评估可能的函数组合。

找出可能的组合

一种方法是使用生成器。它们在内存方面效率高，因此您不会创建大量值并使堆达到最大值。

那么如何获得所有组合。 Python文档的快速搜索建议使用itertools。所以让我们这样做。

from itertools import combinations

def comb(fns, n):
     return combinations(fns, n)

到目前为止，我们有一个可以为我们提供由函数列表组成的所有组合（不重复）的生成器。每个组合将是一个包含n个函数的函数列表。我们可以按顺序调用它们并获得组合结果。这是树中的一个级别。我们如何获取下一级呢？我们可以获取所有大小为1的组合，然后获取所有大小为2的组合，以此类推。由于生成器是惰性的，我们应该能够在不使解释器崩溃的情况下完成这个任务。

def combo_tot(fns):
    start=1
    while (start <= len(fns)):
        for c in comb(fns, start):
            yield c
        start += 1

评估可能的组合

现在我们有了所有有意义的可能组合。让我们使用它来评估东西。

def evalf(fns_to_compose, initval):
    v = initval
    for fn in fns_to_compose:
        v = fn(v)
    return v

这就是第二部分。现在你需要将它们链接起来。

def results(fns, init):
    return (evalf(fn, init) for fn in combo_tot(fns))

现在只需要获取所需结果即可。 缺点 与不克隆obj的任何方法相同，它将改变对象。此外，我们还有生成器的开销（可能比for循环略慢）。我们还会对可读性造成影响（特别是对于不熟悉生成器的人）。

免责声明：我正在手机上输入此内容。可能存在一些小错误等。

- Abhinav Ramakrishnan