如何在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]]