Data-structure for multiway associativity in Python

[Steven D'Aprano]

On Sun, 28 Jan 2018 14:48:02 -0800, qrious wrote:

> First list = { 1, 2, 3}
> Second list = { 4, 5, 6}
> Third list = { 7, 8, 9}
> 
> If I pass 9 as the argument, the return value of the function would be 
> {7, 8}.



subsets = [{1, 2, 3}, {4, 5, 6}, {7, 8, 9}]

data = {}
for subset in subsets:
    for key in subset:
        data[key] = subset

# At this point, your master data looks like this:
# 
# {1: {1, 2, 3},  2: {1, 2, 3},  3: {1, 2, 3},
#  4: {4, 5, 6},  5: {4, 5, 6},  6: {4, 5, 6}, 
#  7: {7, 8, 9},  8: {7, 8, 9},  9: {7, 8, 9}}
#
# but don't worry, that's not three COPIES of each set, just three
# references to the same one: each reference costs only a single
# pointer.

# Find a set associated with a key
subset = data[9]  # this is a lightning-fast lookup

# Get the items in the set, excluding the key itself
result = subset - {9}
assert result == {7, 8}

# Add a new data point to that set:
subset.add(10)
data[10] = subset

# Delete a data point:
del subset[9]
del data[9]



If you had started with a concrete example from the start, this would not 
have seemed like such a mysterious and difficult problem. Describing it 
as "multiway associativity" doesn't really help: as far as I can see, 
it's not multiway at all, it is just a straightforward case of one way 
associativity between each key and a set of values that contains that key.

Concrete examples are *really* useful for clarifying the requirements.



-- 
Steve