algorithm - 汉诺塔与K钉

Towers of Hanoi问题是递归的经典问题。给你3个钉，其中一个钉上有磁盘，你必须按照给定的规则将所有磁盘从一个钉移动到另一个钉上您还必须以最少的移动次数来完成此操作。
下面是一个递归算法来解决这个问题：

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

现在，假设同样的问题，只有4个peg，所以我们添加另一个中介peg。当面对在任何一点上必须选择哪一个中间钉的问题时，我们将选择最左边的一个，以防超过1是自由的。
对于这个问题，我有以下递归算法：

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

现在，我的问题是如何将这种递归方法推广到Kpegs上？递归函数将接收一个char[]来保存每个堆栈的标签，因此该函数将如下所示：

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

我知道frame stewart算法，它很可能是最优的，但还没有被证明，它给了你移动的次数。然而，我对一个严格的递归解感兴趣，它遵循3和4钉的递归解的模式，这意味着它打印实际的移动。
至少对我来说，维基百科上的frame-stewart算法的伪代码是相当抽象的，我还没有成功地将其转换成打印移动的代码。我会接受它的一个引用实现（对于randomk），或者更详细的伪代码。
我试着想出一种算法来相应地排列标签数组，但是我没能成功如有任何建议，我们将不胜感激。
更新：
这在函数式语言中似乎更容易解决。
下面是一个基于larsh的haskell解决方案的f实现：

let rec HanoiK n pegs =
    if n > 0 then
        match pegs with
        | p1::p2::rest when rest.IsEmpty
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)
        | p1::p2::p3::rest when not rest.IsEmpty
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

如果不把3个钉子当作边缘病例：

let rec HanoiK n pegs =
    if n > 0 then
        match pegs with
        | p1::p2::rest when rest.IsEmpty
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

注意，这不处理没有解决方案的退化情况，例如HanoiK 2 [1; 2]

最佳答案

下面是haskell中的一个实现（更新：当r=3时，通过使k=n-1来处理3-peg情况）：

-- hanoi for n disks and r pegs [p1, p2, ..., pr]
hanoiR :: Int -> [a] -> [(a, a)]

-- zero disks: no moves needed.
hanoiR 0 _ = []

-- one disk: one move and two pegs needed.
hanoiR 1 (p1 : p2 : rest) = [(p1, p2)] -- only needed for smart-alecks?

{-
-- n disks and 3 pegs -- unneeded; covered by (null rest) below.
hanoiR n [p1, p2, p3] =
    hanoiR (n - 1) [p1, p3, p2] ++
    [(p1, p2)] ++
    hanoiR (n - 1) [p3, p2, p1]
-}

-- n disks and r > 3 pegs: use Frame-Stewart algorithm
hanoiR n (p1 : p2 : p3 : rest) =
    hanoiR k (p1 : p3 : p2 : rest) ++
    hanoiR (n - k) (p1 : p2 : rest) ++
    hanoiR k (p3 : p2 : p1 : rest)
    where k
        | null rest   = n - 1
        | otherwise   = n `quot` 2

在GHCi中加载并输入

hanoiR 4 [1, 2, 3, 4]

也就是说，用4个圆盘和4个钉子来管理河内的塔。你可以随便给这4个钉子起个名字。

hanoiR 4 ['a', 'b', 'c', 'd']

输出：

[(1,2),(1,3),(2,3),(1,4),(1,2),(4,2),(3,1),(3,2),(1,2)]

即，将顶盘从peg 1移动到peg 2，然后将顶盘从peg 1移动到peg 3，等等。
我对哈斯克尔还不太熟悉，所以我必须承认我很自豪这样做。但我可能有愚蠢的错误，所以欢迎反馈。
从代码中可以看出，k的启发式方法只是floor（n/2）。我没有试着优化k，尽管n/2看起来是个不错的猜测。
我已经验证了4个磁盘和4个钉的答案的正确性。如果不写一个模拟器的话，我要验证更多的东西已经太晚了。（@@这里还有几个结果：

ghci>  hanoiR 6 [1, 2, 3, 4, 5]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,4),(1,5),(1,2),
 (5,2),(4,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci>  hanoiR 6 [1, 2, 3, 4]
[(1,2),(1,4),(1,3),(4,3),(2,3),(1,2),(1,4),(2,4),(1,2),
 (4,1),(4,2),(1,2),(3,1),(3,4),(3,2),(4,2),(1,2)]
ghci>  hanoiR 8 [1, 2, 3, 4, 5]
[(1,3),(1,2),(3,2),(1,4),(1,3),(4,3),(2,1),(2,3),(1,3),(1,2),
 (1,4),(2,4),(1,5),(1,2),(5,2),(4,1),(4,2),(1,2),
 (3,2),(3,1),(2,1),(3,4),(3,2),(4,2),(1,3),(1,2),(3,2)]

这说明了算法吗？
最重要的是

hanoiR k (p1 : (p3 : (p2 : rest))) ++      -- step 1; corresponds to T(k,r)
hanoiR (n-k) (p1 : (p2 : rest)) ++         -- step 2; corresponds to T(n-k, r-1)
hanoiR k (p3 : (p2 : (p1 : rest)))         -- step 3; corresponds to T(k,r)

其中，我们将帧Stewart算法的步骤1、2和3的移动序列串联起来。为了确定移动，我们将f-s的步骤注释如下：
传统上，当调用hanoi时，目标被定义为（在不丧失通用性的情况下）将磁盘从第一个peg转移到第二个peg，使用所有剩余的peg进行临时存储。我们在递归时使用此约定来定义已分割和已征服的子问题的源、目标和允许的存储。
因此，源peg是p1，而目的peg是p2。所有剩余的木桩都可以作为临时仓库，以解决河内的顶级问题。
步骤1，“对于某些k，1因此，“不干扰现在包含顶部k个磁盘的peg”（步骤2）意味着使用除p3之外的所有peg递归即p1、p2和p3以外的其他部分。
“将顶部k个磁盘转移到目标peg”（步骤3）意味着从“其他peg”（p3）转移到p2。
这有道理吗？

关于algorithm - 汉诺塔与K钉，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32554838/