Какие алгоритмы существуют для go из одного порядка массива в другой, используя определенные c функции?

Question

Мне было интересно, какие алгоритмы или подходы существуют для решения следующей проблемы:

Имея два массива:

arr_start = [1,2,3,4,5,6]
arr_finish = [5,3,6,1,4,2]

И объявляя некоторые специфические c функции, такие как эта два, где первый разрезает массив в n-м элементе, как будто разрезает колоду карт, а второй выполняет перетасовку Фаро (что является идеальным перетасованием):

def cut_arr(n,arr):
r=[1]*len(arr)
for i in range(len(arr)):
    if (i+n)<len(arr):
        r[i] = arr[i+n]
    else:
        r[i] = arr[i+n-len(arr)]
return r


def faro_shuffle(arr):
r = []

for (a, b) in zip(arr[0:3], arr[3:]):
    r.append(a)
    r.append(b)
arr = r
return r

Цель алгоритм должен был бы найти, сколько раз и какую из объявленных функций мы должны использовать для go от arr_start до arr_fini sh, определяющего кратчайший путь.

В этом примере алгоритм, который я задаю for сказал бы нам сделать faro shuffle и затем вырезать массив в третьем элементе, получив arr_fini sh начиная с arr_start.

arr1 = faro_shuffle(arr_start)
cut_arr(3,arr1)

Output: [5,3,6,1,4,2]

Цель в будущем будет работать с более длинными массивами, и объявить больше функций.

Answer 1

Вероятно, самый простой алгоритм (и единственный, который я могу придумать) - это произвести n -кратное декартово произведение с функций с увеличением n и применяя полученные наборы функций по очереди. Аргументы функции могут быть обработаны путем репликации ее для каждого возможного значения. Этот пример программы (которую можно расширить с помощью дополнительных функций) находит решение данной проблемы:

arr_start = [1,2,3,4,5,6]
arr_finish = [5,3,6,1,4,2]

def cut_arr(n,arr):
    r=[1]*len(arr)
    for i in range(len(arr)):
        if (i+n)<len(arr):
            r[i] = arr[i+n]
        else:
            r[i] = arr[i+n-len(arr)]
    return r

def faro_shuffle(arr):
    r = []
    for (a, b) in zip(arr[0:3], arr[3:]):
        r.append(a)
        r.append(b)
    arr = r
    return r

# make a list with the available functions
## for a function with an argument n, replicate it for all possible n
## for a function without an extra n, specify argument None
functions = [(cut_arr, i) for i in range(len(arr_start))] \
          + [(faro_shuffle, None)]

import itertools

for r in itertools.count(0):
    for c in itertools.product(functions, repeat=r):
        print("TRYING", c)
        arr = arr_start
        for f in c:
            func, argn = f
            arr = func(arr) if argn is None else func(argn, arr)
        if arr == arr_finish:
            print("SUCCESS")
            quit()