时间戳

首页 > 解决方案 > 存在哪些算法可以使用特定函数从数组的一个顺序转到另一个顺序？

algorithm - 存在哪些算法可以使用特定函数从数组的一个顺序转到另一个顺序？

问题描述

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

有两个数组：

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

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

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 的最短路径，我们必须使用声明的函数的次数以及声明的哪些函数。

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

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

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

未来的目标是使用更长的数组，并声明更多的函数。

标签： algorithmsortingheuristics

解决方案

可能最简单的算法（也是我能想到的唯一一个）是产生函数的n倍笛卡尔积s 随着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()

推荐阅读