lnNoam - 1 year ago 66
Python Question

# Procedure to map all relationships between elements in a list of lists

I'm looking for an algorithm that can map all the relationships between all of the elements in sublists belonging to a list of length

`n`
.

More concretely, suppose
`a`
,
`b`
,
`c`
,
`d`
,
`e`
and
`f`
are the names of workers and that each sublist represents a 'shift' that occurred yesterday. I'd like to know, for each worker, who worked with who yesterday.

``````shifts_yesterday = [[a, b, c, d], [b, c, e, f]]
``````

Goal:

``````a: b, c, d
b: a, c, d, e, f
c: a, b, d, e, f
d: a, b, c
e: b, c, f
f: b, c, e
``````

Above, I can see that
`a`
worked with
`b, c, d`
yesterday;
`b`
worked with
`a, c, d, e, f`
yesterday, etc.

Time complexity is a concern here as I have a large list to process.
Though, intuitively, I suspect there is a pretty high floor on this one...

Note: I can obviously write a linear search slow approach with some
`for`
loops, but that is (a) not very clever (b) very slow.

### Edit:

Here's (a messy) attempt:

``````shifts = [['a', 'b', 'c', 'd'], ['b', 'c', 'e', 'f']]
workers = [i for s in shifts for i in s]

import collections
d = collections.defaultdict(list)

for w in workers:
for s in shifts:
for i in s:
if i != w and w in s:
if w in d.keys():
if i not in d[w]:
d[w].append(i)
else:
d[w].append(i)

# Test
for k, v in collections.OrderedDict(sorted(d.items())).items():
print(k, v)
``````

### Edit 2:

Times:

1. mine:
`%%timeit -r 10`
-->
`10000 loops, best of 10: 19 µs per loop`

`%%timeit -r 10`
-->
```100000 loops, best of 10: 4.89 µs per loop```

3. zvone:
`%%timeit -r 10`
-->
```100000 loops, best of 10: 3.88 µs per loop```

4. pneumatics:
`%%timeit -r 10`
-->
`10000 loops, best of 10: 33.5 µs per loop`

``````result = defaultdict(set)

for shift in shifts:
for worker in shift:
result[worker].update(shift)

# now, result[a] contains: a, b, c, d - so remove the a

for k, v in result.iteritems():
v.remove(k)
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download