makispaiktis

DCP51 - Shuffling a deck of cards

Oct 28th, 2020
650
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. This problem was asked by Facebook.
  3. Given a function that generates perfectly random numbers between 1 and k (inclusive), where k is an input, write a function
  4. that shuffles a deck of cards represented as an array using only swaps.
  5. It should run in O(N) time.
  6. Hint: Make sure each one of the 52! permutations of the deck is equally likely.
  7. '''
  8. from random import randrange, shuffle
  9.  
  10. # 1st Function
  11. def generateDeckOfCards():
  12.     ace = "A"
  13.     numbers = list()
  14.     figures = "JQK"
  15.     categories = ["heart", "spade", "diamond", "club"]
  16.     for i in range(2, 11):
  17.         numbers.append(str(i))
  18.     values = list()
  19.     # Generate all the 13 values
  20.     values.append(ace)
  21.     for number in numbers:
  22.         values.append(number)
  23.     for figure in figures:
  24.         values.append(figure)
  25.     # Now, I will generate all the cards (4 categories * 13 values)
  26.     cards = list()
  27.     for category in categories:
  28.         for value in values:
  29.             cards.append(str(value) + "-" + str(category))
  30.     return cards
  31.  
  32.  
  33. # 2nd Function
  34. def random(k):
  35.     if k > 52 * 51 / 2 / 2:
  36.         return -1000
  37.     # Here my swaps will be <= all the comparisons between my elements
  38.     return randrange(1, k+1)
  39.  
  40. # 3rd Function
  41. def doISwap():
  42.     flag = randrange(0, 2)
  43.     if flag == 0:
  44.         return False
  45.     return True
  46.  
  47. # 4th Function
  48. def shuffleCards(cards, k):
  49.     cards = generateDeckOfCards()
  50.     K = random(k)
  51.     # I will first shuffle cards with the given method and then I will begin the process with my extra
  52.     shuffled = cards.copy()
  53.     shuffle(shuffled)
  54.     # print(shuffled)
  55.     # Now, the variable "shuffled" contains a randomly shuffled version of "cards" list
  56.     SUM = 0
  57.     for i in range(len(shuffled)-1):
  58.         for j in range(i, len(shuffled)):
  59.             swap = doISwap()
  60.             if SUM == K:
  61.                 break
  62.             if swap == True:
  63.                 SUM += 1
  64.                 shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
  65.     return shuffled
  66.  
  67.  
  68. # MAIN FUNCTION
  69. cards = generateDeckOfCards()
  70. shuffled = shuffleCards(cards, 10)
  71. print(shuffled)
RAW Paste Data