lnNoam - 1 year ago 46

Python Question

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`

`f`

`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`

`b, c, d`

`b`

`a, c, d, e, f`

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

`for`

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)

Times:

- mine: -->
`%%timeit -r 10`

`10000 loops, best of 10: 19 µs per loop`

- Padraic Cunningham: -->
`%%timeit -r 10`

`100000 loops, best of 10:`

4.89 µs per loop - zvone: -->
`%%timeit -r 10`

`100000 loops, best of 10: 3.88 µs per`

loop - pneumatics: -->
`%%timeit -r 10`

`10000 loops, best of 10: 33.5 µs per loop`

Answer Source

```
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)
```