lrotate

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 5

I'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

HE 2016-03-18: As we could see lrotate3 is slower than lrotate2. I thought it could be useful to do the index math with expr:

proc lrotate4 {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] [expr {$n+1}] [expr {$length+$n}]]
}

This helped a lot. If it works here it also work for lrotate2:

proc lrotate5 {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 [expr {$n-1}]]]
}

And now if we don't use the variable length and calculate the length of the list in place:

proc lrotate6 {xs {n 1}} {
    if {$n == 0 || [llength $xs] == 0 } {return $xs}
    set n [expr {$n % [llength $xs]}]
    return [concat [lrange $xs $n end] [lrange $xs 0 [expr {$n-1}]]]
}

This looks like it is the fastest. At least on my win7 box with Tcl 8.6.1. The Timings:

set xs {1 2 3 4 5}
set ns {{} -1 2 3 4 0}
foreach n $ns {
        foreach cmd {lrotate lrotate2 lrotate3 lrotate4 lrotate5 lrotate6} {
                set inv [concat $cmd [list $xs] $n]
                puts [list {*}$inv]
                puts [time $inv 1000000]
        }
        puts {}
}
lrotate {1 2 3 4 5}
1.989758 microseconds per iteration
lrotate2 {1 2 3 4 5}
1.975649 microseconds per iteration
lrotate3 {1 2 3 4 5}
3.316893 microseconds per iteration
lrotate4 {1 2 3 4 5}
2.576548 microseconds per iteration
lrotate5 {1 2 3 4 5}
1.578767 microseconds per iteration
lrotate6 {1 2 3 4 5}
1.480678 microseconds per iteration

lrotate {1 2 3 4 5} -1
6.909545 microseconds per iteration
lrotate2 {1 2 3 4 5} -1
1.973143 microseconds per iteration
lrotate3 {1 2 3 4 5} -1
3.328409 microseconds per iteration
lrotate4 {1 2 3 4 5} -1
2.543941 microseconds per iteration
lrotate5 {1 2 3 4 5} -1
1.58668 microseconds per iteration
lrotate6 {1 2 3 4 5} -1
1.513842 microseconds per iteration

lrotate {1 2 3 4 5} 2
3.491099 microseconds per iteration
lrotate2 {1 2 3 4 5} 2
1.973063 microseconds per iteration
lrotate3 {1 2 3 4 5} 2
3.32376 microseconds per iteration
lrotate4 {1 2 3 4 5} 2
2.575453 microseconds per iteration
lrotate5 {1 2 3 4 5} 2
1.594157 microseconds per iteration
lrotate6 {1 2 3 4 5} 2
1.497495 microseconds per iteration

lrotate {1 2 3 4 5} 3
4.945149 microseconds per iteration
lrotate2 {1 2 3 4 5} 3
1.977761 microseconds per iteration
lrotate3 {1 2 3 4 5} 3
3.331458 microseconds per iteration
lrotate4 {1 2 3 4 5} 3
2.571252 microseconds per iteration
lrotate5 {1 2 3 4 5} 3
1.586918 microseconds per iteration
lrotate6 {1 2 3 4 5} 3
1.496789 microseconds per iteration

lrotate {1 2 3 4 5} 4
6.429269 microseconds per iteration
lrotate2 {1 2 3 4 5} 4
1.975645 microseconds per iteration
lrotate3 {1 2 3 4 5} 4
3.326426 microseconds per iteration
lrotate4 {1 2 3 4 5} 4
2.544748 microseconds per iteration
lrotate5 {1 2 3 4 5} 4
1.593869 microseconds per iteration
lrotate6 {1 2 3 4 5} 4
1.491271 microseconds per iteration

lrotate {1 2 3 4 5} 0
0.488764 microseconds per iteration
lrotate2 {1 2 3 4 5} 0
0.591116 microseconds per iteration
lrotate3 {1 2 3 4 5} 0
0.597672 microseconds per iteration
lrotate4 {1 2 3 4 5} 0
0.602353 microseconds per iteration
lrotate5 {1 2 3 4 5} 0
0.601545 microseconds per iteration
lrotate6 {1 2 3 4 5} 0
0.440817 microseconds per Iteration

Even with 200 elements the time is only slightly increased.

lrotate2 {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199} 4
2.657402 microseconds per iteration
lrotate6 {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199} 4
2.18812 microseconds per Iteration

Category Command

Category Data Structure