N-Dimensional matrix to 1-D array indexing translations.

Having done the 2-D address indexing translations, I thught about how to translate between a set of 3-D indices and a linear 1-D array index then extrapolated to n-dimensions.

I liked the idea of testing the solution and have brought that across too (with additions)

The class

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

# -*- coding: utf-8 -*- """ Created on Tue Aug 27 01:49:51 2019 @author: Paddy3118 """ from collections import OrderedDict from itertools import product from functools import reduce #%% class ND21D_Addressing(): """ Convert n-dimensional indexing to/from 1-D index as if packed into 1-D array. All indices assumed to start from zero """ def __init__(self, *extent): "extent is tuple of index sizes in each dimension" n_dim = len(extent) # Dimensionality self._extent = extent self._offsets = [reduce(int.__mul__, extent[n + 1:], 1) for n in range(n_dim)] # What n-dimensional index-tuple is stored at linear index. def i2ndim(self, index_i): "1-D array index to to n-D tuple of indices" return tuple((index_i // s) % c for s, c in zip(self._offsets, self._extent)) # What linear 1-D index stores n-D tuple of indices. def ndim2i(self, ni): "n-D tuple of indices to 1-D array index" return sum(d * s for s, d in zip(self._offsets, ni)) def __repr__(self): return f"{self.__class__.__name__}({str(self._extent)[1:-1]})" #%%

The test

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

def _irange(mini, maxi): "Integer range mini-to-maxi inclusive of _both_ endpoints" # Some think ranges should include _both_ endpoints, oh well. return range(mini, maxi+1) def _print_n_dim(ranges_from_zero): "Represent the indexing of an n-D matrix" last = [0] * len(ranges_from_zero) for ni in product(*ranges_from_zero): for s, t in zip(last, ni): if s != t and t == 0: print() last = ni print(str(ni).replace(' ', ''), end=' ') print() #%% if __name__ == "__main__": # Dimensionality for test n_dim = 4 # range of values in each dimension. dranges = [_irange(0, d+1) for d in range(n_dim)] # Num of values in each dim. extent = [len(dr) for dr in dranges] ## The address mapper instance admap = ND21D_Addressing(*extent) ## A test matrix of given dimensionality # Optimum size of mapping to 1-dim. array size_1d = reduce(int.__mul__, extent) # Range of all mapped to 1-dim. array index values range_1d = _irange(0, size_1d - 1) print(f"\n## ORIGINAL {n_dim}-D ARRAY:") _print_n_dim(dranges) print(f"\n# TEST TRIAL MAP {n_dim}-D TO/FROM 1-D ARRAY ADDRESSING") # Representing a 1-D array mapped to n-D index tuple dim_1 = OrderedDict((index_i, admap.i2ndim(index_i)) for index_i in range_1d) all_ndim = set(dim_1.values()) all_by_dim = [set(d1) for d1 in zip(*all_ndim)] assert len(all_ndim) == size_1d, "FAIL! ndim index count" for a_dim, its_count in zip(all_by_dim, extent): assert len(set(a_dim)) == its_count, \ "FAIL! ndim individual index count" # Representing n-D index tuple mapped to 1-D index dim_n = OrderedDict(((ndim), admap.ndim2i(ndim)) for ndim in product(*dranges)) all_i = set(dim_n.values()) assert min(all_i) == 0, "FAIL! Min index_i not zero" assert max(all_i) == size_1d - 1, \ f"FAIL! Max index_i not {size_1d - 1}" # Check inverse mappings assert all(dim_1[dim_n[ndim]] == ndim for ndim in dim_n), \ "FAIL! Mapping n-D to/from 1-D indices" assert all(dim_n[dim_1[index_i]] == index_i for index_i in range_1d), \ "FAIL! Mapping 1-D to/from n-D indices" print(f" {admap}: PASS!")

The test output

## ORIGINAL 4-D ARRAY:
(0,0,0,0) (0,0,0,1) (0,0,0,2) (0,0,0,3) (0,0,0,4) 
(0,0,1,0) (0,0,1,1) (0,0,1,2) (0,0,1,3) (0,0,1,4) 
(0,0,2,0) (0,0,2,1) (0,0,2,2) (0,0,2,3) (0,0,2,4) 
(0,0,3,0) (0,0,3,1) (0,0,3,2) (0,0,3,3) (0,0,3,4) 

(0,1,0,0) (0,1,0,1) (0,1,0,2) (0,1,0,3) (0,1,0,4) 
(0,1,1,0) (0,1,1,1) (0,1,1,2) (0,1,1,3) (0,1,1,4) 
(0,1,2,0) (0,1,2,1) (0,1,2,2) (0,1,2,3) (0,1,2,4) 
(0,1,3,0) (0,1,3,1) (0,1,3,2) (0,1,3,3) (0,1,3,4) 

(0,2,0,0) (0,2,0,1) (0,2,0,2) (0,2,0,3) (0,2,0,4) 
(0,2,1,0) (0,2,1,1) (0,2,1,2) (0,2,1,3) (0,2,1,4) 
(0,2,2,0) (0,2,2,1) (0,2,2,2) (0,2,2,3) (0,2,2,4) 
(0,2,3,0) (0,2,3,1) (0,2,3,2) (0,2,3,3) (0,2,3,4) 


(1,0,0,0) (1,0,0,1) (1,0,0,2) (1,0,0,3) (1,0,0,4) 
(1,0,1,0) (1,0,1,1) (1,0,1,2) (1,0,1,3) (1,0,1,4) 
(1,0,2,0) (1,0,2,1) (1,0,2,2) (1,0,2,3) (1,0,2,4) 
(1,0,3,0) (1,0,3,1) (1,0,3,2) (1,0,3,3) (1,0,3,4) 

(1,1,0,0) (1,1,0,1) (1,1,0,2) (1,1,0,3) (1,1,0,4) 
(1,1,1,0) (1,1,1,1) (1,1,1,2) (1,1,1,3) (1,1,1,4) 
(1,1,2,0) (1,1,2,1) (1,1,2,2) (1,1,2,3) (1,1,2,4) 
(1,1,3,0) (1,1,3,1) (1,1,3,2) (1,1,3,3) (1,1,3,4) 

(1,2,0,0) (1,2,0,1) (1,2,0,2) (1,2,0,3) (1,2,0,4) 
(1,2,1,0) (1,2,1,1) (1,2,1,2) (1,2,1,3) (1,2,1,4) 
(1,2,2,0) (1,2,2,1) (1,2,2,2) (1,2,2,3) (1,2,2,4) 
(1,2,3,0) (1,2,3,1) (1,2,3,2) (1,2,3,3) (1,2,3,4) 

# TEST TRIAL MAP 4-D TO/FROM 1-D ARRAY ADDRESSING
  ND21D_Addressing(2, 3, 4, 5): PASS!

END.

2-Dimension matrix to 1-D array, index translations.

Work has me working with hardware registers. Many registers; arrayed registers; multi-arrayed registers!.

The verifiction library I use has code to handle 1-D arrays of registers but not for 2-d (matrix) of registers - which is the problem I have today.

Problem Statement

A useful description of the problem is:
Given a 2-D matrix of values to store and access in a system that allows the storingof 1-D arrays of values, how do you map from the 2-D x,y indices to the 1-D i index - and vice-versa?

Partial memory

It's several decades since I first looked into this but I do remember divmod! Divmod was a part of the solution: divmod(x, y) returns (x // y, x % y) i.e the integer divisor and the integer remainder of x and y, as a tuple.

Rather than "do the math" to work out the correct functions needed to generate a 1-D array index i, from two matrix indices x and y - as well as the reverse function - I decided to take a suck-it-and-see approach. I had ideas that contain the correct solution and devised tests to reject faulty implementations.

Setup

1. Indices in any dimension count up from zero.
2. Use a different maximum index in each matrix dimension to aid later checks
3. I created function irange (line 14+), as sometimes people like to generate integer ranges that include both endpoints.

1-D to 2-D

Variable i_to_xy_list on lines 35+, has the source for four functions alternatives that when given a 1-D index generate a tuple of index numbers representing x and y. All four use divmod.

To test them I create a python function from the text using eval in line 50 then, knowing that if the matrix has three possible x values and four possible y values and so indexes exactly 3*4 = 24 values, I use a range of 1-D index of 0-to-23 inclsive to hold the corresponding x,y tuples generated, in the (oredered) dict dim_1 in line 52.
Sets all_xy, all_x, and all_y (lines54-56), accumulate the different indexing number-pairs and numbers seen in all/each dimension of the matrix indexing generated from this function i2xy. They are then tested to ensure they have the expected number and range of individual indeces
 in lines 57-68.

2-D to 1-D

Similarly xy_to_i_list has four possible ways that could match-up with a passing 1-D to 2-D fnction to do the reverse conversion from x,y coords to linear array index i.
all permutations of the range of x and y index values are used to generate sample 1-D indeces in dict dim_n (line 73), then the generated 1-D indices are checked (line 76+)

The last check, from line 86, checks that the i2xy function and xy2i functions are inverses of each other, generating and decoding the same indeces.

The output

## ORIGINAL 2-D ARRAY:
0,0 0,1 0,2 0,3
1,0 1,1 1,2 1,3
2,0 2,1 2,2 2,3

  # TRIAL MAPPINGS TO 1-D ARRAY
  FAIL! x count from `x, y = (lambda index_i: divmod(index_i, xcount))(index_i)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x * xcount + y)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x + y * ycount)(x, y)`
  FAIL! Mapping index_i to/from x, y using `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x * xcount + y)(x, y)`
  FAIL! Mapping index_i to/from x, y using `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  FAIL! Max index_i not 11 in `index_i = (lambda x, y: x + y * ycount)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`
  FAIL! x count from `x, y = (lambda index_i: divmod(index_i, ycount)[::-1])(index_i)`

# SUMMARY
  PASS! `x, y = (lambda index_i: divmod(index_i, ycount))(index_i); index_i = (lambda x, y: x * ycount + y)(x, y)`
  PASS! `x, y = (lambda index_i: divmod(index_i, xcount)[::-1])(index_i); index_i = (lambda x, y: x + y * xcount)(x, y)`

Or to rewrite the lambdas as functions:

# These two:
def i2xy(i):
    return divmod(i, ycount)
def xy2i(x, y):
    return x * ycount + y
# Or these two:
def i2xy(i):
    return reversed(divmod(i, xcount))
def xy2i(x, y):
    return x + y * xcount

Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

# -*- coding: utf-8 -*- """ Created on Sat Aug 24 21:31:03 2019 @author: Paddy3118 """ from collections import OrderedDict from itertools import product from pprint import pprint as pp #%% def irange(mini, maxi): "Integer range mini-to-maxi inclusive of _both_ endpoints" # Some think ranges should include _both_ endpoints, oh well. return range(mini, maxi+1) #%% xrange = irange(0, 2) yrange = irange(0, 3) xcount = len(xrange) # 3 ycount = len(yrange) # 4 print("\n## ORIGINAL 2-D ARRAY:") for x in xrange: print(' '.join(f"{x},{y}" for y in yrange)) #%% print("\n # TRIAL MAPPINGS TO 1-D ARRAY") print_on_fail, print_on_pass = False, False # Possible ways to get what n-dimensional index-tuple is stored at linear index i_to_xy_list = """ lambda index_i: divmod(index_i, xcount) lambda index_i: divmod(index_i, ycount) lambda index_i: divmod(index_i, xcount)[::-1] lambda index_i: divmod(index_i, ycount)[::-1] """.strip().split('\n') # Possible ways to generate a linear 1-D index from n-D tuple of indices xy_to_i_list = """ lambda x, y: x * xcount + y lambda x, y: x * ycount + y lambda x, y: x + y * ycount lambda x, y: x + y * xcount """.strip().split('\n') passes = [] for i_to_xy in i_to_xy_list: i2xy = eval(i_to_xy) # Representing a 1-D array as OrderedDict preserves insertion order dim_1 = OrderedDict((index_i, i2xy(index_i)) for index_i in irange(0, xcount*ycount - 1)) all_xy = set(dim_1.values()) all_x = set(x for x, y in dim_1.values()) all_y = set(y for x, y in dim_1.values()) if len(all_xy) != xcount * ycount: print(f" FAIL! x,y count from `x, y = ({i_to_xy})(index_i)`") if print_on_fail: pp(dim_1) continue if len(all_x) != xcount: print(f" FAIL! x count from `x, y = ({i_to_xy})(index_i)`") if print_on_fail: pp(dim_1) continue if len(all_y) != ycount: print(f" FAIL! y count from `x, y = ({i_to_xy})(index_i)`") if print_on_fail: pp(dim_1) continue # for xy_to_i in xy_to_i_list: xy2i = eval(xy_to_i) # Representing a N-D array dim_n = OrderedDict(((x, y), xy2i(x, y)) for x, y in product(xrange, yrange)) all_i = set(dim_n.values()) if min(all_i) != 0: print(f" FAIL! Min index_i not zero in " f"`index_i = ({xy_to_i})(x, y)`") if print_on_fail: pp(dim_n) continue if max(all_i) != xcount * ycount - 1: print(f" FAIL! Max index_i not {xcount * ycount - 1} in " f"`index_i = ({xy_to_i})(x, y)`") if print_on_fail: pp(dim_n) continue if not all(dim_1[dim_n[xy]] == xy for xy in dim_n): print(f" FAIL! Mapping index_i to/from x, y using " f"`x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`") if print_on_fail: pp(dim_1) if print_on_fail: pp(dim_n) continue passes.append((i_to_xy, xy_to_i)) print(f" PASS! `x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`") if print_on_pass: pp(dim_1) pp(dim_n) print('\n# SUMMARY') for i_to_xy, xy_to_i in passes: print(f" PASS! `x, y = ({i_to_xy})(index_i); index_i = ({xy_to_i})(x, y)`") #

Sharing Fairly (Thue Morse)