Rotate a list. (Creates and returns a new list.)
proc lrotate {xs {n 1}} {
if {!$n} {return $xs}
if {$n<0} {return [lrotate $xs [expr {[llength $xs]+$n}]]}
foreach x [lassign $xs y] {
lappend ys $x
}
lappend ys $y
lrotate $ys [incr n -1]
}By default, rotates a list left by one element (moving the head to the tail).
Examples:
% lrotate {1 2 3 4 5}
2 3 4 5 1
% lrotate {1 2 3 4 5} -1
5 1 2 3 4
% lrotate {1 2 3 4 5} 2
3 4 5 1 2
% lrotate {1 2 3 4 5} 0
1 2 3 4 5I'm sure someone can come up with a better implementation...
AM I could not resist this challenge :). Here is mine (note that allows any number for the shift):
proc lrotate2 {xs {n 1}} {
set length [llength $xs]
if {$n == 0 || $length == 0 } {return $xs}
set n [expr {$n % $length}]
return [concat [lrange $xs $n end] [lrange $xs 0 $n-1]]
} KPV This is a fairly well-know technical interview question. One quick solution is to concatenate the list with itself and extract out $length items starting at $n.
proc lrotate3 {xs {n 1}} {
set length [llength $xs]
if {$n == 0 || $length == 0 } {return $xs}
set n [expr {($n % $length) - 1}]
return [lrange [concat $xs $xs] $n+1 $length+$n]
}set xs {1 2 3 4 5}
set ns {{} -1 2 0}
foreach n $ns {
foreach cmd {lrotate lrotate2 lrotate3} {
set inv [concat $cmd [list $xs] $n]
puts [list {*}$inv]
puts [time $inv 1000000]
}
}
lrotate {1 2 3 4 5}
3.004224 microseconds per iteration
lrotate2 {1 2 3 4 5}
2.952052 microseconds per iteration
lrotate3 {1 2 3 4 5}
4.958409 microseconds per iteration
lrotate {1 2 3 4 5} -1
10.49206 microseconds per iteration
lrotate2 {1 2 3 4 5} -1
2.928712 microseconds per iteration
lrotate3 {1 2 3 4 5} -1
4.869703 microseconds per iteration
lrotate {1 2 3 4 5} 2
5.185748 microseconds per iteration
lrotate2 {1 2 3 4 5} 2
2.903272 microseconds per iteration
lrotate3 {1 2 3 4 5} 2
4.819574 microseconds per iteration
lrotate {1 2 3 4 5} 0
0.684359 microseconds per iteration
lrotate2 {1 2 3 4 5} 0
0.739171 microseconds per iteration
lrotate3 {1 2 3 4 5} 0
0.741189 microseconds per iteration