Overhand Shuffle with Clojure - almost

Question

I'm trying to implement a Overhand Shuffle in Clojure as a bit of a learning exercise

So I've got this code...

(defn overhand [cards]
    (let [ card_count (count cards)
          _new_cards '()
         _rand_ceiling (if (> card_count 4) (int (* 0.2 card_count)) 1)]
      (take card_count
            (reduce into (mapcat
                           (fn [c]
                             (-> (inc (rand-int _rand_ceiling))
                                 (take cards)
                                 (cons _new_cards)))
                           cards)))))

It is very close to doing what I want, but it is repeatedly taking the first (random) N number of cards off the front, but I want it to progress through the list...

calling as

(overhand [1 2 3 4 5 6 7 8 9])

instead of ending up with

(1 2 3 1 2 1 2 3 4)

I want to end up with

(7 8 9 5 6 1 2 3 4)

Also, as a side note this feels like a really ugly way to indent/organize this function, is there a more obvious way?

Answer 1

A better way to organise the function is to separate the shuffling action from the random selection of splitting points that drive it. Then we can test the shuffler with predictable splitters.

The shuffling action can be expressed as

(defn shuffle [deck splitter]
  (if (empty? deck)
    ()
    (let [[taken left] (split-at (splitter (count deck)) deck)]
      (concat (shuffle left splitter) taken))))

where

• deck is the sequence to be shuffled
• splitter is a function that chooses where to split deck, given its size.

We can test shuffle for some simple splitters:

=> (shuffle (range 10) (constantly 3))
(9 6 7 8 3 4 5 0 1 2)
=> (shuffle (range 10) (constantly 2))
(8 9 6 7 4 5 2 3 0 1)
=> (shuffle (range 10) (constantly 1))
(9 8 7 6 5 4 3 2 1 0)

It works.

Now let's look at the way you choose your splitting point. We can illustrate your choice of _rand_ceiling thus:

=> (map
     (fn [card_count] (if (> card_count 4) (int (* 0.2 card_count)) 1))
     (range 20))
(1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3)

This implies that you will take just one or two cards from any deck of less than ten. By the way, a simpler way to express the function is

(fn [card_count] (max (quot card_count 5) 1))

So we can express your splitter function as

(fn [card_count] (inc (rand-int (max (quot card_count 5) 1))))

So the shuffler we want is

(defn overhand [deck]
  (let [splitter (fn [card_count] (inc (rand-int (max (quot card_count 5) 1))))]
    (shuffle deck splitter)))

Answer 2

Answering your indentation question, you could refactor your function. For instance, pull out the lambda expression from mapcat, defn it, then use its name in the call to mapcat. You'll not only help with the indentation, but your mapcat will be clearer.

For instance, here's your original program, refactored. Please note that issues with your program have not been corrected, I'm just showing an example of refactoring to improve the layout:

(defn overhand [cards]
    (let [ card_count (count cards)
          _new_cards '()
         _rand_ceiling (if (> card_count 4) (int (* 0.2 card_count)) 1)]

        (defn f [c]
            (-> (inc (rand-int _rand_ceiling))
                (take cards)
                (cons _new_cards)))

        (take card_count (reduce into (mapcat f cards)))))

You can apply these principles to your fixed code.

A great deal of indentation issues can be resolved by simply factoring out complex expressions. It also helps readability in general.

Answer 3

this function is creating a list of lists, transforming each of them, and cating them back together. the problem it that it is pulling from the same thing every time and appending to a fixed value. essentially it is running the same operation every time and so it is repeating the output over with out progressing thgough the list. If you break the problem down differently and split the creation of random sized chunks from the stringing them together it gets a bit easier to see how to make it work correctly.

some ways to split the sequence:

(defn random-partitions [cards]
  (let [card_count (count cards)
        rand_ceiling (if (> card_count 4) (inc (int (* 0.2 card_count))) 1)]
   (partition-by (ƒ [_](= 0 (rand-int rand_ceiling))) cards)))

to keep the partitions less than length four

(defn random-partitions [cards]
  (let [[h t] (split-at (inc (rand-int 4)) cards)]
    (when (not-empty h) (lazy-seq (cons h (random-partition t))))))

or to keep the partitions at the sizes in your original question

(defn random-partitions [cards]
  (let [card_count (count cards)
        rand_ceiling (if (> card_count 4) (inc (int (* 0.2 card_count))) 1)
        [h t] (split-at (inc (rand-int rand_ceiling)) cards)]
    (when (not-empty h) (lazy-seq (cons h (random-partition t))))))

(random-partitions [1 2 3 4 5 6 7 8 9 10])
((1 2 3 4) (5) (6 7 8 9) (10))

this can also be written without directly using lazy-seq:

(defn random-partitions [cards]
  (->> [[] cards]
       (iterate
        (ƒ [[h t]]
          (split-at (inc (rand-int 4)) t)))
       rest ;iterate returns its input as the first argument, drop it.
       (map first)
       (take-while not-empty)))

which can then be reduced back into a single sequence:

(reduce  into (random-partitions [1 2 3 4 5 6 7 8 9 10]))
(10 9 8 7 6 5 4 3 1 2)

if you reverse the arguments to into it looks like a much better shuffle

 (reduce #(into %2 %1) (random-partitions [1 2 3 4 5 6 7 8 9 10]))
(8 7 1 2 3 4 5 6 9 10)