HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

A "triangular" data structure for commutative relationships

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
commutativeforstructurerelationshipsdatatriangular

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#28221, answer score: 8

Revisions (0)

No revisions yet.