<p>You asked two questions, one somewhat open-ended (the first one) and other one that has a definitive answer, so I will start by the second one:</p>

<blockquote>
  <p>Is there a transformation already available that takes as an input a
  matrix like M and produces a matrix like C? Preferably, a python
  package?</p>
</blockquote>

<p>The answer is yes, there is one package named <a href="https://docs.scipy.org/doc/scipy/reference/spatial.distance.html" rel="nofollow noreferrer">scipy.spatial.distance</a> that contains a function that takes a matrix like <code>M</code> and produces a matrix like <code>C</code>. The following example is to show the function:</p>

<pre><code>import numpy as np
from scipy.spatial.distance import pdist, squareform

# initial data
M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]

# convert to numpy array
arr = np.array(M)

result = squareform(pdist(M, metric='euclidean'))
print(result)
</code></pre>

<p><strong>Output</strong></p>

<pre><code>[[ 0.         22.         16.1245155 ]
 [22.          0.         33.76388603]
 [16.1245155  33.76388603  0.        ]]
</code></pre>

<p>As seen from the example above, <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.pdist.html#scipy.spatial.distance.pdist" rel="nofollow noreferrer">pdist</a> takes the <code>M</code> matrix and generates an <code>C</code> matrix. Note that the output of <code>pdist</code> is a <em>condensed distance matrix</em>, so you need to convert it to square form using <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.squareform.html#scipy.spatial.distance.squareform" rel="nofollow noreferrer">squareform</a>. Now onto the second issue:</p>

<blockquote>
  <p>What is a good choice for comparing the ordering of two lists? That
  is, what is a good choice for function f?</p>
</blockquote>

<p>Given that order does matter in your particular case I suggest you look at rank correlation coefficients such as: <a href="https://en.wikipedia.org/wiki/Kendall_rank_correlation_coefficient" rel="nofollow noreferrer">Kendall</a> or <a href="https://en.wikipedia.org/wiki/Spearman%27s_rank_correlation_coefficient" rel="nofollow noreferrer">Spearman</a>, both are provided in the <a href="https://docs.scipy.org/doc/scipy/reference/stats.html" rel="nofollow noreferrer">scipy.stats</a> package, along with a whole bunch of other coefficients. Usage example:</p>

<pre><code>import numpy as np
from scipy.spatial.distance import pdist, squareform
from scipy.stats import kendalltau, spearmanr

# distance function
kendall = lambda x, y : kendalltau(x, y)[0]
spearman = lambda x, y : spearmanr(x, y)[0]


# initial data
M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]

# convert to numpy array
arr = np.array(M)

# compute kendall C and convert to square form
kendall_result = 1 - squareform(pdist(arr, kendall))  # subtract 1 because you want a similarity
print(kendall_result)
print()

# compute spearman C and convert to square form
spearman_result = 1 - squareform(pdist(arr, spearman))  # subtract 1 because you want a similarity
print(spearman_result)
print()
</code></pre>

<p><strong>Output</strong></p>

<pre><code>[[1.         0.33333333 0.        ]
 [0.33333333 1.         0.33333333]
 [0.         0.33333333 1.        ]]

[[1.  0.2 0. ]
 [0.2 1.  0.2]
 [0.  0.2 1. ]]
</code></pre>

<p>If those do not fit your needs you can take a look at the <a href="https://en.wikipedia.org/wiki/Hamming_distance" rel="nofollow noreferrer">Hamming distance</a>, for example:</p>

<pre><code>import numpy as np
from scipy.spatial.distance import pdist, squareform

# initial data
M = [[18, 34, 54, 65],
     [18, 12, 54, 65],
     [21, 43, 55, 78]]

# convert to numpy array
arr = np.array(M)

# compute match_rank C and convert to square form
result = 1 - squareform(pdist(arr, 'hamming'))
print(result)
</code></pre>

<p><strong>Output</strong></p>

<pre><code>[[1.   0.75 0.  ]
 [0.75 1.   0.  ]
 [0.   0.   1.  ]]
</code></pre>

<p>In the end the choice of the similarity function will depend on your final application, so you will need to try out different functions and see the ones that fit your needs. Both <code>scipy.spatial.distance</code> and <code>scipy.stats</code> provide a plethora of distance and coefficient functions you can try out.</p>

<p><strong>Further</strong></p>

<ol>
<li>The following <a href="https://arxiv.org/pdf/1107.2691.pdf" rel="nofollow noreferrer">paper</a> contains a section on list similarity</li>
</ol>
Second-order cooccurrence of terms in texts
<p>Basically, <a href="https://www.youtube.com/watch?v=sI7VpFNiy_I&amp;t=20m" rel="nofollow noreferrer">I want to reimplement this video</a>. </p>

<p>Given a corpus of documents, I want to find the terms that are most similar to each other. </p>

<p>I was able to generate a cooccurrence matrix using <a href="https://stackoverflow.com/a/37822989">this SO thread</a> and use the video to generate an association matrix. Next I, would like to generate a second order cooccurrence matrix.</p>

<p>Problem statement: Consider a matrix where the rows of the matrix correspond to a term and the entries in the rows correspond to the top k terms similar to that term. Say, k = 4, and we have n terms in our dictionary, then the matrix <code>M</code> has <code>n</code> rows and <code>4</code> columns.</p>

<p>HAVE: </p>

<pre><code>M = [[18,34,54,65],   # Term IDs similar to Term t_0
     [18,12,54,65],   # Term IDs similar to Term t_1
     ...
     [21,43,55,78]]   # Term IDs similar to Term t_n.
</code></pre>

<p>So, M contains for each term ID, the most similar term IDs. Now, I would like to check how many of those similar terms match. In the example of <code>M</code> above, it seems that term <code>t_0</code> and term <code>t_1</code> are quite similar, because three out of four terms match, where as terms <code>t_0</code> and <code>t_n</code>are not similar, because no terms match. Let's write <code>M</code> as a series of lists.</p>

<pre><code>M = [list_0,   # Term IDs similar to Term t_0
     list_1,   # Term IDs similar to Term t_1
     ...
     list_n]   # Term IDs similar to Term t_n.
</code></pre>

<p>WANT:</p>

<pre><code>C = [[f(list_0, list_0), f(list_0, list_1), ..., f(list_0, list_n)],
     [f(list_1, list_0), f(list_1, list_1), ..., f(list_1, list_n)],
     ...
     [f(list_n, list_0), f(list_n, list_1), ..., f(list_n, list_n)]]
</code></pre>

<p>I'd like to find the matrix <code>C</code>, that has as its elements, a function <code>f</code> applied to the lists of <code>M</code>. <code>f(a,b)</code> measures the degree of similarity between two lists <code>a</code> and <code>b</code>. Going, with the example above, the degree of similarity between <code>t_0</code> and <code>t_1</code> should be high, whereas the degree of similarity of <code>t_0</code> and <code>t_n</code> should be low. </p>

<p>My questions:   </p>

<ol>
<li>What is a good choice for comparing the ordering of two lists? That is, what is a good choice for function <code>f</code>?   </li>
<li>Is there a transformation already available that takes as an input a matrix like <code>M</code> and produces a matrix like <code>C</code>? Preferably a python package?</li>
</ol>

<p>Thank you, r0f1</p>