lnNoam lnNoam - 2 months ago 9
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

  2. Padraic Cunningham:
    %%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


Answer
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)
Comments