CODEWITHSUNDEEP
schemeracket
Glen Marek
Glen Marek

Reputation: 75

Scheme: All Possible Shifts from Front of List to Back

I need to write a Scheme function that takes a list as an argument and returns a list of lists where every list is a cycle of the original list. By a cycle, I mean shifting the first element to the last position. I have the following functions:

(define (cycle lst)
  (cond ((null? lst) '())
        ((null? (cdr lst)) lst)
        (else (append (cdr lst) (list (car lst)))))) 

(define (shift lst)
  (define (iter l cycles result)
    (cond ((= cycles 0) (cons lst result))
          ((< cycles 1) result)
          (else (iter (cycle-1 l) (- cycles 1) (cons result (cycle-1 l))))))
  (iter lst (- (length lst) 1) '()))

Now, when I do: (shift '(1 2 3)) I get: '((1 2 3) (() 2 3 1) 3 1 2) I should get: '((1 2 3) (2 3 1) (3 1 2))

Upvotes: 2

Views: 550

Answers (1)

osa1
osa1

Reputation: 7078

(define (shift lst)
  (define (iter l cycles result)
    (cond ((= cycles 0)
           (cons lst result))
          ((< cycles 0) result)
          (else (let ((cycled (cycle l)))
                  (iter cycled (- cycles 1) (cons cycled result))))))
  (iter lst (- (length lst) 1) '()))

First, I've made a simple improvement to prevent calculate cycled form of the list twice(added let). Second, you need to cons cycled to result since you need to append result list, not cycled list. In your code, you're adding last result to old results and then passing this wrongly appended results list to iter functions as result parameter.

Update: To get the results in your order you can simple just append result with cycled list, instead of adding cycled list to head of the result:

(define (shift lst)
  (define (iter l cycles result)
    (cond ((= cycles 0)
           (cons lst result))
          ((< cycles 0) result)
          (else (let ((cycled (cycle l)))
                  (iter cycled (- cycles 1) (append result (list cycled)))))))
  (iter lst (- (length lst) 1) '()))

Upvotes: 1

Related Questions