StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm very slightly skeptical that there is a solution. Your problem seems to be very close to one posed several years ago in the mathematical literature, with <a href="http://geomete.com/abdali/papers/duplmath.pdf" rel="nofollow noreferrer">a summary given here ("The Duplicate Detection Problem", S. Kamal Abdali, 2003)</a> that uses cycle-detection -- the idea being the following:</p> <p>If there is a duplicate, there exists a number <code>j</code> between 1 and N such that the following would lead to an infinite loop:</p> <pre><code>x := j; do { x := a[x]; } while (x != j); </code></pre> <p>because a permutation consists of one or more subsets S of distinct elements s<sub>0</sub>, s<sub>1</sub>, ... s<sub>k-1</sub> where s<sub>j</sub> = a[s<sub>j-1</sub>] for all j between 1 and k-1, and s<sub>0</sub> = a[s<sub>k-1</sub>], so all elements are involved in cycles -- one of the duplicates would not be part of such a subset.</p> <p>e.g. if the array = [2, 1, 4, 6, <strong>8</strong>, 7, 9, 3, 8]</p> <p>then the element in bold at position 5 is a duplicate because all the other elements form cycles: { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3}. Whereas the arrays [2, 1, 4, 6, 5, 7, 9, 3, 8] and [2, 1, 4, 6, 3, 7, 9, 5, 8] are valid permutations (with cycles { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 3, 5 } and { 2 -> 1, 4 -> 6 -> 7 -> 9 -> 8 -> 5 -> 3 } respectively).</p> <p>Abdali goes into a way of finding duplicates. Basically the following algorithm (using <a href="http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare" rel="nofollow noreferrer">Floyd's cycle-finding algorithm</a>) works if you happen across one of the duplicates in question:</p> <pre><code>function is_duplicate(a, N, j) { /* assume we've already scanned the array to make sure all elements are integers between 1 and N */ x1 := j; x2 := j; do { x1 := a[x1]; x2 := a[x2]; x2 := a[x2]; } while (x1 != x2); /* stops when it finds a cycle; x2 has gone around it twice, x1 has gone around it once. If j is part of that cycle, both will be equal to j. */ return (x1 != j); } </code></pre> <p>The difficulty is I'm not sure your problem as stated matches the one in his paper, and I'm also not sure if the method he describes runs in O(N) or uses a fixed amount of space. A potential counterexample is the following array:</p> <p>[3, 4, 5, 6, 7, 8, 9, 10, ... N-10, N-9, N-8, N-7, N-2, N-5, N-5, N-3, N-5, N-1, N, 1, 2]</p> <p>which is basically the identity permutation shifted by 2, with the elements [N-6, N-4, and N-2] replaced by [N-2, N-5, N-5]. This has the correct sum (not the correct product, but I reject taking the product as a possible detection method since the space requirements for computing N! with arbitrary precision arithmetic are O(N) which violates the spirit of the "fixed memory space" requirement), and if you try to find cycles, you will get cycles { 3 -> 5 -> 7 -> 9 -> ... N-7 -> N-5 -> N-1 } and { 4 -> 6 -> 8 -> ... N-10 -> N-8 -> N-2 -> N -> 2}. The problem is that there could be up to N cycles, (identity permutation has N cycles) each taking up to O(N) to find a duplicate, and you have to keep track somehow of which cycles have been traced and which have not. I'm skeptical that it is possible to do this in a fixed amount of space. But maybe it is.</p> <p>This is a heavy enough problem that it's worth asking on <a href="https://mathoverflow.net/">mathoverflow.net</a> (despite the fact that most of the time mathoverflow.net is cited on stackoverflow it's for problems which are too easy)</p> <hr> <p><strong>edit:</strong> I did <a href="https://mathoverflow.net/questions/25374/duplicate-detection-problem/25419#25419">ask on mathoverflow</a>, there's some interesting discussion there.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload