Hacker News Reader

Comment by astine | Hacker News Reader

I can honestly say that that isn't the algorithm that would have occured to me. In CL, this is the what I would have thought to do:

  (defun butnth (index list)
    (append (subseq list 0 index)
  	    (subseq list (1+ index))))

  (defun shuffle (list)
    (unless (null list)
      (let ((index (random (list-length list))))
        (cons (nth index list)
  	      (shuffle (butnth index list))))))

Building a second sequence by randomly selecting nodes from the old sequnece and inserting them into the new sequence seems more intuitive to me. It certainly works better with lists. If I where working with arays, the OPs method would be more efficient.

View on HN

Won't that explode somewhat performance-wise once you have more than a handful of cards? It looks like something along the lines of O(n^2)...

As it's written I'll blow the call stack before I see a performance decrease. :)

Actually, the algorithm is O(n), it's essentially a list reversal with a call to random inserted. In psuedocode:

  oldlist = [...]
  newlist = []
  
  if oldlist not empty
  do
    x = remove random from oldlist
   insert x into newlist
  repeat

Of course, I'm ignoring the complexity of 'butnth' in that assesment, but this was just a 'first instinct' sort of deal.

I didn't like the butnth. I get an allergic reaction to append. Blame Ken Tilton.

  (defun shuffle-in-place (l)
    (cond ((null l) nil)
          (t (rotatef (nth 0 l)
                      (nth (random (length l)) l))
             (shuffle-in-place (rest l))))
    l)

  (defun shuffle (l)
    (shuffle-in-place (copy-list l)))

Blame Ken Tilton.

I do. Always.

One could use nconc instead of append, but that's not where the processor cycles are being lost as far as I can tell.

It's not O(n): both 'nth' and 'butnth' are themselves O(n), and get called 'n' times. I'm fairly certain you'll end up with O(n^2) unless you introduce mutation. I'm also fairly certain there is no purely functional O(n) algorithm. ;)

You're right of course; I'm not looking very deeply.

I'm also fairly certain there is no purely functional O(n) algorithm.

  (defun nth (index list)
    (if (zerop index)
        (first index)
        (nth (1- index) (rest list))))

I meant for perfect shuffling, not 'nth'. :)

This is for you, since I've already had three today & the brainos in your nth implementation are a strong indication for its prescription:

http://www.espressoguide.net/resources/images/articles/A002I...

Cheers!

Interesting.

It makes me realize how much whether one begins with lists which allow cheap insertions or not affects both one's choice of algorithm and one's thinking.

I think you're doing the same thing as the "good" knuth algorithm which, as I read it, always exchanges the random card with the one at the decreasing index from the end of the deck.

Reply on news.ycombinator.com