Two simple examples¶
Description: Indexing problem and its inverse, base-N number conversion
Example 1¶
Code up a function to convert $ (i,j) $ index in a two-dimensional array into a single index $ k $ which swipes the matrix by column. Also code up the inverse of this function.
In [ ]:
# code here
In [27]:
def k(i,j,m,base0=True):
'''Convert (i,j) indexes in a two-dimensional array
with m rows into a single index computed column-wise
'''
if base0:
return j*m + i
else:
return (j-1)*m + i
def ik(k,m,base0=True):
'''Convert k index in a two-dimensional array
with m rows into a pair of (i,j) indexes
'''
if base0:
j = k//m
i = k%m
else:
j = k//m + 1
i = k%m
return i,j
m=5
for i in range(5):
for j in range(10):
k0 = k(i,j,m)
i1,j1 = ik(k0,m)
print('(%d,%d) --> %d --> (%d,%d)'%(i,j,k0,i1,j1))
(0,0) --> 0 --> (0,0) (0,1) --> 5 --> (0,1) (0,2) --> 10 --> (0,2) (0,3) --> 15 --> (0,3) (0,4) --> 20 --> (0,4) (0,5) --> 25 --> (0,5) (0,6) --> 30 --> (0,6) (0,7) --> 35 --> (0,7) (0,8) --> 40 --> (0,8) (0,9) --> 45 --> (0,9) (1,0) --> 1 --> (1,0) (1,1) --> 6 --> (1,1) (1,2) --> 11 --> (1,2) (1,3) --> 16 --> (1,3) (1,4) --> 21 --> (1,4) (1,5) --> 26 --> (1,5) (1,6) --> 31 --> (1,6) (1,7) --> 36 --> (1,7) (1,8) --> 41 --> (1,8) (1,9) --> 46 --> (1,9) (2,0) --> 2 --> (2,0) (2,1) --> 7 --> (2,1) (2,2) --> 12 --> (2,2) (2,3) --> 17 --> (2,3) (2,4) --> 22 --> (2,4) (2,5) --> 27 --> (2,5) (2,6) --> 32 --> (2,6) (2,7) --> 37 --> (2,7) (2,8) --> 42 --> (2,8) (2,9) --> 47 --> (2,9) (3,0) --> 3 --> (3,0) (3,1) --> 8 --> (3,1) (3,2) --> 13 --> (3,2) (3,3) --> 18 --> (3,3) (3,4) --> 23 --> (3,4) (3,5) --> 28 --> (3,5) (3,6) --> 33 --> (3,6) (3,7) --> 38 --> (3,7) (3,8) --> 43 --> (3,8) (3,9) --> 48 --> (3,9) (4,0) --> 4 --> (4,0) (4,1) --> 9 --> (4,1) (4,2) --> 14 --> (4,2) (4,3) --> 19 --> (4,3) (4,4) --> 24 --> (4,4) (4,5) --> 29 --> (4,5) (4,6) --> 34 --> (4,6) (4,7) --> 39 --> (4,7) (4,8) --> 44 --> (4,8) (4,9) --> 49 --> (4,9)
In [28]:
# Running the check for base1 reveals the bug when i=5!
m=5
for i in range(1,m+1):
for j in range(1,11):
k0 = k(i,j,m,base0=False)
i1,j1 = ik(k0,m,base0=False)
print('(%d,%d) --> %d --> (%d,%d)'%(i,j,k0,i1,j1))
# So, the correct inverse conversion in base1 should be:
def ik(k,m,base0=True):
'''Convert k index in a two-dimensional array
with m rows into a pair of (i,j) indexes
'''
if base0:
j = k//m
i = k%m
else:
j = (k-1)//m + 1
i = (k-1)%m + 1
return i,j
(1,1) --> 1 --> (1,1) (1,2) --> 6 --> (1,2) (1,3) --> 11 --> (1,3) (1,4) --> 16 --> (1,4) (1,5) --> 21 --> (1,5) (1,6) --> 26 --> (1,6) (1,7) --> 31 --> (1,7) (1,8) --> 36 --> (1,8) (1,9) --> 41 --> (1,9) (1,10) --> 46 --> (1,10) (2,1) --> 2 --> (2,1) (2,2) --> 7 --> (2,2) (2,3) --> 12 --> (2,3) (2,4) --> 17 --> (2,4) (2,5) --> 22 --> (2,5) (2,6) --> 27 --> (2,6) (2,7) --> 32 --> (2,7) (2,8) --> 37 --> (2,8) (2,9) --> 42 --> (2,9) (2,10) --> 47 --> (2,10) (3,1) --> 3 --> (3,1) (3,2) --> 8 --> (3,2) (3,3) --> 13 --> (3,3) (3,4) --> 18 --> (3,4) (3,5) --> 23 --> (3,5) (3,6) --> 28 --> (3,6) (3,7) --> 33 --> (3,7) (3,8) --> 38 --> (3,8) (3,9) --> 43 --> (3,9) (3,10) --> 48 --> (3,10) (4,1) --> 4 --> (4,1) (4,2) --> 9 --> (4,2) (4,3) --> 14 --> (4,3) (4,4) --> 19 --> (4,4) (4,5) --> 24 --> (4,5) (4,6) --> 29 --> (4,6) (4,7) --> 34 --> (4,7) (4,8) --> 39 --> (4,8) (4,9) --> 44 --> (4,9) (4,10) --> 49 --> (4,10) (5,1) --> 5 --> (0,2) (5,2) --> 10 --> (0,3) (5,3) --> 15 --> (0,4) (5,4) --> 20 --> (0,5) (5,5) --> 25 --> (0,6) (5,6) --> 30 --> (0,7) (5,7) --> 35 --> (0,8) (5,8) --> 40 --> (0,9) (5,9) --> 45 --> (0,10) (5,10) --> 50 --> (0,11)
In [29]:
m=5
for i in range(1,m+1):
for j in range(1,5):
k0 = k(i,j,m,base0=False)
i1,j1 = ik(k0,m,base0=False)
print('(%d,%d) --> %d --> (%d,%d)'%(i,j,k0,i1,j1))
(1,1) --> 1 --> (1,1) (1,2) --> 6 --> (1,2) (1,3) --> 11 --> (1,3) (1,4) --> 16 --> (1,4) (2,1) --> 2 --> (2,1) (2,2) --> 7 --> (2,2) (2,3) --> 12 --> (2,3) (2,4) --> 17 --> (2,4) (3,1) --> 3 --> (3,1) (3,2) --> 8 --> (3,2) (3,3) --> 13 --> (3,3) (3,4) --> 18 --> (3,4) (4,1) --> 4 --> (4,1) (4,2) --> 9 --> (4,2) (4,3) --> 14 --> (4,3) (4,4) --> 19 --> (4,4) (5,1) --> 5 --> (5,1) (5,2) --> 10 --> (5,2) (5,3) --> 15 --> (5,3) (5,4) --> 20 --> (5,4)
Example 2¶
Write a function to converter a decimal number into a given base. Return the result as string.
In [ ]:
# code here
In [ ]:
def baseN(x,base=2):
'''Converts given number to given base'''
digits = [str(i) for i in range(10)] + [chr(i) for i in range(97,123)]
assert 2 <= base <= len(digits),'Number base must be between 2 and %d'%(len(digits))
if x == 0:
return '0'
out = []
while x>0:
i = x%base
out.append(digits[i])
x = x//base
return ''.join(out[::-1])
for n in [3,8,35,574,1023523,9999]:
for b in range(36,1,-4):
print('%d in base %d is %s' % (n,b,baseN(n,b)))
print()