[math-fun] recognizing an even permutation
Given a permutation of {1,2,3,...,N}, how iton -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Given a permutation of {1,2,3,...,N}, in the form of a vector f(1), f(2), ..., f(N) how quickly (and using how little memory) can you decide whether it is an "even" permutation? I can see a way to do it in O(N) operations which uses only O(1) words of memory plus the memory used to store the input array f[]; but unfortunately this N-entry array will be destroyed/overwritten. I also see a way to do it in O(N^2) operations with only O(1) words of extra memory -- the input array now is unaltered. But I do not know a way to do it that uses memory*time product that is o(N^2). -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Warren, The following is O(N) plus 1 bit (if you don't count the sign bits). It doesn't treat f as readonly, but does restore it to its orignal state. A permutation is even if and only if the number of even cycles is even. So do the following: set b = 0 i = 1 /* check for a cycle starting at i */ while (i < n) and f(i) > 0: k = 1 j = f(i) f(i) = -f(i) while f(j) > 0 do k = 1-k jnew = f(j) j = f(j) f(j) = - jnew if k = 0 set b = 1-b i = i+1 end while /* Now the permuation is even if and only if b = 0 */ /* fix up the signs */ for i = 1 to n: f(i) = -f(i) return b On Thu, Apr 28, 2016 at 4:18 PM, Warren D Smith <warren.wds@gmail.com> wrote:
Given a permutation of {1,2,3,...,N}, in the form of a vector f(1), f(2), ..., f(N) how quickly (and using how little memory) can you decide whether it is an "even" permutation?
I can see a way to do it in O(N) operations which uses only O(1) words of memory plus the memory used to store the input array f[]; but unfortunately this N-entry array will be destroyed/overwritten. I also see a way to do it in O(N^2) operations with only O(1) words of extra memory -- the input array now is unaltered. But I do not know a way to do it that uses memory*time product that is o(N^2).
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Warren D Smith <warren.wds@gmail.com> [Apr 29. 2016 08:44]:
Given a permutation of {1,2,3,...,N}, in the form of a vector f(1), f(2), ..., f(N) how quickly (and using how little memory) can you decide whether it is an "even" permutation?
I can see a way to do it in O(N) operations which uses only O(1) words of memory plus the memory used to store the input array f[]; but unfortunately this N-entry array will be destroyed/overwritten. I also see a way to do it in O(N^2) operations with only O(1) words of extra memory -- the input array now is unaltered. But I do not know a way to do it that uses memory*time product that is o(N^2).
I know no better than "cycle chasing": use an extra (boolean) array to remember which elements were see so far. With slight cheating: negate the element already seen. At end, flip all signs back to positive (that may be what's suggested in the other answer). Slightly worse in terms of big-O: compute the inversion table in O(n*log(n)), perm even <==> sum of inversion numbers even (IIRC).
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Joerg Arndt -
Victor Miller -
Warren D Smith