有哪些算法可以使用特定函数从数组的一个顺序转到另一个顺序?

Question

我想知道存在哪些算法或方法可以解决以下问题。

有两个数组：

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

并声明一些特定的函数，例如这两个，其中第一个在第 n 个元素中切割数组，就像切割一副牌一样，第二个执行 faro 洗牌(这是一个完美的洗牌(：

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

该算法的目标是找出我们必须使用多少次以及声明哪些函数才能从arr_start到arr_finish识别最短路径。

在这个例子中，我要求的算法会告诉我们做一个法鲁洗牌，然后在第三个元素中切割数组，从arr_start开始arr_finish。

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()