51
$\begingroup$

The sign of a permutation $\sigma\in \mathfrak{S}_n$, written ${\rm sgn}(\sigma)$, is defined to be +1 if the permutation is even and -1 if it is odd, and is given by the formula

$${\rm sgn}(\sigma) = (-1)^m$$

where $m$ is the number of transpositions in the permutation when written as a product of transpositions.

Alternatively the sign is -1 if, when we express $\sigma$ as a product of disjoint cycles, the result contains an odd number of even-length cycles. Otherwise the sign is +1.

My permutations are expressed as tuples $(\sigma_1,\dots,\sigma_n)$, so neither the expression of the tuple as a product of disjoint cycles nor as a product of transpositions are immediately available to me.

This suggests two high-algorithms to compute the sign of a permutation:

  1. Express the permutation as a product of transpositions and count the number of transpositions.

  2. Express the permutation as a product of disjoint cycles and count the number of even-length cycles.

What are typical algorithms for accomplishing these tasks, and how do they vary in running type depending on $n$? Are there more efficient algorithms for calculating the sign of a permutation?


Additional info

The motivation is to quickly decide whether instances of the fifteen puzzle are solvable. I want to generate a large number of solvable instances of the fifteen puzzle for testing some search algorithms. At the moment I generate a random instance, and test whether it is solvable by trying to solve it with depth-first search, which is fairly slow going, and won't generalize well to larger puzzles (24 puzzle, 35 puzzle...) due to time and memory limitations. Since solvable instances of the fifteen puzzle are in 1-1 correspondence with even elements of $\mathfrak{S}_{16}$, I figure that there must be a faster way of generating solvable instances.

It has just occurred to me that a better way of generating solvable instances of the puzzle might be to generate an even number of transpositions and multiply them together to generate an even permutation. I'd prefer an algorithm that was guaranteed to return an even distribution over $\mathfrak{S}_n$ though, and in fact I'm now sufficiently interested in the answer to this question in its own right.

$\endgroup$
10
  • 8
    $\begingroup$ The parity of a permutation is also the number of inversions in the permutation modulo $2$. Since the number of inversions can be computed in $O(n \log n)$ time, parity can certainly be. It's an interesting question if even faster algorithms are possible. Off the top of my head, I can't think of any reason why $O(n)$ algorithm is impossible. (This is the best reference I could pull off right now for finding inversions: stackoverflow.com/questions/6523712/… .) $\endgroup$
    – Srivatsan
    Commented Sep 19, 2011 at 23:58
  • 2
    $\begingroup$ It seems the situation is more complicated. PengOne's answer in the other question says that there is a long-standing $O(n \frac{\log n}{\log \log n})$ algorithm and a recent $O(n \sqrt{\log n})$ algorithm for counting inversions. Actually, I think this question would be a good fit for cstheory.SE as well. $\endgroup$
    – Srivatsan
    Commented Sep 20, 2011 at 0:02
  • 1
    $\begingroup$ I think you can find this in Knuth. (No, I don't know where. It just feels like it's in there somewhere.) $\endgroup$ Commented Sep 20, 2011 at 0:16
  • 3
    $\begingroup$ You should probably specify what encoding of a permutation you're using (in cycle notation, shouldn't you be able to compute the parity in $O(n)$ time?). $\endgroup$ Commented Sep 20, 2011 at 0:27
  • 1
    $\begingroup$ See also mathoverflow.net/questions/72669/… $\endgroup$
    – lhf
    Commented Sep 20, 2011 at 0:52

7 Answers 7

25
$\begingroup$

So you have a permutation $f: X \to X$ for which you can efficiently compute $f(x)$ from $x$.

I think a good way to do any of the things you mentioned is to make a checklist for the elements of $X$. Then you can start with the first unchecked element and follow the chain $x, f(x), f(f(x))$, etc. checking off each element as you find it until you reach an element that is already checked. You have now traversed one cycle. Then you can pick the next unchecked element and traverse that cycle, and so on until all elements are checked.

While you traverse a cycle you can easily

  1. Count the cycle length
  2. Record the cycle, or
  3. Record transpositions

All this works in roughly linear time. Obviously just counting the cycle lengths is going to be the fastest.

$\endgroup$
2
  • $\begingroup$ Nice :). I totally missed that the cycle representation can indeed be obtained in linear time... $\endgroup$
    – Srivatsan
    Commented Sep 20, 2011 at 1:05
  • $\begingroup$ Thanks for your answer Niels. $\endgroup$ Commented Sep 23, 2011 at 14:11
14
$\begingroup$

It's worth mentioning the quadratic time algorithm, since it can be faster for small permutations:

$$\textrm{sgn}(\sigma) = (-1)^{\sum_{0 \le i<j<n} (\sigma_i>\sigma_j)}$$

I.e., the sign is negative iff there are an odd number of misordered pairs of indices. This algorithm also works if we're interested in the permutation defined by an unsorted list of integers where the cycle structure can't be determined in linear time.

$\endgroup$
2
  • $\begingroup$ Wouldn't you need a sum over all $1 \leq i < j \leq n$? $\endgroup$
    – lynn
    Commented Oct 13, 2015 at 15:02
  • $\begingroup$ Mauris: Fixed. I had left off the $0 \le$. $\endgroup$ Commented Oct 13, 2015 at 23:02
9
$\begingroup$

If $c_e(n)$ is the number of even-length cycles in a permutation $p$ of length $n$, then one of the formulas for the sign of a permutation $p$ is $\text{sgn}(p) = (-1)^{c_e(n)}$.

Here is an $O(n)$ Matlab function that computes the sign of a permutation vector $p(1:n)$ by traversing each cycle of $p$ and (implicitly) counting the number of even-length cycles. The number of cycles in a random permutation of length $n$ is $O(H_n)$, where $H_n$ is the $n$-th Harmonic Number.

function sgn = SignPerm(p);
% ----------------------------------------------------------
% Calculates the sign of a permutation p.
% p is a row vector p(1,n), which represents the permutation.
% sgn(p) = (-1)^(No. of even-length cycles)
% Complexity : O(n + ncyc) ~ O(n + Hn) ~~ O(n+log(n)) steps.
%
% Derek O'Connor 20 March 2011.
% ----------------------------------------------------------
n   = length(p);
visited(1:n) = false;                  % Logical vector which marks all p(k)
                                       % not visited.
sgn = 1;
for k = 1:n
    if ~visited(k)                     % k not visited, start of new cycle
        next = k;
        L = 0;
        while ~visited(next)           % Traverse the current cycle k
            L = L+1;                   % and find its length L
            visited(next) =  true;
            next    = p(next);
        end
        if rem(L,2) == 0               % If L is even, change sign.
            sgn = -sgn;
        end
    end % if ~visited(k)
end % for k 
$\endgroup$
2
  • $\begingroup$ Every cycle of length $n$ can be factored into a product of $n-1$ transpositions (on the same elements). For example, $(abc\cdots)=(ab)(ac)\cdots$. This explains the $c_{\epsilon}(n)$ formula, since disjoint cycles factor into disjoint transpositions. $\endgroup$
    – bgins
    Commented Dec 15, 2011 at 21:34
  • $\begingroup$ Note that for $n$ approaching $\infty$ (which is what we are interested in when doing the time complexity analysis), $O(n+\log n)=O(n)$. $\endgroup$ Commented Dec 14, 2020 at 9:18
3
$\begingroup$

The inverse permutation can be constructed as a sequence of $n-1$ transpositions via Gaussian Elimination with partial pivoting, $P A = L U$, where $A$ is the original permutation matrix, $P=A^{-1}$, and $L=U=I$. Since the signature of the inverse permutation is the same as that of the original permutation, this procedure yields the sign of the permutation.

Thankfully, this algorithm can be run in linear time by maintaining the permutation and its inverse throughout a short-circuited Gaussian Elimination procedure since it can easily be seen that the Schur complement updates will always be zero.

$\endgroup$
3
$\begingroup$

$sgn(\sigma)=\prod_{i<j}\frac{\sigma(i)-\sigma(j)}{i-j}$ is quadratic, but straightforward to code.

$\endgroup$
2
$\begingroup$

Use the Fisher-Yates-Shuffle in its inside-out version to generate a permutation of the numbers $1\dots16$. You can find the parity of this permutation by counting the number of transpositions you performed. This is easy: Every time $i\neq j$ you perform a transposition. If the puzzle invariant is violated now, simply exchange two arbitrary tiles (not the empty spot) to make the puzzle solvable.

Here is the inside-out Fisher-Yates shuffle in a version that generates a random permutation in an array $a[1\dots n]$:

  1. for $i$ from $1$ to $n$ do:
  2. $j\leftarrow\mathop{\rm rnd}\{1\ldots i\}$
  3. if $i\neq j$ then $a[i]\leftarrow a[j]$
  4. $a[j]\leftarrow i$

Every time the branch in step 3 is taken, you perform a transposition and need to toggle your parity.

$\endgroup$
3
  • $\begingroup$ I almost didn't see how this answered the question, because this question is an example of an "XY" problem. The OP really wanted to generate solvable puzzles (problem X), and guessed that a good way to do this was to shuffle the tiles (using a "black box" algorithm where the number of transpositions was not visible to the user) and then discard the shuffles that weren't solvable (problem Y). Instead of asking how to solve X, OP asked how to solve Y. You have offered a replacement for the black box that makes it possible to solve X without dealing with Y. $\endgroup$
    – David K
    Commented Sep 5, 2017 at 22:56
  • 1
    $\begingroup$ Assuming random number generation is more expensive than just storing a number in memory, it's more efficient to do the shuffle using the non-inside-out (i.e. the regular) version. This way, the last swap is always a 50/50 coin flip. One side of the coin yields a valid permutation, and the other side doesn't. If you have been keeping track of how many swaps you did, then instead of flipping the coin, you can just immediately go for the valid permutation. This way you always get a valid permutation, and all valid permutations are equally likely, and it's O(n). $\endgroup$
    – Matt
    Commented May 15, 2020 at 0:43
  • $\begingroup$ @Matt Cool idea! Will keep that one in mind. $\endgroup$
    – FUZxxl
    Commented May 15, 2020 at 10:07
-1
$\begingroup$

Welcome to $O(n)$'s world. Python code

def decomposition(n, sigma):
   lista = list()
   for k in range (1, n + 1):
      boo = False
      for i in range (0, n):
         if sigma[i] == k:
            boo = True
            break
      if not boo:
         print("Error")
         return
   
   contador = 0
   for i in range (0, n - 1):
      if sigma[i] != i + 1:
         k = sigma[i] - 1
         sigma[i], sigma[k] = i + 1, k + 1
         s = "(" + str(i + 1) + ", " + str(k + 1) + ")"
         lista.insert(0, s)
         contador = contador + 1
         
   s = ""
   for cadaUm in lista:
     s = s + cadaUm
   print("sigma =", s)
   print("size =", contador)
   return
$\endgroup$
4
  • $\begingroup$ Although your code has within it an $O(n)$ method of counting the number of transpositions, it also contains two $O(n^2)$ sections: first, the for k ... for i ... loop nest, and second, the lista.insert(0, s) step, which for large arrays in Python is an $O(n)$ op inside an $O(n)$ loop. So your code as shown is $O(n^2)$, not $O(n)$. Of course, the first loop nest is not needed, and returning the lista result also is undesirable, so it's easy to reduce the code to $O(n)$. Note, the Python way for the 3 lines that compute s before printing s is: s = ''.join(lista) instead of a loop. $\endgroup$ Commented Feb 22, 2021 at 2:50
  • $\begingroup$ Also, a Python way to test for all numbers present is to just say: if not all(k in sigma for k in range(1,n)): before print("Error") and return. That is, just use the built-in function all along with list comprehension. Also, while your s = "(" + str(i + 1) + ", " + str(k + 1) + ")" is a way to compute that string, a shorter way is to just say s = f'({i +1}, {k+1})' $\endgroup$ Commented Feb 22, 2021 at 2:57
  • $\begingroup$ Note, whether the if not all(k in sigma for k in range(1,n)): method is $O(n)$ or $O(n^2)$ depends on the implementation of k in sigma... if a hash table is used, so a lookup is $O(1)$, the test is $O(n)$; but if linear search is used, the test is $O(n^2)$. Of course, if you leave the test to the end instead of doing it at the beginning, you could check if array sigma ends up equal to list(range(1,n)) which is easy to test in $O(n)$ time; eg, if not all(sigma[k-1]==k for k in range(1,n+1)): .... $\endgroup$ Commented Feb 22, 2021 at 3:27
  • $\begingroup$ The essence is: given a vector $[x_1, x_2, ..., x_n]$, the target vector is $[1, 2, ..., n]$. Exchange the first by 1, the second by 2, the third by 3... and the last by $n$. That's $O(n)$. All other validations may be external. $\endgroup$ Commented Feb 25, 2021 at 18:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .