方案中的循环排列

Question

你好，我尝试使用递归在 Scheme (Dr. Racket) 中进行循环排列。

例如，如果我们有 (1 2 3)，循环排列给出 ((1 2 3) (2 3 1) (3 1 2))。

我写了一段代码，但是我在转换时遇到了问题。

我的代码：

(define cpermit
  (lambda (lst)
    (cpermitAux lst (length lst))))

(define cpermitAux
  (lambda (lst n)
    (if (zero? n) '()
        (append (cpermitAux lst (- n 1)) (cons lst '())))))

其中 (cpermit '(1 2 3)) 给出 '((1 2 3) (1 2 3) (1 2 3))

Answer 1

您可以使用移动列表的功能

(defun lshift (l) (append (cdr l) (list (car l))))

这会将您的列表向左移动。

在追加之前使用这个函数

(define cpermit
  (lambda (lst)
    (cpermitAux lst (length lst))))

(define cpermitAux
  (lambda (lst n)
    (if (zero? n) '()
      (append (cpermitAux (lshift lst) (- n 1)) (lshift (cons lst '()))))))

Answer 2

以下代码也有效（没有任何辅助函数）：

(define (cpermit sl)
  (define outl '())
  (for((i (length sl)))
    (set! sl (append (rest sl) (list (first sl))) )
    (set! outl (cons sl outl)))
  outl)

(cpermit '(1 2 3 4))

输出为：

'((1 2 3 4) (4 1 2 3) (3 4 1 2) (2 3 4 1))

Answer 3

这个答案是@rnso 代码的一系列翻译，修改为使用递归辅助函数而不是重复set!。

#lang racket
(define (cpermit sl)
  ;; n starts at (length sl) and goes towards zero
  ;; sl starts at sl
  ;; outl starts at '()
  (define (loop n sl outl)
    (cond [(zero? n) outl]
          [else
           (loop (sub1 n) ; the new n
                 (append (rest sl) (list (first sl))) ; the new sl
                 (cons sl outl))])) ; the new outl
  (loop (length sl) sl '()))

> (cpermit (list 1 2 3 4))
(list (list 4 1 2 3) (list 3 4 1 2) (list 2 3 4 1) (list 1 2 3 4))

对于这种递归助手的 shorthand，您可以使用命名的 let。这会将初始值带到顶部以使其更易于理解。

#lang racket
(define (cpermit sl)
  (let loop ([n (length sl)] ; goes towards zero
             [sl sl]
             [outl '()])
    (cond [(zero? n) outl]
          [else
           (loop (sub1 n) ; the new n
                 (append (rest sl) (list (first sl))) ; the new sl
                 (cons sl outl))]))) ; the new outl

> (cpermit (list 1 2 3 4))
(list (list 4 1 2 3) (list 3 4 1 2) (list 2 3 4 1) (list 1 2 3 4))

@rnso，你可以认为 n、sl 和 outl 实现与 "mutable variables," 相同的目的，但这实际上是相同的代码正如我之前将 loop 定义为递归辅助函数时所写的那样。

上面的模式对于 Scheme/Racket 代码中的累加器非常常见。每次你想要这样的循环时，写出 (cond [(zero? n) ....] [else (loop (sub1 n) ....)]) 有点烦人。因此，您可以将 for/fold 与两个累加器一起使用。

#lang racket
(define (cpermit sl)
  (define-values [_ outl]
    (for/fold ([sl sl] [outl '()])
              ([i (length sl)])
      (values (append (rest sl) (list (first sl))) ; the new sl
              (cons sl outl)))) ; the new outl
  outl)

> (cpermit (list 1 2 3 4))
(list (list 4 1 2 3) (list 3 4 1 2) (list 2 3 4 1) (list 1 2 3 4))

您可能已经注意到外部列表的最后一个 (list 1 2 3 4)，倒数第二个 (list 2 3 4 1)，等等。这是因为我们通过 pre 从后到前构建列表-等待 cons。要解决这个问题，我们可以在最后反转它。

#lang racket
(define (cpermit sl)
  (define-values [_ outl]
    (for/fold ([sl sl] [outl '()])
              ([i (length sl)])
      (values (append (rest sl) (list (first sl))) ; the new sl
              (cons sl outl)))) ; the new outl
  (reverse outl))

> (cpermit (list 1 2 3 4))
(list (list 1 2 3 4) (list 2 3 4 1) (list 3 4 1 2) (list 4 1 2 3))

最后，(append (rest sl) (list (first sl))) 应该是它自己的辅助函数，因为它有一个明确的目的：旋转列表一次。

#lang racket
;; rotate-once : (Listof A) -> (Listof A)
;; rotates a list once around, sending the first element to the back
(define (rotate-once lst)
  (append (rest lst) (list (first lst))))

(define (cpermit sl)
  (define-values [_ outl]
    (for/fold ([sl sl] [outl '()])
              ([i (length sl)])
      (values (rotate-once sl) ; the new sl
              (cons sl outl)))) ; the new outl
  (reverse outl))

> (cpermit (list 1 2 3 4))
(list (list 1 2 3 4) (list 2 3 4 1) (list 3 4 1 2) (list 4 1 2 3))

Answer 4

以下解决方案实用且简短。我发现在很多情况下，辅助函数可以用默认参数代替：

(define (cpermit_1 sl (outl '()) (len (length sl)))
  (cond ((< len 1) outl)
        (else (define sl2 (append (rest sl) (list (first sl))))
              (cpermit_1 sl2 (cons sl2 outl) (sub1 len)))))

输出为：

(cpermit_1 '(1 2 3 4))
'((1 2 3 4) (4 1 2 3) (3 4 1 2) (2 3 4 1))

方案中的循环排列

Circular permutation in scheme

algorithm

recursion

scheme

racket

circular-permutations