title: How to speed up itertools combinations?
body: <p>As part of my own research on genotype networks, I have a block of code in which I am trying to construct a single-difference network from a list of strings. The procedure is as such:</p>
  
  <ol>
  <li>Iterate over all pairwise combinations of strings.</li>
  <li>If the strings differ by a single position, then draw an edge between them in the network.</li>
  <li>If they don't differ by a single position, then pass.</li>
  </ol>
  
  <p>The block of code I have right now is as such:</p>
  
  <pre><code>from itertools import combinations
  import Levenshtein as lev # a package that wraps a C-implemented levenshtein distance
  import networkx as nx
  strings = [...list of strings...]
  
  G = nx.Graph()
  
  for (s1, s2) in combinations(strings, 2):
      if s1 not in G.nodes():
          G.add_node(s1)
      if s2 not in G.nodes():
          G.add_node(s2)
  
      if lev.distance(s1, s2) == 1:
          G.add_edge(s1, s2)
  </code></pre>
  
  <p>There's clearly no way to improve the computational complexity of the graph construction procedure - it will always be <code>O(n**2)</code>. At least, in my limited knowledge, that's what I think - perhaps I'm wrong?</p>
  
  <p>That said, given the normal scale of the number of comparisons that I need to make (~approx. 2000-5000), if I can get a few orders of magnitude speedup, overall, then the real-world computing time would be still acceptable - with the current Python implementation, it takes ~days to construct the graph. With the correct imports (not stated below), I have tried a Cython implementation below, but could not figure out how to make it faster:</p>
  
  <pre><code>cpdef cython_genotype_network(sequences):
  
      G = nx.Graph()
      cdef:
          unicode s1
          unicode s2
  
      for (s1, s2) in combinations(sequences, 2):
          if lev.distance(s1, s2) == 1:
              G.add_edge(s1, s2)
  
      return G
  </code></pre>
  
  <p>Particularly, Cython expects <code>bytes</code>, not <code>str</code> for <code>s1</code> and <code>s2</code>. That block of code throws an error.</p>
  
  <p>So... I come to my two questions:</p>
  
  <ul>
  <li>Q1: Will the Cython implementation help? And how do I fix the bytes vs. str error?</li>
  <li>Q2: Is it possible to do this problem using <code>numpy</code> instead? It's easy to convert from a <code>numpy</code> matrix to NetworkX; however, I can't seem to figure out how to broadcast the Levenshtein distance function across an n-by-n empty matrix where the each row and column corresponds to a string.</li>
  </ul>
  
  <p><strong>UPDATE 1: How to generate sample data</strong></p>
  
  <p>To generate strings:</p>
  
  <pre><code>from random import choice
  
  def create_random_nucleotides_python(num_nucleotides):
      """
      Creates random nucleotides of length num_nucleotides.
      """
  
      sequence = ''
  
      letters = ['A', 'T', 'G', 'C']
  
      for i in range(num_nucleotides):
          sequence = sequence + choice(letters)
  
      return sequence
  
  
  def mutate_random_position(string):
      """
      Mutates one position in the nucleotide sequence at random.
      """
  
      positions = [i for i in range(len(string))]
      pos_to_mut = choice(positions)
  
      letters = ['A', 'T', 'G', 'C']
  
      new_string = ''
      for i, letter in enumerate(string):
          if i == pos_to_mut:
              new_string = new_string + choice(letters)
          else:
              new_string = new_string + letter
  
      return new_string
  
  
  # Create 100 Python srings by mutating a first sequence, then randomly choosing stuff to mutate a single position.
  base_sequence = create_random_nucleotides_python(1000)
  
  sequences = [base_sequence]
  
  for i in range(99):
      sequence = choice(sequences)
      mutseq = mutate_random_position(sequence)
      sequences.append(mutseq)
  </code></pre>