Python : efficient bytearray incrementation

Question

How to iterate all possible values of bytearray of length = n in Python ? in worst case n <= 40bytes

For example, iterate for n = 4 :

00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000010

.
.
.
.

11111111 11111111 11111111 11111110
11111111 11111111 11111111 11111111

I will not need all combinations :) i just need hint how to implement that - real usage will be a little bit different. — Martin V.
– Martin V., Commented Apr 29, 2013 at 4:52
This is better done one by one mathematically. 2^320 for all combinations is a lot of combinations. Years of time and all the memory of all computers etc... 2^320 is 2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576 numbers... — dawg
– dawg, Commented Apr 29, 2013 at 5:18
Yes @MartinV. How do you ever expect to reach the worst case of 2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962086936576? — jamylak
– jamylak, Commented Apr 29, 2013 at 6:29

Ashwini Chaudhary · Accepted Answer · 2013-04-29 05:05:28Z

4

You can use itertools.product:

In [11]: from itertools import product

In [15]: for x in product('01',repeat=4): #for your n=4 change repeat to 32 
    print "".join(x)
   ....:     
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

edited Apr 29, 2013 at 5:05

answered Apr 29, 2013 at 4:50

Ashwini Chaudhary

252k60 gold badges478 silver badges519 bronze badges

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

1 Comment

Martin V. Over a year ago

Thats great thank you. I am just reading http://docs.python.org/2/library/itertools.html#itertools.product and its really cool.

Community · Accepted Answer · 2017-05-23 12:25:06Z

2

Inspired by https://stackoverflow.com/a/15538456/1219006

n = 2
[[[i>>k&1 for k in range(j, j-8, -1)] for j in range(8*n-1, 0, -8)] 
 for i in range(2**(8*n))]

You'll need to run this on Python 3 for large n cause xrange doesn't support big ints.

As a generator:

def byte_array(n):
    for i in range(2**(8*n)):
        yield [[i>>k&1 for k in range(j, j-8, -1)] for j in range(8*n-1, 0, -8)]

>>> i = byte_array(4)
>>> next(i)
[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]
>>> next(i)
[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1]]

Or if you don't want them grouped it's simpler:

[[i>>j&1 for j in range(8*n-1, -1, -1)] for i in range(2**(8*n))]

Equivalent generator:

def byte_array(n):
    for i in range(2**(8*n)):
        yield [i>>j&1 for j in range(8*n-1, -1, -1)]

edited May 23, 2017 at 12:25

CommunityBot

11 silver badge

answered Apr 29, 2013 at 6:22

jamylak

134k30 gold badges238 silver badges240 bronze badges

1 Comment

Martin V. Over a year ago

Great job, a can learn a lot from your code. I am working on one crypto challenge and in few tasks i need to iterate very narrow intervals of bytearrays (grouped) so i was wondering about more general case - "how to iterate all combinations...". I know it would take almost ethernity to iterate one by one :)

Collectives™ on Stack Overflow

Python : efficient bytearray incrementation

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related