近乎完美的洗牌

Question

要使用偏移量k几乎完美地洗牌一副n张牌，请执行以下步骤：

• 从牌组D中取出k顶牌，将它们放在新的P堆上，一次一张
• 将剩余的n-k卡平分为上半部分（T）和下半部分（B）
• 按此顺序将B和T的底部卡片放在P的顶部
• 重复上一步，直到所有牌都在P上，P成为洗牌牌组

例如：
n=11，k=3，起始甲板从底部开始：3 7 9 A 2 8 J k 6 4 Q
首先，我们在桩P上放置Q，然后放置4，然后放置6。
然后我们将剩下的卡分成下半部分：379A和上半部分：28JK.
B的底牌是3，我们把它放在P上，然后T的底牌是2 重复上一步，我们最终得到了洗牌牌组：q46332789jak.
您的任务是编写一个程序，对于给定的值n和k，该程序输出需要多少次近乎完美的洗牌才能将完全排序的数据组返回到其原始状态

示例输入1

6  
0 

示例输出1
4
示例输入2

11  
3  

示例输出2
10

约束条件

• 3<；=n<；=一百万
• 0<；=k<；=n
• 对于提供的输入，n-k始终为偶数
• 所需输出不超过1018

我在这个问题上困惑了很久，但我一直遇到问题
我该怎么解决这个问题

我的代码正在运行：

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

Answer 1

回答这个问题有两种方法-第二种方法效率更高，因为它速度更快，这就是为什么它在Perse编码挑战中获得满分的原因

第一种（效率较低的）方法

就是创建一个虚拟牌组，然后虚拟地洗牌。这是可行的，但对于较大的值n（例如1000000），这可能会很慢，因此在将其作为答案提交时会导致超时。我的代码如下：

#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个

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

  • 为了简单起见，让我们假设k=0，甲板是：abcdefgh
  • A在位置0，B在位置1，等等
  • 把它分成两部分，得到A，B，C，D和E，F，G，H
  • 完美的洗牌会产生一个E B F C G D H
  • 注意A、B、C、D的位置。之前，它们分别位于甲板的位置0、1、2和3。现在，他们在位置0，2，4，6。你所做的就是把他们在甲板上的位置乘以2
  • 现在让我们看看E，F，G，H。它们分别位于位置4，5，6，7，但现在它们位于位置1，3，5，7。
    1. 首先，我们从每个位置减去甲板上半部分的尺寸（例如，4-4=0）
    2. 然后我们把它乘以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返回其起点。4个循环后，卡Y返回其起点。因此，两张牌要同时回到起始点，我们需要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))