How to check if two permutations are symmetric?
<p>Given two permutations <code>A</code> and <code>B</code> of <code>L</code> different elements, <code>L</code> is even, let's call these permutations &quot;symmetric&quot; (for a lack of a better term), if there exist <code>n</code> and <code>m</code>, <code>m &gt; n</code> such as (in python notation):</p>
<pre><code> - A[n:m] == B[L-m:L-n]
 - B[n:m] == A[L-m:L-n]
 - all other elements are in place
</code></pre>
<p>Informally, consider</p>
<pre><code>A = 0 1 2 3 4 5 6 7
</code></pre>
<p>Take any slice of it, for example <code>1 2</code>. It starts at the second index and its length is 2. Now take a slice symmetric to it: it ends at the penultimate index and is 2 chars long too, so it's <code>5 6</code>. Swapping these slices gives</p>
<pre><code>B = 0 5 6 3 4 1 2 7
</code></pre>
<p>Now, <code>A</code> and <code>B</code> are &quot;symmetric&quot; in the above sense (<code>n=1, m=3</code>). On the other hand</p>
<pre><code>A = 0 1 2 3 4 5 6 7
B = 1 0 2 3 4 5 7 6
</code></pre>
<p>are not &quot;symmetric&quot; (no <code>n,m</code> with above properties exist).</p>
<p>How can I write an algorithm in python that finds if two given permutations (=lists) are &quot;symmetric&quot; and if yes, find the <code>n</code> and <code>m</code>? For simplicity, let's consider only even <code>L</code> (because the odd case can be trivially reduced to the even one by eliminating the middle fixed element) and assume correct inputs (<code>set(A)==set(B), len(set(A))==len(A)</code>).</p>
<p>(I have no problem bruteforcing all possible symmetries, but looking for something smarter and faster than that).</p>
<p>Fun fact: the number of symmetric permutations for the given <code>L</code> is a <a href="https://en.wikipedia.org/wiki/Triangular_number" rel="noreferrer">Triangular number</a>.</p>
<h3>I use <a href="https://gist.github.com/gebrkn/8b73949295853bdaf2b9" rel="noreferrer">this code</a> to test  out your answers.</h3>
<p>Bounty update: many excellent answers here. <a href="https://stackoverflow.com/a/35589985/989121">@Jared Goguen's solution</a> appears to be the fastest.</p>
<p>Final timings:</p>
<pre><code>testing 0123456789 L= 10
    test_alexis ok in 15.4252s
    test_evgeny_kluev_A ok in 30.3875s
    test_evgeny_kluev_B ok in 27.1382s
    test_evgeny_kluev_C ok in 14.8131s
    test_ian ok in 26.8318s
    test_jared_goguen ok in 10.0999s
    test_jason_herbburn ok in 21.3870s
    test_tom_karzes ok in 27.9769s
</code></pre>