|
the task description says "A shuffle that produces a randomized result is to be preferred." so i don't see how this is compared to general permutation tasks which seem to ask for all possible permutations instead of one random permutation.
:::''I interpeted that as meaning that when multiple best solutions are possible we should randomly pick from that set of best solutions. --[[User:Rdm|Rdm]] 10:56, 14 October 2011 (UTC)''
::hmm, that's an interesting interpretation, supported by the fact that random is an option, but it would make this task even more like the permutation tasks where all permutations need to be generated.
<del>
i posted a function for generating a random permutation as per the task description, and am still working on comparing the results.
<del>
maybe it is better to save the incomplete solution here and move it to the main page when it is ready.
:--[[User:EMBee|eMBee]] 07:21, 14 October 2011 (UTC) </del>▼
:new version is ready and moved to main page.--[[User:EMBee|eMBee]] 11:14, 14 October 2011 (UTC)
:better-shuffle is based on a [http://blog.viridian-project.de/2008/04/06/sequence-shuffling-revisited/ discussion here]
<lang lisp>(defun better-shuffle (seq)
(let ((tagged (mapcar (lambda (x) (cons (random 1.0) x)) (loop for char across seq collect char))))
(coerce (mapcar 'cdr (sort tagged #'> :key 'car)) 'string)))
(defun compare-shuffle (seq sqe)
(list (count T (mapcar (lambda (x y) (equalp x y))
(loop for char across seq collect char)
(loop for char across sqe collect char)))
sqe seq))
(defun best-shuffle (seq)
(car (sort (loop repeat 10 collect
(compare-shuffle seq (better-shuffle seq))) #'< :key 'car)))))
(defun format-best-shuffle (seq)
(format t "~{~a ~a (~d)~}~%" (reverse (best-shuffle seq))))
(let ((input '("abracadabra" "seesaw" "elk" "grrrrrr" "up" "a")))
(map 'nil 'format-best-shuffle input))
abracadabra arbrabacada (2)
seesaw esaews (0)
elk lke (0)
grrrrrr rrrgrrr (5)
up pu (0)
a a (1)
NIL
▲:--[[User:EMBee|eMBee]] 07:21, 14 October 2011 (UTC)
|