[Feature Request]Add new function `-shuffle`

[cireu]

Since we have -sort to sort a list with fn. There should be a -shuffle to disorder the list

I try to wrote a function like

(defun -shuffle (list)
  (declare (pure t) (side-effect-free t))
  (let* ((source (copy-sequence list))
         (random-nums (->> list
                           length
                           (number-sequence 1)
                           (-map #'random)
                           nreverse))
         result)
    (--each random-nums
      (setq source (-rotate it source))
      (push (car source) result)
      (!cdr source))
    result))

It generate a number-sequence first then use random to disorder and nreverse to reverse it. Then use these random number to -rotate the list. collect the head and reset the tail to source for next rotation.

Do you have faster implementation?

[Fuco1]

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.

[Fuco1]

Oh wait nevermind, it's actually correct.

I thought number-sequence just generated (10 10 10 10 10 10 ...) which would then make the bias towards front element (since e.g rotation of 1 and 9 on an 8-length list is the same). But it actually generates an ascending sequence.

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.

[cireu]

(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 cl-rotatef from cl-macs. So I wrote it with -rotate you see it.

---

I expand the cl-rotatef macro

(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 -shuffle and -shuffle1 has much more disordered result than -shuffle-origin and -shuffle2

[Fuco1]

I think the problem with -shuffle2 is that it doesn't update the source, i.e. can also shuffle numbers from the front to the "working" position. That shouldn't happen in the inside-out algorithm as I understand it.

In other words the it-index correctly identifies the working place but in it we can refer to a previous position.

I think the -shuffle1 is a good implementation, except you can use -split-at instead of two calls to -take and -drop

If you want to open a PR with some examples added to the tests that would be neat!

[cireu]

I'd like to open a PR. But I found that dash.el is in ELPA and -shuffle1 is 15 lines. I don't have an Emacs Copyright Assignment now. It may takes a long time for me to do it. :(

---

Using -split-at will be more readable, but it's a litte more cumbersome because we need extra car and cdr to get the splitted list

[Fuco1]

There's the -let macro which allows for desctructuring

(-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)))

[cireu]

Well, I even don't know how to write a test-example for a shuffle function now.... :joy:

[cireu]

Hello. I got an Emacs Copyright Assignment now. I will reopen a PR to continue this work

[cireu]

What about the progress on this? @Fuco1