[eric.mercer]

Hi, I am trying to write a Scheme function that takes a list and returns a list of lists. Each list in the outer list will be the the list before it, except with the front shifted to the back.
So (shift '(1 2 3)) would give
'((1 2 3) (2 3 1) (3 1 2))
and (shift '(1 1 1)) would get
'((1 1 1) (1 1 1) (1 1 1))

I wrote a function that shifts the list once, but I am not sure how to apply it so that it shows all possible shifts.

(define (shift-once lst)
  (cond ((null? lst) '())
        ((null? (cdr lst)) lst)
        (else (append (cdr lst) (list (car lst))))))

Thanks in advance!

[sepp2k]

You could write a function that takes a list and a number (to count how many shifts are left) and then calls itself recursively with the shifted list and the decremented integer as arguments, prepending the original list to the result of the recursive call. The base case (returning an empty list) would be for n=0.

[eric.mercer]

sepp2k, on 14 February 2012 - 07:51 PM, said:

You could write a function that takes a list and a number (to count how many shifts are left) and then calls itself recursively with the shifted list and the decremented integer as arguments, prepending the original list to the result of the recursive call. The base case (returning an empty list) would be for n=0.

Thank you for your reply. I am still not quite sure how to do it. I wrote something like

(define (shifts 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) '(())))

which doesn't quite work. What am I doing wrong? Thanks.

[sepp2k]

It would help if you described how exactly it doesn't quite work.

One thing I notice from glancing at the code is that you're using an accumulator, which will build the list the wrong way around (basically whenever you rewrite a list-building function to be tail-recursive the results will end up reversed). So you'll either need to put a call to reverse in the base case or rewrite shift-1 to shift in the other direction.

Also your case for (< cycles 0) will never be entered because the case for (= cycles 0) will fire first.

I also don't understand why you pass a list containing an empty list (as opposed to just an empty list) as the initial value for result.

This post has been edited by sepp2k: 14 February 2012 - 11:44 PM

[eric.mercer]

The passing it an empty list in a list instead of just an empty list is to take care of the case:
(shifts '()) -> '(())
same thing as the (< cycles 0) clause as it makes sure the code doesn't crash if the initial list is empty

By it doesn't work, I mean something like this:
(shifts '(1 2 3)) -> '((1 2 3) (() 2 3 1) 3 1 2)
instead of '((1 2 3) (2 3 1) (3 1 2))
It actually appears to have the right order, but it seems that something about the way I use cons is off.

Thanks,