## List manipulation in Python

``````

In [1]:

[1,3,5] + [ 3,4,1]

``````
``````

Out[1]:

[1, 3, 5, 3, 4, 1]

``````
``````

In [2]:

range(10)

``````
``````

Out[2]:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

``````
``````

In [3]:

l = [3,1,4]

``````
``````

In [4]:

[i^2 for i in range(11)]

``````
``````

Out[4]:

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

``````
``````

In [ ]:

``````

# Binary words of a given length

## List of binary words, recursive version

``````

In [5]:

def Bn(n):
if n == 0:
return [[]]
else:
return [[0]+u for u in Bn(n-1)] + [[1]+u for u in Bn(n-1)]

``````
``````

In [6]:

Bn(4)

``````
``````

Out[6]:

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

``````
``````

In [ ]:

``````

## List of binary words, base 2 version

Here I'm using Sagemath's `Integer` class who has a digit method. The argument `padto` complete with zero's. The returned list starts with the lowest significant bits.

``````

In [7]:

``````
``````

Out[7]:

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

``````
``````

In [8]:

def binary(n):
l = [None]*2^n
for i in range(2^n):
return l

``````
``````

In [9]:

binary(4)

``````
``````

Out[9]:

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

``````
``````

In [ ]:

``````
``````

In [ ]:

``````

## Iterator fo binary words

``````

In [4]:

class binaryIter():
def __init__(self, n):
self._n = n
self._2n = 2^n
self._i = 0
def __iter__(self):
return self
def next(self):
if self._i == self._2n:
raise StopIteration
self._i += 1
return res

``````
``````

In [5]:

it = iter(binaryIter(3))

``````
``````

In [6]:

it.next()

``````
``````

Out[6]:

[0, 0, 0]

``````
``````

In [7]:

list(binaryIter(3))

``````
``````

Out[7]:

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

``````
``````

In [5]:

it = binaryIter(100)

``````
``````

In [8]:

it.next()

``````
``````

Out[8]:

[0,
1,
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,
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,
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,
0,
0]

``````
``````

In [ ]:

``````
``````

In [ ]:

``````
``````

In [ ]:

``````
``````

In [ ]:

``````

## Generator using the yield keyword

``````

In [14]:

def binaryIterYield(n):
for i in range(2^n):

``````
``````

In [15]:

it = iter(binaryIterYield(4))

``````
``````

In [16]:

it.next()

``````
``````

Out[16]:

[0, 0, 0, 0]

``````
``````

In [ ]:

``````
``````

In [17]:

list(binaryIterYield(4))

``````
``````

Out[17]:

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

``````
``````

In [ ]:

``````

## Iteration using Gray code

``````

In [18]:

class binaryIterGray(object):
def __init__(self, n):
self._n = n
self._g = [0]*n
self._t = range(n+1)
def __iter__(self):
return self
def next(self):
i = self._t[0]
if i == self._n:
raise StopIteration
self._g[i] = 1-self._g[i]
self._t[0] = 0
self._t[i] = self._t[i+1]
self._t[i+1] = i+1
def get(self):
return self._g

``````

### Beware, you need to copy the list

``````

In [19]:

def listGrayBug(n):
it = binaryIterGray(n)
res = [it.get()]
for _ in it:
res.append(it.get())
return res

``````
``````

In [20]:

listGrayBug(3)

``````
``````

Out[20]:

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

``````
``````

In [ ]:

``````

### The correct version

``````

In [21]:

def listGray(n):
it = binaryIterGray(n)
res = [list(it.get())]
for _ in it:
res.append(list(it.get()))
return res

``````
``````

In [22]:

listGray(3)

``````
``````

Out[22]:

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

``````
``````

In [ ]:

``````

### Iteration using gray code, instrumented version

``````

In [23]:

class binaryIterGrayInst(object):
def __init__(self, n):
self._n = n
self._g = [0]*n
self._t = range(n+1)
self._c = 0
def __iter__(self):
return self
def next(self):
i = self._t[0]

print self._c.digits(2, padto=self._n)[::-1], self._t[::-1], i, self._g[::-1]

if i == self._n:
raise StopIteration

self._c += 1

self._g[i] = 1-self._g[i]
self._t[0] = 0
self._t[i] = self._t[i+1]
self._t[i+1] = i+1

def get(self):
return self._g

``````
``````

In [24]:

l = list(binaryIterGrayInst(4))

``````
``````

[0, 0, 0, 0] [4, 3, 2, 1, 0] 0 [0, 0, 0, 0]
[0, 0, 0, 1] [4, 3, 2, 1, 1] 1 [0, 0, 0, 1]
[0, 0, 1, 0] [4, 3, 2, 2, 0] 0 [0, 0, 1, 1]
[0, 0, 1, 1] [4, 3, 2, 1, 2] 2 [0, 0, 1, 0]
[0, 1, 0, 0] [4, 3, 3, 1, 0] 0 [0, 1, 1, 0]
[0, 1, 0, 1] [4, 3, 3, 1, 1] 1 [0, 1, 1, 1]
[0, 1, 1, 0] [4, 3, 2, 3, 0] 0 [0, 1, 0, 1]
[0, 1, 1, 1] [4, 3, 2, 1, 3] 3 [0, 1, 0, 0]
[1, 0, 0, 0] [4, 4, 2, 1, 0] 0 [1, 1, 0, 0]
[1, 0, 0, 1] [4, 4, 2, 1, 1] 1 [1, 1, 0, 1]
[1, 0, 1, 0] [4, 4, 2, 2, 0] 0 [1, 1, 1, 1]
[1, 0, 1, 1] [4, 4, 2, 1, 2] 2 [1, 1, 1, 0]
[1, 1, 0, 0] [4, 3, 4, 1, 0] 0 [1, 0, 1, 0]
[1, 1, 0, 1] [4, 3, 4, 1, 1] 1 [1, 0, 1, 1]
[1, 1, 1, 0] [4, 3, 2, 4, 0] 0 [1, 0, 0, 1]
[1, 1, 1, 1] [4, 3, 2, 1, 4] 4 [1, 0, 0, 0]

``````
``````

In [ ]:

``````

# Binary words of a given length and number of one

## Recursive version

``````

In [10]:

def Bnk(n, k):
if k == 0:
return [[0]*n]
if k == n:
return [[1]*n]
else:
return [[0]+u for u in Bnk(n-1, k)] + [[1]+u for u in Bnk(n-1, k-1)]

``````
``````

In [17]:

l = Bnk(5,3)
l

``````
``````

Out[17]:

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

``````
``````

In [ ]:

``````

## Unrank

``````

In [12]:

def unrankBnk(n,k,i):
if i >= binomial(n,k):
raise ValueError
if n == 0:
return []
if i < binomial(n-1, k):
return [0]+unrankBnk(n-1, k, i)
else:
return [1]+unrankBnk(n-1, k-1, i-binomial(n-1, k))

``````
``````

In [16]:

unrankBnk(5, 5, 0)

``````
``````

Out[16]:

[1, 1, 1, 1, 1]

``````
``````

In [ ]:

``````
``````

In [ ]:

``````
``````

In [ ]:

``````
``````

In [28]:

def unrankBnk(n,k,i):
if i >= binomial(n,k):
raise ValueError
if k == 0:
return [0]*n
if k == n:
return [1]*n
if i < binomial(n-1, k):
return [0]+unrankBnk(n-1, k, i)
else:
return [1]+unrankBnk(n-1, k-1, i-binomial(n-1, k))

``````
``````

In [18]:

all(unrankBnk(5,3, i) == l[i] for i in range(len(l)))

``````
``````

Out[18]:

True

``````
``````

In [30]:

l[5]

``````
``````

Out[30]:

[1, 0, 1, 0, 1]

``````
``````

In [ ]:

``````
``````

In [31]:

binomial(100, 50), 2^64

``````
``````

Out[31]:

(100891344545564193334812497256, 18446744073709551616)

``````
``````

In [20]:

unrankBnk(100, 50, 100891344545564193334812197256)

``````
``````

Out[20]:

[1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
1,
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,
0,
0,
0,
0,
0,
1,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0,
0,
1,
0,
0,
0,
0,
0,
0,
0,
0]

``````
``````

In [ ]:

``````

## Next using a backtracking algorithm

``````

In [32]:

def nextBin(l):
i = 0
while i < len(l) and l[i] == 1:
l[i] = 0
i += 1
if i == len(l):
raise ValueError
else:
l[i] = 1

``````
``````

In [33]:

l = [1,1,0,1,1]

``````
``````

In [34]:

nextBin(l)

``````
``````

In [35]:

l

``````
``````

Out[35]:

[0, 0, 1, 1, 1]

``````

## List using first/next

``````

In [36]:

def listBin(n):
l = [0]*n
res = [list(l)]
try:
while True:
nextBin(l)
res.append(list(l))
except ValueError:
pass
return res

``````
``````

In [37]:

listBin(4)

``````
``````

Out[37]:

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

``````
``````

In [ ]:

``````
``````

In [38]:

binomial(4,2)

``````
``````

Out[38]:

6

``````
``````

In [39]:

[ factorial(2*N)/factorial(N)/factorial(N+1) for N in range(20) ]

``````
``````

Out[39]:

[1,
1,
2,
5,
14,
42,
132,
429,
1430,
4862,
16796,
58786,
208012,
742900,
2674440,
9694845,
35357670,
129644790,
477638700,
1767263190]

``````
``````

In [ ]:

``````