近乎完美的洗牌

The Nearly Perfect Shuffle

要使用偏移量 k 近乎完美地洗牌一副 n 牌,请执行以下步骤:

例如:
n = 11, k = 3 从底部开始甲板: 3 7 9 A 2 8 J K 6 4 Q
首先我们把Q、4、6放在P堆上。
然后我们将剩余的牌分成下半部分:3 7 9 A 和上半部分:2 8 J K.
B 的底牌是 3,我们将其放在 P 上,然后是 T 的底牌,即 2 重复上一步,我们最终得到洗牌的牌组:Q 4 6 3 2 7 8 9 J A K.
你的任务是编写一个程序,对于给定的值 n 和 k,输出需要多少次近乎完美的洗牌才能 return 完美排序的牌组回到其原始状态。

示例输入 1

6  
0 

示例输出 1
4
示例输入 2

11  
3  

示例输出 2
10

约束条件

我对这个问题困惑了很久,但我一直运行陷入困境!
我该如何解决这个问题?

我的代码正在进行中:

def shuffle(n, k):
  global shuffledA, shuffledB, shuffledZ, cards
  if 0 <= k <= n <= 1000000 and (n-k) % 2 == 0:
    cards = []
    shuffled = [None]
    shuffledA = []
    shuffledB = []
    shuffledZ = []
    num = 1
    for i in range(1, n+1):
      cards.append(i)
    shuffledZ = cards[n-1-k:n-1]
    shuffledA = cards[0:(n-k)/2-1]
    shuffledB = cards[(n-k)/2:n-k-2]

当我 运行 它总是输出这个错误,其中 n - k 是偶数:

>>> shuffle(11, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "main.py", line 256, in shuffle
    shuffledA = cards[0:(n-k)/2-1]
TypeError: slice indices must be integers or None or have an __index__ method

有两种回答这个问题的方法 - 第二种更有效因为它更快,这就是为什么它在 Perse Coding Challenge 中获得满分的原因。

第一种(效率较低)方式

是创建一个虚拟牌组,然后虚拟洗牌。这是有效的,但是如果 n 值较大(例如 1,000,000),这可能会很慢,因此在提交它作为答案时会导致超时。我的代码如下:

#Accept inputs
n = int(input())
k = int(input())
it = 1

#Apply the Nearly Perfect Shuffle
def shuffle(string):
        P = []
        global n,k
        
    if k!=0:
    #Remove the bottom k cards, place them on top
    #last goes to first, second last --> second, nth last --> nth
        for i in range(k):
            P.append(string[-i-1])
            i += 1
        string = string[:-k]

    #Now for the "perfect" part of the nearly perfect shuffle
        
    #Split deck into two
    l = len(string)//2

    B = string[:l]
    T = string[l:]
    #Add the top card from each pile onto P one by one
    for i in range(l):
        P.append(B[i])
        P.append(T[i])
    return P

#Create a deck of cards
#We do this by creating an array containing numbers from 1 to n
first = list(range(n))
#print(first)
P = shuffle(first)

#We repeatedly shuffle until we get back to where we started
while P != first:
    P = shuffle(P)
    it += 1
print(it)

更高效、更省时的方式

是找出每张洗牌背后的数学模式。

  • 每次洗牌,最后一张牌总会变成第一张牌,倒数第二张总会变成第二张……倒数第n张总会变成第n张。

  • 甲板的其余部分一分为二。

    • 为了简单起见,我们假设 k = 0,牌组是:A B C D E F G H
    • A在位置0,B在位置1,依此类推
    • 将其一分为二得到 A、B、C、D 和 E、F、G、H
    • 完美洗牌给出 A E B F C G D H[​​=56=]
    • 注意A、B、C、D的位置,之前分别在牌组的位置0、1、2、3。现在,它们位于位置 0、2、4、6。您所做的只是将它们在牌组中的位置乘以二。
    • 现在让我们看看E、F、G、H。它们分别位于位置4、5、6、7,但现在它们位于位置1、3、5、7。
      1. 首先我们从每个位置减去甲板前半部分的大小(例如 4-4 = 0)
      2. 然后我们像之前一样将其乘以二 (0*2=0)
      3. 最后我们加上 (0+1=1) 因为这张牌必须在前一张牌之后出现,而不是替换它。 E本来在4号位,现在在1号位
  • 当您沿着数组中的单个元素(一副牌中的一张牌)的路径走时,您可能会注意到它可能会循环遍历相同的位置,例如在位置 2 找到的卡片,然后是 4,然后是 5,然后是 0,然后回到 2。

  • 每张卡片都有自己的“循环”序列。想象一副牌,位置 1 的卡片 X 变为 2,然后是 3,然后再次变为 1,而位置 4 的卡片 Y 变为 5、6、7,然后再次变为 4。 3 个循环后,卡片 A returns 到达起点。 4 个循环后,卡片 Yreturns 到达起点。因此,两张张牌同时return到它们的起点,我们需要12次洗牌。这是因为12是3和4的最小公倍数

  • 基本上,您需要找到所有卡片的所有“循环”长度的最小公倍数。

代码可以找到here,但我还是复制并粘贴到了下面。

"""
12) NEARLY PERFECT SHUFFLE - ALL MARKS
"""

from math import gcd
from functools import reduce

n, k = int(input()), int(input())
sizeHalf = (n - k) // 2

nums = set(range(n))
cycles = []

# example shuffle mapping
# n = 11 k = 3
# 0  1  2  3  4  5  6  7  8  9  10
# AFTER ONE SHUFFLE GOES TO....
# 10 9  8  0  4  1  5  2  6  3  7

def findCycle(i):
  # a different way of thinking 
  # ... can I track the card at index i as it moves around until it gets back to index i?
  #... how many moves does it take (its cycle length)?

  x = i
  count = 0 

  while True:
    
    count += 1

    if x >= n - k:
      x = n - x - 1
    elif x < sizeHalf:
      x = k + x * 2
    else:
      x = k + 1 + (x - sizeHalf) * 2

    if x == i:
      return count

    nums.remove(x)


while len(nums) > 0:
    cycles.append(findCycle(nums.pop()))

lcm = cycles[0]
for i in range(1, len(cycles)):
  lcm = (lcm * cycles[i]) // gcd(lcm, cycles[i])

print(lcm)

# or do 
# print(reduce(lambda a,b : a * b // gcd(a, b), cycles))