計画中の円順列

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)))) 

これはリストを左にシフトします。次のコードappendings

(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のコードの翻訳で、0123の代わりに再帰ヘルパー関数を使うように修正されました。再帰的ヘルパーのこの種の略記については

#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)) 

、あなたはletという名前を使用することができます。これは、最初の値を上に持ち上げて理解しやすくします。 @rnsoする

#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)) 

、あなたは「可変変数」と同じ目的を果たすようn、sl、およびoutlと考えることができますが、これは本当に私は私のようにloopを定義したとき前に書いたのと同じコードです再帰ヘルパー関数。

上記のパターンは、Scheme/Racketコードのアキュムレータで非常に一般的です。 (cond [(zero? n) ....] [else (loop (sub1 n) ....)])は、このようなループが必要なたびに書き出すのに少し面倒です。その代わりに、for/foldに2つのアキュムレータを使用することができます。

#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)最後から2番目のなど、私たちは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))