置乱函数是如何工作的？(经验丰富的阴谋家第一章)

Question

根据这本书，这就是函数的定义，

函数扰码采用非空元组，其中没有任何参数大于其自己的索引，并返回长度相同的元组。参数中的每个数字都被视为从其自身位置到元组前面某个点的反向索引。根据该索引，从当前位置向后计数每个位置的结果。

这些是一些例子，

; Examples of scramble
(scramble '(1 1 1 3 4 2 1 1 9 2))       ; '(1 1 1 1 1 4 1 1 1 9)
(scramble '(1 2 3 4 5 6 7 8 9))         ; '(1 1 1 1 1 1 1 1 1)
(scramble '(1 2 3 1 2 3 4 1 8 2 10))    ; '(1 1 1 1 1 1 1 1 2 8 2)

这是实现，

(define pick
  (λ (i lat)
    (cond
      ((eq? i 1) (car lat))
      (else (pick (sub1 i)
                  (cdr lat))))))

(define scramble-b
  (lambda (tup rev-pre)
    (cond
      ((null? tup) '())
      (else
       (cons (pick (car tup) (cons (car tup) rev-pre))
             (scramble-b (cdr tup)
                         (cons (car tup) rev-pre)))))))

(define scramble
  (lambda (tup)
    (scramble-b tup '())))

Answer 1

在这种情况下，使用极小版本的语言意味着代码足够冗长，因此理解算法可能并不容易。

处理这个问题的一种方法是用一种更丰富的语言编写程序，然后计算出算法是如何在最小版本中实现的，这一点现在很明显了。让我们选择球拍作为丰富的语言。

Racket有一个名为list-ref：(list-ref l i)的函数(和Scheme一样)，它返回基于零的l的i第四元素。

它还有一个很好的“序列”概念，它基本上是“你可以迭代的东西”，还有一堆以for开头的结构，用于迭代序列。有两个函数使我们关心的序列：

• in-naturals生成一个无限自然数序列，默认情况下，自然数从0开始，而(in-naturals n)从n开始。
• in-list从一个列表中生成一个序列(列表实际上已经是一个序列，但是in-list使事情变得更清楚了，而且还有传言说得更快)。

我们关心的迭代构造是for/list，它对某些序列进行迭代，并将结果从其体内收集到一个列表中。

在这些情况下，算法几乎是微不足道的:我们希望沿着列表进行迭代，跟踪当前的索引，然后执行适当的减法，在列表的后面选择一个值。唯一重要的一点是处理基于零对一的索引。

(define (scramble l)
  (for/list ([index (in-naturals)]
             [element (in-list l)])
    (list-ref l (+ (- index element) 1))))

事实上，如果我们让in-naturals从1中计数，我们就可以避免尴尬的添加-1：

(define (scramble l)
  (for/list ([index (in-naturals 1)]
             (element (in-list l)))
    (list-ref l (- index element))))

现在看一下这段代码，即使你不知道Racket，算法也是非常清晰的，您可以检查它给出了书中的答案：

> (scramble '(1 1 1 3 4 2 1 1 9 2))
'(1 1 1 1 1 4 1 1 1 9)

现在还需要弄清楚书中的代码是如何实现相同算法的。这是很微妙的，但一旦你知道算法是什么，它应该是简单明了的。

Answer 2

如果语言描述看上去模糊不清，很难理解，我们可以试着遵循代码本身，将其转化为更直观的伪代码：

pick i [x, ...ys] = 
  case i { 
     1 --> x ;
     pick (i-1) ys }
==>
  pick i xs = nth1 i xs
     (* 1 <= i <= |xs| *)

scramble xs = 
   scramble2 xs []

scramble2 xs revPre =
 case xs {
   [] --> [] ;
   [x, ...ys] -->
     [ pick x [x, ...revPre],
       ...scramble2 ys
              [x, ...revPre]] }

因此，

scramble [x,y,z,w, ...] 
 =
  [ nth1 x [x]       (*x=1..1*)
  , nth1 y [y,x]     (*y=1..2*)
  , nth1 z [z,y,x]   (*z=1..3*)
  , nth1 w [w,z,y,x] (*w=1..4*)
  , ... ]

因此，输入列表中的每个元素被用作该列表反向前缀的索引，直至并包含该元素。换句话说，在向后计数时，将索引放入前缀，即从元素到左边，即指向列表的开始。

因此，我们现在已经可视化了代码正在做什么，并且还发现了它的输入列表元素的需求。