近乎完美的洗牌
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))