python - 如何在 Python 中将二进制向量旋转到最小值

Question

如果我在 Python 中有一个任意二进制向量(numpy 数组)，例如

import numpy as np

vector = np.zeros((8,1))
vector[2,1] = 1
vector[3,1] = 1 

这会给我二进制数组 00001100。我也可以有 00000000 或 00010100 等。如何制作这样一个脚本，当我将这个二进制向量作为输入时，该脚本给出最小的右旋转二进制 numpy 数组作为输出？几个例子:

00010000 --> 00000001
10100000 --> 00000101
11000001 --> 00000111
00000000 --> 00000000
11111111 --> 11111111
10101010 --> 01010101
11110000 --> 00001111
00111000 --> 00000111
10001111 --> 00011111

等有什么建议/好的优化 Python 实现吗？ =) 感谢您的帮助。我需要这个用于本地二进制模式实现 =)

Answer 1

最快的方法是先创建一个表，然后你可以使用 ndarray 索引来获取结果，这里是代码:

需要自己创建表，这里的代码只是演示

import numpy as np
np.random.seed(0)

#create the table
def rotated(s):
    for i in range(len(s)):
        s2 = s[i:] + s[:i]
        if s2[-1] == "1":
            yield int(s2, 2)

bitmap = []
for i in range(256):
    s = "{:08b}".format(i)
    try:
        r = min(rotated(s))
    except ValueError:
        r = i
    bitmap.append(r)

bitmap = np.array(bitmap, np.uint8)

然后我们可以使用bitmap和numpy.packbits()和numpy.unpackbits():

a = np.random.randint(0, 2, (10, 8))
a = np.vstack((a, np.array([[1,1,0,0,0,0,0,1]])))
b = np.unpackbits(bitmap[np.packbits(a, axis=1)], axis=1)
print a
print
print b

这是输出:

[[0 1 1 0 1 1 1 1]
 [1 1 1 0 0 1 0 0]
 [0 0 0 1 0 1 1 0]
 [0 1 1 1 1 0 1 0]
 [1 0 1 1 0 1 1 0]
 [0 1 0 1 1 1 1 1]
 [0 1 0 1 1 1 1 0]
 [1 0 0 1 1 0 1 0]
 [1 0 0 0 0 0 1 1]
 [0 0 0 1 1 0 1 0]
 [1 1 0 0 0 0 0 1]]

[[0 1 1 0 1 1 1 1]
 [0 0 1 0 0 1 1 1]
 [0 0 0 0 1 0 1 1]
 [0 0 1 1 1 1 0 1]
 [0 1 0 1 1 0 1 1]
 [0 1 0 1 1 1 1 1]
 [0 0 1 0 1 1 1 1]
 [0 0 1 1 0 1 0 1]
 [0 0 0 0 0 1 1 1]
 [0 0 0 0 1 1 0 1]
 [0 0 0 0 0 1 1 1]]