-
Notifications
You must be signed in to change notification settings - Fork 137
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Feature Request]Add new function -shuffle
#283
Comments
Generally we don't care much for performance until proven necessary. Elisp isn't a mathematical package so we're not epxecting you to work with lists of 10^5 orders. For anything less any implementation is good enough. Having said that, shuffling an array is actually a subtly tricky stuff and many people get it wrong. Your algorithm also isn't exactly correct, although for practical purposes it might be enough. You can read this blog https://www.i-programmer.info/programming/theory/2744-how-not-to-shuffle-the-kunth-fisher-yates-algorithm.html or this wikipedia page https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle for more details. tl;dr we want to make sure any shuffle has equal probability of being generated. |
Oh wait nevermind, it's actually correct. I thought In this case your algorithm is basically what I linked. Sorry, I just woke up, coffee is still processing :D Edit: I'm still not sure about the rotate though, specifically if we don't need to "unrotate" the list. Because then the previous random numbers also affect the further choices by mutating the order in the list, so 1,3 and 2,2 would end up with the same result on the 2nd place, which gives it a bias. |
(defun -shuffle1 (list)
(let ((source (copy-sequence list))
(random-nums (->> list
length
(number-sequence 1)
(-map #'random)
nreverse))
result)
(--each random-nums
(let* ((part1 (-take it source))
(part2 (-drop it source))
(target (pop part2)))
(push target result)
(setq source (nconc part1 part2))))
result)) A rigorous implementtation of Fish-Yate's shuffle alorithm In fact that I try to implement "Inside-out" shuffle algorithm first, so I wrote (defun -shuffle-origin (list)
(let ((source (copy-sequence list))
(random-nums (->> list
length
(number-sequence 1)
(-map #'random)
nreverse)))
(--each random-nums
(cl-rotatef (nth it-index source) (nth it source)))
source)) But it needs I expand the (defun -shuffle2 (list)
(let ((source (copy-sequence list))
(random-nums (->> list
length
(number-sequence 1)
(-map #'random)
nreverse))
result)
(--each random-nums
(let ((part1 (nthcdr it-index source))
(part2 (nthcdr it source))
tmpvar)
(setq tmpvar (car part1))
(setcar part1 (car part2))
(setcar part2 tmpvar)))
source)) Well, it seems that |
I think the problem with In other words the I think the If you want to open a PR with some examples added to the tests that would be neat! |
I'd like to open a PR. But I found that dash.el is in ELPA and Using |
There's the (-let (((front back) (-split-at 3 (list 1 2 3 4 5 6))))
(message "front %s back %s" front back))
;; expanded
(let
((input0
(-split-at 3
(list 1 2 3 4 5 6))))
(let*
((--dash-source-124-- input0)
(front
(pop --dash-source-124--))
(back
(car --dash-source-124--)))
(message "front %s back %s" front back))) |
Well, I even don't know how to write a test-example for a shuffle function now.... 😂 |
Hello. I got an Emacs Copyright Assignment now. I will reopen a PR to continue this work |
What about the progress on this? @Fuco1 |
Since we have
-sort
to sort a list with fn. There should be a-shuffle
to disorder the listI try to wrote a function like
It generate a number-sequence first then use
random
to disorder andnreverse
to reverse it.Then use these random number to
-rotate
the list. collect the head and reset the tail to sourcefor next rotation.
Do you have faster implementation?
The text was updated successfully, but these errors were encountered: