近乎完美的洗牌
The Nearly Perfect Shuffle
要使用偏移量 k 近乎完美地洗牌一副 n 牌，请执行以下步骤：
- 从牌组 D 中取出 k 顶牌，将它们放在新的牌堆 P 上，一次一张。
- 将剩余的 n-k 张牌平均分成上半部分 (T) 和下半部分 (B)。
- 将 B 和 T 底牌依次放在 P 上面。
- 重复上一步，直到所有牌都在P上，成为洗牌后的牌组。
例如：
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
约束条件
- 3 <= n <= 1,000,000
- 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
有两种回答这个问题的方法 - 第二种更有效因为它更快，这就是为什么它在 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。
- 首先我们从每个位置减去甲板前半部分的大小（例如 4-4 = 0）
- 然后我们像之前一样将其乘以二 (0*2=0)
- 最后我们加上 (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))
要使用偏移量 k 近乎完美地洗牌一副 n 牌，请执行以下步骤：
- 从牌组 D 中取出 k 顶牌，将它们放在新的牌堆 P 上，一次一张。
- 将剩余的 n-k 张牌平均分成上半部分 (T) 和下半部分 (B)。
- 将 B 和 T 底牌依次放在 P 上面。
- 重复上一步，直到所有牌都在P上，成为洗牌后的牌组。
例如：
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
约束条件
- 3 <= n <= 1,000,000
- 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
有两种回答这个问题的方法 - 第二种更有效因为它更快，这就是为什么它在 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。
- 首先我们从每个位置减去甲板前半部分的大小（例如 4-4 = 0）
- 然后我们像之前一样将其乘以二 (0*2=0)
- 最后我们加上 (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))