All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Sign of a Permutation (Posted on 2006-08-05)
A permutation p1,p2,...,pn of 1,2,...,n is even (resp. odd) if it can be returned to the original order 1,2,...,n using an even (resp. odd) number of interchanges of pairs of elements. It is known that every permutation is either even or odd (and therefore not both).

The sign, or signum (for those who want to be fancy), of a permutation is +1 for an even permutation and -1 for an odd permutation.

You are given the integer n and the array p initialized to the integer values p[1]=p1, p[2]=p2, ..., p[n]=pn which are guaranteed to be a permutation of 1,2,...,n. What algorithm would you advocate for determining the sign of the permutation? You need not preserve the original contents of p.

 See The Solution Submitted by Richard Rating: 3.2000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: Solution | Comment 3 of 11 |
(In reply to Solution by Bractals)

While Bractals' algorithm is indeed not a generalized sort, it does, under the given circumstances sort p into ascending order.  In doing so, it also is indeed more efficient than the Quicksort.  I've implemented both the quicksort method, while counting swaps, as well as Bractals' method, while counting changes of sign of SIGNUM with its two assignments, and indeed the number of sign changes of SIGNUM is less than the number of interchanges in the quicksort.

The program:

DECLARE FUNCTION bractals! (a!())
DECLARE SUB sort (a!(), first!, last!)
CLEAR , , 25000
CLS
DIM SHARED ct

DO
n = INT(20 + RND(1) * 5)
REDIM p(n)
REDIM p2(n)
FOR i = 1 TO n
DO
s = INT(RND(1) * n + 1)
LOOP UNTIL p(s) = 0
p(s) = i
p2(s) = i
NEXT
FOR i = 1 TO n
PRINT USING "###"; p(i);
NEXT
PRINT
ct = 0
sort p(), 1, n
PRINT ct, SGN(.5 - (ct MOD 2))
FOR i = 1 TO n
PRINT USING "###"; p(i);
NEXT
PRINT
ct = 0
signum = bractals(p2())
PRINT ct, signum
FOR i = 1 TO n
PRINT USING "###"; p2(i);
NEXT
PRINT
PRINT
DO: LOOP UNTIL INKEY\$ > ""
LOOP

FUNCTION bractals (a())
i = 1
signum = 1
n = UBOUND(a)
DO WHILE i < n
j = a(i)
IF j = i THEN
i = i + 1
ELSE
signum = -signum
a(i) = a(j)
a(j) = j
ct = ct + 1
END IF
LOOP
bractals = signum
END FUNCTION

SUB sort (a(), first, last)
midV = (a(first) + a(last)) / 2
p1 = first: p2 = last
DO
DO UNTIL (a(p1) > midV OR p1 = p2)
p1 = p1 + 1
LOOP
DO UNTIL (a(p2) < midV OR p1 = p2)
p2 = p2 - 1
LOOP
IF p2 > p1 THEN SWAP a(p1), a(p2): ct = ct + 1
LOOP UNTIL p1 = p2
IF a(p1) >= midV THEN p1 = p1 - 1
IF a(p2) <= midV THEN p2 = p2 + 1
IF p1 > first THEN sort a(), first, p1
IF p2 < last THEN sort a(), p2, last
END SUB

The results:

Here the first row is a randomly sorted array of 20 to 25 members. The second row in each group is the number of swaps the quicksort used, and its concommitant value for the sign. The third line in each group verifies that the array has been sorted. The population of array p was simultaneously made to p2, which Bractals' algorithm worked on.  The fourth line shows how many times the ELSE was taken in that algorithm, with its assignments, and the resulting SIGNUM. The fifth, last line in each group, shows the array p2 after Bractals' algorithm, and it is indeed sorted, as mentioned due to the special nature of the contents of the array.  In all instances, Bractals' algorithm took fewer ELSE's than the quicksort took swaps, and the results agree.

`  5  8 19 20 22 17  3 21 11  9 15 23  1  2 16 18  7  4  6 10 13 14 12 25           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 19           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23`
` 16  5 12  7 17  4 21  2  3 18  1  9 20  8 11 19 14 13 15 22 10  6 28            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 18            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22`
`  5  9  4 19 10  3  1  6 22 17 23  8 15 12 16  2 20 13  7 11 21 14 18 27           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 21           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23`
` 13  9 12  5  7 18 19 10 17 11 14 15  3  1  2  4  6 20 16  8 24            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 18            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20`
`  6 21  1  7 13 18  9 15  5 17 12  8 20 19 10  4 16  3 11 14  2 22 22            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 18            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22`
` 21  8  2 19 14  7 18 11 12  9 16 13  5  4 20 10 17 15  6  1  3 23           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 19           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21`
`  7 17  6  5  9 12  1 14  8 15 21 16 11 22 20 19  2 13  4  3 18 10 26            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 18            1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22`
` 14  4 21 12 18 13 15 17  6  7  1  5 11 19  8 16  2 20  3  9 10 29           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 19           -1  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21`

 Posted by Charlie on 2006-08-05 17:24:50

 Search: Search body:
Forums (0)