Perm sign
From QETLAB
perm_sign | |
Computes the sign of a permutation | |
Other toolboxes required | none |
---|---|
Related functions | perm_inv |
Function category | Helper functions |
This is a helper function that only exists to aid other functions in QETLAB. If you are an end-user of QETLAB, you likely will never have a reason to use this function. |
perm_sign is a function that computes the sign of a permutation. The output of the function is either 1, indicating the permutation is even, or -1, indicating the permutation is odd.
Contents
Syntax
- SGN = perm_sign(PERM)
Argument descriptions
- PERM: A vector containing a permutation of the integers 1, 2, ..., n.
Examples
Small examples
The identity permutation is even:
The permutation that transposes 3 and 4 is odd:
A large example
This function has no trouble with large permutations. The following code determines the sign of a random permutation of 1:1000000 in under 1/2 of a second on a standard desktop computer:
Source code
Click on "expand" to the right to view the MATLAB source code for this function.
%% PERM_SIGN Computes the sign of a permutation
% This function has one required argument:
% PERM: a permutation vector
%
% SGN = perm_sign(PERM) is the sign (either -1 or 1) of the permutation
% PERM. In other words, SGN = (-1)^INV, where INV is the number of
% inversions contained in PERM.
%
% URL: http://www.qetlab.com/perm_sign
% requires: nothing
% author: Nathaniel Johnston (nathaniel@njohnston.ca)
% package: QETLAB
% last updated: November 21, 2012
function sgn = perm_sign(perm)
Id = speye(length(perm));
% At first glance, the following looks like it should be slow (something
% like O(n^3)). However, MATLAB is able to exploit the extreme sparsity of
% Id(:,perm) to make this computation more like O(n).
sgn = det(Id(:,perm));