recursion - 方案:给定列表的列表和排列，排列

Question

我正在练习编程范例考试并解决问题集，我遇到了这个问题。这是递归地反转和连接列表后的第一个问题，所以我想有一个优雅的递归解决方案。

我得到了一个列表列表和一个排列。我应该对每个列表进行排列，包括具有指定排列的列表列表。

我举了一个例子:

->(permute '((1 2 3) (a b c) (5 6 7)) '(1 3 2))
->((1 3 2) (5 7 6) (a c b))

我什至不知道如何开始。我需要用递归解释来表述问题才能解决它，但我不知道如何解决。

Answer 1

好吧，让我们看看如何解决这个问题。我们得到一个列表列表和一个数字列表，我们希望根据数字列表指定的顺序对每个列表进行排序:

=>(permute '((1 2 3) (4 5 6)) '(3 2 1))
'((3 2 1) (6 5 4))

我们可以看到列表列表中的每个列表都可以单独处理，它们的解决方案彼此无关。因此，我们可以有一个帮助器 permute1 来处理一个列表的情况，然后使用 map 将此函数应用于每个列表(每次都具有相同的顺序):

(define (permute lists ordering)
  (map (lambda (xs) (permute1 xs ordering))
       lists))

(define (permute1 items ordering)
  ...)

现在，计算 (permute1 '(4 5 6) '(3 2 1))，我们的意思是:

1. 新列表的第一项将是 items 的第 3 项，因为 ordering 中的第一个数字是 3.
2. 新列表中的其余项目将通过使用排序中的其余数字来确定。
3. 如果排序为空列表，则返回空列表。

这形成了基本情况 (3)、递归情况 (1) 以及更深层次递归的步骤 (2)。因此，我们的解决方案的草图如下所示:

(define (permute1 items ordering)
  (if (empty? ordering)
      '()
      (let ([next-item ???])
        (??? next-item
             (permute1 items (rest ordering))))))

其中 ??? 分别表示根据 ordering 中的第一个数字获取项目，并将该项目与计算的其余部分相结合。