title: Grouping similar strings together from a list
body: <p>I've been struggling this morning with a problem at the office.</p>
  
  <p>I need to find a way to group strings together from a list. It's hard to explain so here's an example:</p>
  
  <p>Let's say I have a list as follow:</p>
  
  <pre class="lang-py prettyprint-override"><code>['MONTREAL EDUCATION BOARD', 'Île de Montréal', 'Montréal',
         'Ville de Montréal', 'MONTREAL CITY', 'Monrtéal', 'Mont-réal',
         'Toronto', 'Toronto city', 'Tornoto', 'What is this', 'Bananasplit',
         'Banana', 'StLouis', 'St-Louis', 'Saint Louis']
  </code></pre>
  
  <p>I need to find a way to group these values together depending on their similarity:</p>
  
  <pre class="lang-py prettyprint-override"><code>[['MONTREAL EDUCATION BOARD'],
   ['Île de Montréal', 'Montréal','Ville de Montréal', 'MONTREAL CITY', 'Monrtéal', 'Mont-réal'],
   ['Toronto', 'Toronto city', 'Tornoto'],
   ['anything'],
   ['Bananasplit', 'Banana'],
   ['StLouis', 'St-Louis', 'Saint Louis']
  ]
  </code></pre>
  
  <p>That would be the perfect case. Obviously it can have (and will) errors. I need to do this with around 10 000 lists which contains from 5 to 15 000 strings each. I need to minimize the error and get the best groups I can.</p>
  
  <p>I am using a slightly modified version of <code>fuzzywuzzy</code>. I first take off the accents and capitalize all letters for a more accurate levenshtein distance.</p>
  
  <p>What I tried is setting a threshold (let's say 80), iterating through the list, making a group out of every string and taking out duplicates elements. Obviously this isn't the result I need because I need every element to appear in only one list (and it isn't the case because A can be linked to B, B to C but not A to C).</p>
  
  <pre class="lang-py prettyprint-override"><code>    groups = []
      for curr in lst:
          curr_grp = []
          for item in lst:
              ratio = normalized.partial_ratio(curr, item)
              if ratio &gt; SET_THRESHOLD:
                  curr_grp.append((item, ratio))
  
          groups.append(curr_grp)
  </code></pre>
  
  <p>I <em>think</em> that there could be a way to find the most optimal configuration from my output:</p>
  
  <pre class="lang-py prettyprint-override"><code>[[('MONTREAL EDUCATION BOARD', 100),
    ('Montréal', 100), # Will probably have to use ratio() and not partial_ratio() because
    ('Monrtéal', 88),  # this can't happen, EDUCATION BOARD is NOT Montreal
    ('Mont-réal', 89)],
   [('Île de Montréal', 100),
    ('Montréal', 100),
    ('Ville de Montréal', 93),
    ('Monrtéal', 88),
    ('Mont-réal', 94)],
   [('MONTREAL EDUCATION BOARD', 100),
    ('Île de Montréal', 100),
    ('Montréal', 100),
    ('Ville de Montréal', 100),
    ('MONTREAL CITY', 100),
    ('Monrtéal', 88),
    ('Mont-réal', 88)],
   [('Île de Montréal', 93),
    ('Montréal', 100),
    ('Ville de Montréal', 100),
    ('Monrtéal', 88),
    ('Mont-réal', 94)],
   [('Montréal', 100),
    ('MONTREAL CITY', 100),
    ('Monrtéal', 88),
    ('Mont-réal', 89)],
   [('MONTREAL EDUCATION BOARD', 88),
    ('Île de Montréal', 88),
    ('Montréal', 88),
    ('Ville de Montréal', 88),
    ('MONTREAL CITY', 88),
    ('Monrtéal', 100)],
   [('MONTREAL EDUCATION BOARD', 89),
    ('Île de Montréal', 94),
    ('Montréal', 88),
    ('Ville de Montréal', 94),
    ('MONTREAL CITY', 89),
    ('Mont-réal', 100)],
   [('Toronto', 100), ('Toronto city', 100), ('Tornoto', 86)],
   [('Toronto', 100), ('Toronto city', 100), ('Tornoto', 86)],
   [('Toronto', 86), ('Toronto city', 86), ('Tornoto', 100)],
   [('What is this', 100)],
   [('Bananasplit', 100), ('Banana', 100)],
   [('Bananasplit', 100), ('Banana', 100)],
   [('StLouis', 100), ('St-Louis', 86), ('Saint Louis', 86)],
   [('StLouis', 86), ('St-Louis', 100)],
   [('StLouis', 86), ('Saint Louis', 100)]]
  </code></pre>
  
  <p>Could it be possible to find the most optimal subset of this list where each element appears only in one group? (so with the highest score?) Take in consideration that my lists will be WAY bigger, so I can't test every configurations because it would take years.</p>
  
  <p>Else, is there another more efficient way to do what I'm trying to do?</p>
  
  <p>Thank you!</p>