How to rotate a binary vector to minimum in Python

Question 1

The fastest way to do this is create a table first and then you can use ndarray indexing to get the result, here is the code:

You need create the table yourself, the code here is just a demo

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)

Then we can use bitmap and numpy.packbits() and 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

here is the output:

[[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]]

Question 2

Try this:

v = np.array([0,0,1,1,1,0,0,0]) #testing value

count = 0
def f(x):
    global count
    if x: count = 0 
    else: count += 1
    return count
uf = np.vectorize(f)

v = np.array([0,0,1,1,1,0,0,0])
v2 = np.concatenate((v,v))    
vs = uf(v2)
i = vs.argmax()
m = vs[i]
rot = i-m + 1
print np.roll(v2,-rot)[:v.size] #output: [0 0 0 0 0 1 1 1]

Question 3

I am not sure if numpy provides this, but it is strange that none of the numpy guys has answered so far.

If there is no already builtin way to do this, I would go about it like this:

Convert your array to an int
Then do the rotating over the pure int and test for the minimum
Convert back to array

This way your array rotations are reduced to bit-shifts which should be quite fast.

If your bitarrays are of the size for the samples, I guess this could suffice (I have no numpy at hands, but logic should be the same):

#! /usr/bin/python3

def array2int (a):
    i = 0
    for e in a: i = (i << 1) + e
    return i

def int2array (i, length):
    return [ (i >> p) & 1 for p in range (length - 1, -1, -1) ]

def rot (i, length):
    return ( (i & ((1 << (length - 1) ) - 1) ) << 1) | (i >> (length - 1) )

def rotMin (a):
    length = len (a)
    minn = i = array2int (a)
    for _ in range (length):
        i = rot (i, length)
        if i < minn: minn = i
    return int2array (minn, length)

#test cases
for case in (16, 160, 193, 0, 255, 170, 240, 56, 143):
    case = int2array (case, 8)
    result = rotMin (case)
    print ("{} -> {}".format (case, result) )

If they are way longer, you maybe would like to find first the longest runs of zeros, and then only test those cases that begin with such a run.

Output is:

[0, 0, 0, 1, 0, 0, 0, 0] -> [0, 0, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 0, 0, 0, 0] -> [0, 0, 0, 0, 0, 1, 0, 1]
[1, 1, 0, 0, 0, 0, 0, 1] -> [0, 0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0] -> [0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1] -> [1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 1, 0] -> [0, 1, 0, 1, 0, 1, 0, 1]
[1, 1, 1, 1, 0, 0, 0, 0] -> [0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 0, 0, 0] -> [0, 0, 0, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 1, 1, 1, 1] -> [0, 0, 0, 1, 1, 1, 1, 1]

Question 4

Using numpy I can't completely avoid iteration, but I can limit it to the smallest dimension, the number of possible rotations (8). I've found several alternatives. I suspect the last is fastest, but I haven't done time tests. The core idea is to collect all the possible rotations into an array, and pick the minimum value from those.

x=[[0, 0, 0, 1, 0, 0, 0, 0],
   [1, 0, 1, 0, 0, 0, 0, 0],
   [1, 1, 0, 0, 0, 0, 0, 1],
   ...
   [1, 0, 0, 0, 1, 1, 1, 1]]
x = np.array(x)
M,N = x.shape
j = 2**np.arange(N)[::-1] # powers of 2 used convert vector to number
# use np.dot(xx,j) to produce a base 10 integer

A) In the first version I collect the rotations in a 3D array

xx = np.zeros([M, N, N],dtype=int)
for i in range(N):
  xx[:,i,:] = np.roll(x, i, axis=1)
t = np.argmin(np.dot(xx, j), axis=1) # find the mimimum index
print t
print xx[range(M),t,:]

produces:

[4 5 6 0 0 1 4 3 7]

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

B) A variation would be to store the np.dot(xx, j) values in a 2D array, and convert the minimum of each row back to the 8 column array.

xx = x.copy()
for i in range(N):
  y = np.roll(x, i, axis=1)
  xx[:,i] = np.dot(y, j)
y = np.min(xx, axis=1)
print y
# [4 5 6 0 0 1 4 3 7]
# convert back to binary
z = x.copy()
for i in range(N):
   z[:,i] = y%2
   y = y//2
z = np.fliplr(z)
print z

I couldn't find a numpy way of converting a vector of numbers to a binary array. But with N much smaller than M, this iterative approach isn't costly. numpy.base_repr uses this, but only operates on scalars. [int2array and np.unpackbits used in the other answers are faster.]

C) Better yet, I could roll j rather than x:

xx = x.copy()
for i in range(N):
   xx[:,i] = np.dot(x, np.roll(j,i))
y = np.min(xx, axis=1)
print y

D) Possible further speed up by constructing an array of rotated j, and doing the dot product just once. It may be possible to construct jj without iteration, but creating an 8x8 array just once isn't expensive.

jj = np.zeros([N,N], dtype=int)
for i in range(N):
  jj[:,i] = np.roll(j,i)
print jj
xx = np.dot(x, jj)
# or xx = np.einsum('ij,jk',x,jj)
y = np.min(xx, axis=1)
print y

Timing notes:

For small x, such as the sample 9 rows, the first solution (A) is fastest. Converting the integers back to binary takes up a 1/3 of time, slowing down the other solutions.

But for a large x, such as 10000 rows, the last is best. With IPython timeit

A) 10 loops, best of 3: 22.7 ms per loop
B) 100 loops, best of 3: 13.5 ms per loop
C) 100 loops, best of 3: 8.21 ms per loop
D) 100 loops, best of 3: 6.15 ms per loop
# Hyperboreous: rotMin(x1)
# adapted to work with numpy arrays
H) 1 loops, best of 3: 177 ms per loop

At one point I thought I might gain speed by selectively rotating rows only until they reach their minimum value. But these added samples show that I cannot use a local minimum:

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

corresponding xx values

[168  81 162  69 138  21  42  84]
[152  49  98 196 137  19  38  76]
[145  35  70 140  25  50 100 200]
[ 84 168  81 162  69 138  21  42]
[ 82 164  73 146  37  74 148  41]

But notice that the minimum for each of these rows is the first 0 of the longest run of 0s. So it might possible to find the minimum without doing all the rotations and conversion to numeric value.

Question 5

You can use collection deques rotate function if you convert your array to a list, you can convert it back to an array whence you're done with your rotations.

import numpy as np  
import collections   #import collections and deque
from collections import deque
vector = np.array([1, 1,0])  # example array
list =  vector.tolist()     # use tolist() to convert the array "vector" to a list

n = collections.deque(list)    # convert the list to a deque

#rotate two closest       
print n.rotate(1)
>>> deque([1, 1, 0])
#rotate three closest
print n.rotate(2) 
deque([1, 0, 1])

n.rotate(-1) to rotate back from last rotation