How to rotate a binary vector to minimum in Python

Question

If I have an arbitrary binary vector (numpy array) in Python, e.g.

import numpy as np

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

This would give me the binary array 00001100. I could also have 00000000 or 00010100 etc. How to make such a script that when I give this binary vector as an input, the script gives the minimum right-rotated binary numpy array as output? Few examples:

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

etc. Any suggestions / good optimized Python implementations in mind? =) Thank you for any assistance. I need this for Local Binary Pattern implementation =)

And by right shifted you mean rotated? Right shifting by k is usually taken to imply dropping the k least significant bits. — user395760
– user395760, Commented Jan 31, 2014 at 19:16
+1 Sorry about that =) Yes, I mean rotation. I want to keep the bits =) I'll fix that in the post — jjepsuomi
– jjepsuomi, Commented Jan 31, 2014 at 19:16
Yes, it should be like that =) Rotated to the minimum binary value...isn't it minimum? I will add few more examples — jjepsuomi
– jjepsuomi, Commented Jan 31, 2014 at 19:18

HYRY · Accepted Answer · 2014-01-31 23:59:23Z

5

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

edited Jan 31, 2014 at 23:59

answered Jan 31, 2014 at 23:45

HYRY

97.9k28 gold badges197 silver badges192 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Hyperboreus Over a year ago

Are you positive that string slicing and concatenating is faster that bit-shifts and bit-tests? Why is this fastest?

Alvaro Fuentes · Accepted Answer · 2014-01-31 21:11:39Z

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]

answered Jan 31, 2014 at 21:11

Alvaro Fuentes

17.6k4 gold badges59 silver badges68 bronze badges

Comments

Hyperboreus · Accepted Answer · 2014-01-31 21:03:26Z

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]

+1 Thank you for your help! I will give it a go and accept your answer later =) Appreciate the help! =)

15 revs · Accepted Answer · 2014-02-03 07:36:34Z

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.

Alvaro Fuentes · Accepted Answer · 2014-02-03 13:34:13Z

1

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

edited Feb 3, 2014 at 13:34

Alvaro Fuentes

17.6k4 gold badges59 silver badges68 bronze badges

answered Jan 31, 2014 at 21:16

user1749431

5696 silver badges21 bronze badges

Collectives™ on Stack Overflow

How to rotate a binary vector to minimum in Python

5 Answers 5

1 Comment

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related