Procedure to map all relationships between elements in a list of lists
<p>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 <code>n</code>. </p>

<p>More concretely, suppose <code>a</code>, <code>b</code>, <code>c</code>, <code>d</code>, <code>e</code> and <code>f</code> 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.</p>

<pre><code>shifts_yesterday = [[a, b, c, d], [b, c, e, f]] 
</code></pre>

<p>Goal:</p>

<pre><code>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
</code></pre>

<p>Above, I can see that <code>a</code> worked with <code>b, c, d</code> yesterday; <code>b</code> worked with <code>a, c, d, e, f</code> yesterday, etc.</p>

<p>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...</p>

<p>Note: I can obviously write a <strike>linear search</strike> straightforward approach with only <code>for</code> loops, but that is (a) not very clever (b) very slow.</p>

<h3>Edit:</h3>

<p>Here's (a messy) attempt:</p>

<pre><code>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)
</code></pre>

<p>Test:</p>

<pre><code>for k, v in collections.OrderedDict(sorted(d.items())).items():
    print(k, v)
</code></pre>

<h3>Edit 2:</h3>

<p>Times:</p>

<ol>
<li><p>mine: <code>%%timeit -r 10</code> --> <code>10000 loops, best of 10: 19 Âµs per loop</code></p></li>
<li><p>Padraic Cunningham: <code>%%timeit -r 10</code> --> <code>100000 loops, best of 10:
4.89 Âµs per loop</code></p></li>
<li><p>zvone: <code>%%timeit -r 10</code> --> <code>100000 loops, best of 10: 3.88 Âµs per
loop</code></p></li>
<li><p>pneumatics: <code>%%timeit -r 10</code> --> <code>10000 loops, best of 10: 33.5 Âµs per loop</code></p></li>
</ol>

<p>I think you're looking for a set membership relationship. Let's call it <code>coworkers</code>:</p>

<pre><code>shifts_yesterday = [['a', 'b', 'c', 'd'], ['b', 'c', 'e', 'f']]

def coworkers(worker, shifts):
    coworkers = set()
    coworkers.update( *[shift for shift in shifts if worker in shift] )
    return coworkers
</code></pre>

<p>For each worker, you create a set of all the shifts that include the worker.</p>

<pre><code>everybody = set()
everybody.update( *shifts_yesterday )

for worker in everybody:
     print("{}: {}".format(worker, coworkers(worker, shifts_yesterday)))
</code></pre>

<p>The output is</p>

<pre><code>a: set(['a', 'c', 'b', 'd'])
c: set(['a', 'c', 'b', 'e', 'd', 'f'])
b: set(['a', 'c', 'b', 'e', 'd', 'f'])
e: set(['c', 'b', 'e', 'f'])
d: set(['a', 'c', 'b', 'd'])
f: set(['c', 'b', 'e', 'f'])
</code></pre>

python algorithm time-complexity