4 ms·

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

by astine 17y ago

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.

duncanj 17y ago
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.
joe_the_user 17y ago
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.
crux_ 17y ago
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)...
- astine 17y ago
  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.
  - kmcgivney 17y ago
    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)))
    - astine 17y ago
      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.
  - crux_ 17y ago
    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. ;)
    - astine 17y ago
      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))))
      - crux_ 17y ago
        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/A002Image01.jpg http://www.espressoguide.net/resources/images/articles/A002I... Cheers!

by astine 17y ago

duncanj 17y ago

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.

joe_the_user 17y ago

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.

crux_ 17y ago

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

astine 17y ago
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.
- kmcgivney 17y ago
  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)))
  - astine 17y ago
    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.
- crux_ 17y ago
  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. ;)
  - astine 17y ago
    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))))
    - crux_ 17y ago
      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/A002Image01.jpg http://www.espressoguide.net/resources/images/articles/A002I... Cheers!