Вычисление "закрытия" атрибутов объекта заданными функциями, которые изменяют атрибуты

У меня есть объект 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 композиций функций).

Вывод должен быть списком всех возможных выходов вместе со всеми ведущими там путями. Поэтому, если, скажем, 104 и 93 являются единственными возможными конечными выходами, если obj.attr=22, и есть два способа добраться до 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

Как я мог реализовать это? Как было предложено в комментариях, это лучше всего делать с деревьями, но, хотя я пробовал 2 дня, я почти не добился прогресса в реализации этого (я новичок в Python/programming)!
Мой пример настолько прост, что вместо func(obj) мы могли бы напрямую использовать func(22), но пример, который мне нужен для работы, более сложный, где определенно нужно будет использовать объекты, поэтому это будет лишь минимальным рабочим примером для этого.

Дерево, вероятно, не будет полным n-арным деревом, так как каждое приложение-функция будет содержать тест, может ли он применяться к текущему состоянию (атрибутов) obj, а в некоторых случаях тест не удастся оставляя (атрибуты) obj неизменными.

Ответы

Ответ 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 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.

Ответ 2

Звучит забавно, пусть он разбивается на шаги.

  • Выясните возможные комбинации функций.

  • Оценить возможные комбинации функций.

Вычисление возможных комбинаций

Один из способов сделать это - использовать генераторы. Они эффективны с точки зрения памяти, поэтому вы не создаете кучу значений и максимизируете кучу.

Итак, как мы получаем все комбинации. Быстрый поиск документов Python предполагает использование itertools. Так что сделайте это.

from itertools import combinations

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

До сих пор у нас есть генератор, который может дать нам все комбинации (без замены) списка функций. Каждая предоставленная комбинация представляет собой список функций n large. Мы можем просто вызвать каждый по очереди, и мы можем получить сложенный результат.

Этот уровень в дереве. Как мы получим следующий уровень. Ну, мы могли бы получить все комбинации размера 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

Итак, это вторая часть. Теперь все, что вам нужно сделать, это цепочка em.

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

Теперь просто возьмите столько результатов, сколько вам нужно.

Даунсайд

То же, что и для любого метода, который не клонирует obj. Он собирается мутировать объект. Более того, у нас есть накладные расходы генераторов (которые могут быть немного медленнее, чем for-loops). У нас также есть хитрость для удобочитаемости (особенно, если кто-то не знаком с генераторами).

Отказ от ответственности: я набираю это по телефону. Возможны незначительные опечатки и т.д.