Last active
March 11, 2021 00:16
-
-
Save woodRock/d28ff8e776cb2a7a7f9e2363c076f774 to your computer and use it in GitHub Desktop.
Given a function that generates perfectly random numbers between 1 and k (inclusive), where k is an input, write a function that shuffles a deck of cards represented as an array using only swaps. It should run in O(N) time. Hint: Make sure each one of the 52! permutations of the deck is equally likely.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env ruby | |
| def deck | |
| ranks = ['A',*(2..10),'J','Q','K'] | |
| suits = ['♠','♦','♣','♥'] | |
| deck = [] | |
| suits.product(ranks).map { |rank, suit| deck << "#{rank}#{suit}" } | |
| deck | |
| end | |
| def shuffle deck | |
| deck.each_with_index do |card, i| | |
| rnd = i + rand(deck.size()-i) | |
| deck[i], deck[rnd] = deck[rnd], deck[i] | |
| end | |
| return deck | |
| end | |
| p shuffle(deck).pop(5) |
K is input, you can not consider the deck size as input to the rand function.
@CristianoPassos could you please elaborate?
I wrote this quite some time ago. I understood the question as k is the length of the deck. Ruby has a random number generator rand() built into its standard library. So I just chose to use that. Is there something I am missing here?
I understand my code may not run in the O(N) time complexity. At the time I wrote this, I had next to no experience in optimization, and Big O(N) notation.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
K is input, you can not consider the deck size as input to the rand function.