How to shuffle cards with #Neo4j

kudos-5
graph-algorithms

(Bratanic Tomaz) #1

Hi all,

I made a post to show how to shuffle cards with random walk algorithm in Neo4j.


(Andrew Bowman) #2

Copying my reply over, and adjusting as the actual hand size was 8, not 7:

Love the randomWalk usage!

Just to note APOC Procedures has support for shuffling a collection or taking random items from collections, which might work a bit easier when you need to get items from a shuffled set of nodes.

For example:

MATCH (card:Card)
WITH collect(card) as deck
WITH apoc.coll.shuffle(deck) as deck
RETURN deck[..8] as hand

or

MATCH (card:Card)
WITH collect(card) as deck
RETURN apoc.coll.randomItems(deck, 8) as hand

While randomWalk may not be the best means to shuffle, it is really neat that you can do this just with traversals, lots of great applications for this!


(Andrew Bowman) #3

Keep in mind also that your randomWalk() approach allows the possibility of revisiting previously visited nodes, so the hands generated may contain duplicate cards, not a thing that should be allowed to happen when simulating a card deck.

EDIT

Though I guess you're actually simulating separate games, so each individual traversal simulates a draw of 2 from an entirely new shuffle, so since we can never traverse back to the start, we can never draw the same card twice in a row, so for this kind of game it works.


(Bratanic Tomaz) #4

Yes maybe I didn’t elaborate that much on my game :slightly_smiling_face: In my case no sequence of two cards will contain duplicate cards, because I didn’t create a relationships from a card to itself. But you are correct, every new game(sequence of 2 cards) means a new shuffle of cards in my scenario as the cards can repeat, because random walk algorithm can revisit previously visited nodes. If any of you is interested in expanding the game, this is taken from the paper http://web.cs.elte.hu/~lovasz/erdos.pdf:

For example, consider the shuffling of a deck of
cards. Construct a graph whose nodes are all permutations of the deck, and
two of them are adjacent if they come by one shuffle move (depending on
how you shuffle). Then repeated shuffle moves correspond to a random walk
on this graph (see Diaconis [20])


(The Graph Giraffe) #5

Thanks for submitting!

I’ve added a tag that allows your blog to be displayed on the community home page!