Timeline for finding the parity of a permutation in little space
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 1, 2014 at 18:54 | comment | added | Brendan McKay | @JiK : $\Theta(1)$ time. But any version which makes sense as a nice question is fine with me. | |
| Dec 1, 2014 at 12:10 | comment | added | Janne Kokkala | Does, for example, comparing two $\Theta(\log n)$-bit integers require $\Theta(\log n)$ or $\Theta(1)$ time? | |
| Nov 30, 2014 at 19:00 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 319 characters in body
|
| Nov 30, 2014 at 18:56 | comment | added | Brendan McKay | @Włodzimierz: I edited the question to answer yours. | |
| Nov 30, 2014 at 18:55 | history | edited | Brendan McKay | CC BY-SA 3.0 |
added 319 characters in body
|
| Nov 30, 2014 at 9:12 | comment | added | Włodzimierz Holsztyński | @BrendanMcKay -- does space mean additional space? Would it be ok to overwrite the input? | |
| Nov 30, 2014 at 8:24 | answer | added | Vsevolod Oparin | timeline score: 2 | |
| Aug 11, 2011 at 22:15 | answer | added | Gerhard Paseman | timeline score: 1 | |
| Aug 11, 2011 at 18:00 | comment | added | Gerhard Paseman | It occurred to me that you may want theta(n) bits to hellp you avoid retracing. If you are willing to do some retracing, you could drop bread crumbs on a long cycle every sqrt(n) steps or less. This would involve fewer than n bits and take at most sqrt(n)times c extra steps, where c is the number of longish cycles. Replace sqrt(n) by a more comfortable parameter as desired. If you have more time and fewer bits, use a bit to mark the lowest number not yet guaranteed to be visited. Gerhard "Ask Me About System Design" Paseman, 2011.08.11 | |
| Aug 11, 2011 at 17:00 | comment | added | Gerhard Paseman | How do you trace a cycle? And is it not sufficient to mark just 1 number in that cycle? Gerhard "!Ask Me About System Design" Paseman, 2011.08.11 | |
| Aug 11, 2011 at 15:29 | comment | added | Brendan McKay | To Junkie: Given any $i$ you can get $\pi(i)$. For example, it might be an array $p$ of length $n$ such that $p[i]=\pi(i)$. As for overwriting in place, that's not what I had in mind to allow but it makes for an interesting variation. However, assume the number of bits in each array element is only just enough to hold $n$, otherwise you need to count the extra bits as working space. To Alexander: I should have been clearer that I'm counting space in bits. You need two indexes that are integers with $O(\log n)$ bits each. I agree the count of inversions only needs 1 bit. | |
| Aug 11, 2011 at 15:24 | answer | added | Igor Rivin | timeline score: 3 | |
| Aug 11, 2011 at 14:08 | comment | added | Alexander Woo | Counting the inversions only takes O(1) space, because you can count them mod 2. | |
| Aug 11, 2011 at 14:02 | comment | added | Junkie | How is the permutation represented? If it is an array of $n$ integers, can you over-write these in place, if at the end the original array is restored? | |
| Aug 11, 2011 at 8:50 | history | asked | Brendan McKay | CC BY-SA 3.0 |