问题描述
所以我在 python 中实现了块交换算法.
我遵循的算法是这样的:
初始化 A = arr[0..d-1] 和 B = arr[d..n-1]1) 执行以下操作，直到 A 的大小等于 B 的大小
a) 如果 A 较短，则将 B 分成 Bl 和 Br，使得 Br 相同长度为 A.交换 A 和 Br 以将 ABlBr 更改为 BrBlA.现在A是在它的最后位置，所以在 B 块上重复.
b) 如果 A 更长，则将 A 分成 Al 和 Ar，使得 Al 相同长度为 B 交换 Al 和 B 以将 AlArB 变为 BArAl.现在 B是在它的最后位置，所以在 A 的片段上重复.
2) 最后当 A 和 B 大小相等时，块交换它们.
同样的算法已经在这个网站上用 C 实现了 - Array旋转
我的python代码是
a = [1,2,3,4,5,6,7,8]x = 2n = len(a)定义旋转(a，x):n = len(a)如果 x == 0 或 x == n:返回一个如果 x == n -x:打印(一)对于范围(x)中的我:a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]打印(一)返回一个如果 x 我在每个阶段都得到了正确的值，但递归函数调用没有返回预期的结果，我似乎无法理解原因.有人可以解释我的递归有什么问题吗?以及可能的替代方案是什么.
您可以在 Python 中使用 deque:
>>>从集合导入双端队列>>>d=deque([1,2,3,4,5])>>>d双端队列([1, 2, 3, 4, 5])>>>d.旋转(2)>>>d双端队列([4, 5, 1, 2, 3])>>>d.旋转(-2)>>>d双端队列([1, 2, 3, 4, 5])或者使用列表切片:
>>>li=[1,2,3,4,5]>>>li[2:]+li[:2][3, 4, 5, 1, 2]>>>li[-2:]+li[:-2][4, 5, 1, 2, 3]请注意，符号约定与 deque.rotate 与切片相反.
如果你想要一个具有相同符号约定的函数:
def 旋转(l，y=1):如果 len(l) == 0:返回 ly = -y % len(l) # 翻转旋转方向返回 l[y:] + l[:y]>>>旋转([1,2,3,4,5],2)[4, 5, 1, 2, 3]>>>旋转([1,2,3,4,5],-22)[3, 4, 5, 1, 2]>>>旋转('abcdefg'，3)'efgabcd'对于 numpy，只需使用 np.roll
>>>一种数组([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])>>>np.roll(a, 1)数组([9, 0, 1, 2, 3, 4, 5, 6, 7, 8])>>>np.roll(a, -1)数组([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])或者您可以使用上述 rotate 的 numpy 版本(再次注意符号与 np.roll 的区别):
defrotate(a,n=1):如果 len(a) == 0:返回一个n = -n % len(a) # 翻转旋转方向返回 np.concatenate((a[n:],a[:n]))So I am implementing a block swap algorithm in python.
The algorithm I am following is this:
Initialize A = arr[0..d-1] and B = arr[d..n-1]1) Do following until size of A is equal to size of B
a) If A is shorter, divide B into Bl and Br such that Br is of same length as A. Swap A and Br to change ABlBr into BrBlA. Now A is at its final place, so recur on pieces of B.
b) If A is longer, divide A into Al and Ar such that Al is of same length as B Swap Al and B to change AlArB into BArAl. Now B is at its final place, so recur on pieces of A.
2) Finally when A and B are of equal size, block swap them.
The same algorithm has been implemented in C on this website - Array Rotation
My python code for the same is
a = [1,2,3,4,5,6,7,8]
x = 2
n = len(a)
def rotate(a,x):
n = len(a)
if x == 0 or x == n:
return a
if x == n -x:
print(a)
for i in range(x):
a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]
print(a)
return a
if x < n-x:
print(a)
for i in range(x):
a[i], a[(i-x+n) % n] = a[(i-x+n) % n], a[i]
print(a)
rotate(a[:n-x],x)
else:
print(a)
for i in range(n-x):
a[i], a[(i-(n-x) + n) % n] = a[(i-(n-x) + n) % n] , a[i]
print(a)
rotate(a[n-x:], n-x)
rotate(a,x)
print(a)
I am getting the right values at each stage but the recursive function call is not returning the expected result and I cannot seem to understand the cause. Can someone explain whats wrong with my recursion ? and what can be the possible alternative.
You can rotate a list in place in Python by using a deque:
>>> from collections import deque
>>> d=deque([1,2,3,4,5])
>>> d
deque([1, 2, 3, 4, 5])
>>> d.rotate(2)
>>> d
deque([4, 5, 1, 2, 3])
>>> d.rotate(-2)
>>> d
deque([1, 2, 3, 4, 5])
Or with list slices:
>>> li=[1,2,3,4,5]
>>> li[2:]+li[:2]
[3, 4, 5, 1, 2]
>>> li[-2:]+li[:-2]
[4, 5, 1, 2, 3]
Note that the sign convention is opposite with deque.rotate vs slices.
If you want a function that has the same sign convention:
def rotate(l, y=1):
if len(l) == 0:
return l
y = -y % len(l) # flip rotation direction
return l[y:] + l[:y]
>>> rotate([1,2,3,4,5],2)
[4, 5, 1, 2, 3]
>>> rotate([1,2,3,4,5],-22)
[3, 4, 5, 1, 2]
>>> rotate('abcdefg',3)
'efgabcd'
For numpy, just use np.roll
>>> a
array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
>>> np.roll(a, 1)
array([9, 0, 1, 2, 3, 4, 5, 6, 7, 8])
>>> np.roll(a, -1)
array([1, 2, 3, 4, 5, 6, 7, 8, 9, 0])
Or you can use a numpy version of the same rotate above (again noting the difference in sign vs np.roll):
def rotate(a,n=1):
if len(a) == 0:
return a
n = -n % len(a) # flip rotation direction
return np.concatenate((a[n:],a[:n]))
这篇关于Python 数组旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！