30 lines
839 B
Text
30 lines
839 B
Text
import : only (srfi :27 random-bits) random-integer
|
|
srfi :64 tests
|
|
|
|
define : vector-shuffle! vec
|
|
. "Shuffle the vector VEC with Knuth shuffle"
|
|
define len : vector-length vec
|
|
define : swap! i j
|
|
define tmp : vector-ref vec i
|
|
vector-set! vec i : vector-ref vec j
|
|
vector-set! vec j tmp
|
|
cond
|
|
: <= len 1
|
|
. vec
|
|
else
|
|
for-each : λ (i) : swap! i : random-integer i
|
|
reverse : cdr : iota len
|
|
. vec
|
|
|
|
define : list-shuffle the-list
|
|
. "Shuffle a list in O(N) with Knuth shuffle using an intermediate vector."
|
|
vector->list : vector-shuffle! : list->vector the-list
|
|
|
|
;; deterministic tests
|
|
test-begin "knuth-shuffle"
|
|
test-equal '() : list-shuffle '()
|
|
test-equal '(1) : list-shuffle '(1)
|
|
test-end
|
|
;; sample run
|
|
display : list-shuffle '(1 2 3 4)
|
|
newline
|