# A "triangular" data structure for commutative relationships

A multiplication table is symmetric over a diagonal, so only about $n^2/2$ of the elements in an $n \times n$ multiplication table contain unique information. Same goes for addition tables. In fact, the same is true for any table that represents a commutative relationship. Is there a data structure that can take advantage of commutativity to avoid storing redundant values?

Some languages, such as C, support ragged arrays: two-dimensional arrays where the rows have different lengths. That lets you avoid the redundancy of representing a symmetric function in a square array.

• Just wondering: that seems OK when you have e few rows, but can you actually nicely specify that the rows are of lengths, say, 1,2,3, ..., 1000? Jul 4 '14 at 22:37
• Sure. In C, you'd do it by allocating the rows individually using a for loop, rather than statically defining it the way you would for a rectangular m-by-n array. Jul 4 '14 at 22:40

Sure, you can put all information (of half a table) in a linear array, and use a formula to compute the new position given the original arguments. That formula is quadratic, and you are basically changing space for speed.

The best thing to do however is looking for two tables that are symmetric (commutative operations) and of the same size, and share the space.

• Personally, I think use formula to map 2-D position to 1-D position is better than sharing table. Especially when the 2 commutative function you're storing have different diagonals. Jul 5 '14 at 13:34
• If you use your formula to map 2-D position to 1-D position, what is the cost in access time, and what is the code size for one access, compared to standard accessing of a $n\times n$ array. cc @Billiska Jul 5 '14 at 14:37
• @babou I am about to post an example of that mapping as another answer. It's kind of f(x,y) = ((y+1)*(y))/2 + x which is so small a formula. It's almost the same as when you are accessing 2D array in some implementation, the command a[x][y] is actually translated to a[x*row_size + y]. Jul 5 '14 at 14:54

I want to expand on the other answers and give a concrete example of the 2-D index map to 1-D index.

Let $N = \{0,1,2,3,...\}$. Call our one-to-one map $f \colon N \times N \rightarrow N$.

First, let us list out some desirable properties $f$ should have.

1. $f$ is commutative. We want [x][y] and [y][x] to use same position in memory.
2. Small index maps to small index.
3. Since $f$ is a bijection to $N$, it gives an ordering to $N \times N$. We want this ordering to be meaningful. Say, order by the sum. If sum is equal, order by the larger element.
4. There is no gap in the index mapped, all destination index are used.

Or more mathematically:

1. $f(x,y) = f(y,x)$
2. If $x+y < a+b$ then $f(x,y) < f(a,b)$
3. If $x+y = a+b$, $x<y$, $a<b$ and $y<b$ then $f(x,y) < f(a,b)$
4. If $f(x,y) = k$ then $\exists x',y'. f(x',y') = k+1$
5. $f(0,0) = 0$

Here is an implementation in Python:

def f(x,y):
if x > y:
x,y = y,x
return ((y+1)*(y))/2 + x


Test run:

for y in range(5):
for x in range(y+1):
print (x,y),'->',f(x,y)


gives:

(0, 0) -> 0
(0, 1) -> 1
(1, 1) -> 2
(0, 2) -> 3
(1, 2) -> 4
(2, 2) -> 5
(0, 3) -> 6
(1, 3) -> 7
(2, 3) -> 8
(3, 3) -> 9
(0, 4) -> 10
(1, 4) -> 11
(2, 4) -> 12
(3, 4) -> 13
(4, 4) -> 14


## Let us show how this saves space:

First we consider the data storage space. Let $n$ be the largest index to be accessed.

If I use $n \times n$ array to store the commutative function, it would need $n^2$ units of space.

If I use 1 dimensional array to store the same data with this index mapping scheme, it would need $\frac{n(n+1)}{2}$ units of space.

Hence the data storage space saved is: $n^2 - \frac{n(n+1)}{2} = \frac{n(n-1)}{2} = O(n^2)$.

The increase in code storage size is $O(1)$ and can be overshadowed by the saving in data storage space. The increase in processing time is also $O(1)$ per access.

• I have no doubt one can do it. I did something similar in the exemple cited in my answer. But my question is about the cost in code size in the machine. This is intended to save space. Does it really? What should various parameters be so that it does? How many "commutative relationships" are actually to be represented in the application? How large are they? How many occurences of an access are to be found in the code of the application? How often are they executed? How much space is taken by the access code for your implementation, and when using standard arrays? Jul 5 '14 at 15:13
• I thought we are more concerned about the data storage size, than the code storage size. Data size can grows to million, but code size is just that 4 more lines I wrote. Each time you access the array, just call a[f(x,y)] instead of a[x,y]. Or better yet, if I just let the function f returns the value in a directly, you can just call f(x,y) which uses 1 less character than a[x][y]. For an example of commutative relationship, try the 'friend' relationship of social network. Jul 5 '14 at 15:18
• The question was about commutative relationships. I have no idea how many will be used in the program. I am not saying that your proposal is wrong, but only asking when it is profitable to do so. Many users are beginners, and I do not assume they realize that some savings are expensive. Also I am not worried about source code size, but about compiled code. And that depends also on the programming language. If you consider the "friend" relationship of social networks, it is very big, but very sparse (very low graph density) and will call for very different implementations. Jul 5 '14 at 20:37
• @babou Do I understand correctly that your only concern is just that my answer is not explicit enough for beginners? In that case I'm welcoming your edits. Jul 5 '14 at 21:02
– D.W.
Jul 6 '14 at 1:35

If you are willing to trade time for space, there are many ways to represent matrices (or other structures) satisfying specific constraints. Array of arrays, linked lists, etc. The choice of the representation also depends on what operations you intend to perform, with what frequency and statistics, either using the structure or modifying it (the most basic statement about data-structure choice). See for example this question (which I remember because I answered, and because the structure is unusual) : Algorithm: Dimension increase in 1D representation of Square Matrix.

Trading time for space, i.e. making some operations more costly in time in order to save space is not always a winning proposition. More complex access may mean more instructions inline every time the structure is accessed, which may sometimes make you lose more in code space than you gain in data space, while losing in time too.

Hence, if the dimension of you matrix remains small, and if you create few of them, it may be a wiser choice to simply waste the data space. Actually, it occasionally happens in some situations that one will chose to waste a bit of data space in order to simplify the code. One may even choose to waste a bit of space only to make the program more readable and easier to maintain.

• I don't think this answers the question. This answer is too open-ended. Sure, there are lots of other possible data structures one could consider, but how should we select from them? Are any of them suitable here? You don't say. Yes, in general trading time for space isn't always a win, but does that apply here? It's too hard to tell. (The answer, by the way, appears to be: "no, it doesn't apply here, at least not to the good answers suggested by others".) (cont.)
– D.W.
Jul 6 '14 at 1:39
• (...) I do agree with your last paragraph that sometimes we choose a non-optimal data structure to simplify the code, but that's not quite what the question is asking.
– D.W.
Jul 6 '14 at 1:40
• @D.W. This answer discusses the issues first: the question too open-ended? Then I do give an answer: just waste the space unless you can provide reasons to do otherwise. This should have appeared in comments before any answer. When I chipped in, there was already one answer accepted, and I had little choice. I did what I thought should have been done. The accepted answer in an interesting one, ... among a lot of others. But I have no reason to believe any is appropriate for the OP's problem. Skipping assumptions seems to be a frequent problem on technical SE sites. Jul 6 '14 at 21:40