title: Which algorithm can rationally reduce multiple lists? ("who killed who" pro​blem)
body: <p>I do not know if the problem I am talking about has a name, if that is the case, I would like to know it in order to do more research.</p>
  
  <p>To explain my problem, it is easier to visualize it.</p>
  
  <p>I will give a representation but many others have been possible.</p>
  
  <blockquote>
    <ul>
    <li>In a small town, the police found a large number of corpses.</li>
    <li>For each corpse found, there is a number of suspects among the inhabitants of
    the city. </li>
    <li>A murderer can not kill more than one person.</li>
    <li>There is a solution.
    <br><br><strong>Find out who killed who</strong>!</li>
    </ul>
  </blockquote>
  
  <p>As I write this, I realize that there may have many variants of this problem, so it would be really useful to know what kind of problem it is.</p>
  
  <hr>
  
  <p>I will use a test game.<br>
  So for each corpse, we have a set of suspect among the inhabitants.</p>
  
  <pre><code>C1 -&gt; [S1, S3]
  C2 -&gt; [S1, S3, S4]
  C3 -&gt; [S2]
  C4 -&gt; [S2, S3]
  </code></pre>
  
  <p>By logical deduction, it is then easy to determine who killed who.</p>
  
  <ol>
  <li>There is only one suspect for C3, so, S2 is the murderer.</li>
  <li>S2 is the murderer of C3, so he can not be the murderer of C4. This means that S2 killed C4.</li>
  <li>S1 is the latest potential suspect for C1, so he is the murderer.</li>
  <li>Finally, S4 is the murderer of C2.</li>
  </ol>
  
  <p>Which gives us the solution:</p>
  
  <pre><code>C1 -&gt; S1
  C2 -&gt; S4
  C3 -&gt; S2
  C4 -&gt; S3
  </code></pre>
  
  <p>A naive implementation of the algorithm to solve this would be:</p>
  
  <pre><code>found = []
  
  for corpse in corpses:
      corpse.suspects = [s for s in corpse.suspsects if s not in found]
      if len(corpse.suspects) == 1:
          found.append(suspects[0])
          continue # Restart the loop to remove the new killer found 
                   # from previous corpses suspects
  </code></pre>
  
  <p>The problem is that it becomes very expensive with a large number of bodies and suspects, the loop takes a long time. Of course, small improvements are possible (remove the body from the list once the suspect found, for example) but the algorithm seems to me still not optimal.</p>
  
  <p>Is there a better algorithm for this problem?
  And I repeat again, is it a specific name for this kind of problem? It could definitely help me a lot.</p>