|
|
 | | From: | dtmoore | | Subject: | Re: array Puzzle (spoiler) | | Date: | 23 Jan 2005 13:19:42 -0800 |
|
|
 |
Bill Godfrey wrote:
> Willem wrote:
> > Still not a generic x-missing solution though.
>
> Oh okay then. Here's my one that requires the original array to be
> modifiable. (Which is really just a cheat to get around the O(1)
extra
> memory use restriction.)
>
> First pass, for each item...
> If it is a non-zero, move it to its original position in the array,
before
> it was shuffled, swapping with the item found there.
No, this won't sort your list .. at least not the way you have stated
it above. Forget about the zero's for now and try applying it to the
following array:
9 7 2 5 4 3 6 1 8
Even after the first swap, it is clear that you will need more than one
pass through the array. In fact, I would bet the number of passes
required depends on n, and the overall efficiency of the algo is
something like n(log n).
OTOH, I think the algo can be "fixed" so that it will work. Instead of
proceeding through the list from front to back to perform the swaps,
you need to "follow your tail". It is a little hard to explain in
words, but I'll try, following with a worked example. You start with
the first incorrectly placed element, swapping it into its proper place
(as Bill said). You then examine the new value of the swapped element
... if is now correct (or zero) then you proceed to the next element,
otherwise you keep swapping until it is correct. This will in fact
find the values of M zeroed integers in a shuffled, consecutive
sequence of N integers (where N>M).
Lets consider the above example where 4 6 and 7 have been zeroed:
9 0 2 5 0 3 0 1 8
Stepping through the above algo yields the following sequence of
permutations, where I have used carets (^) to indicate the swapped
elements:
^ ^
8 0 2 5 0 3 0 1 9
^ ^
1 0 2 5 0 3 0 8 9
^ ^
1 2 0 5 0 3 0 8 9
^ ^
1 2 0 0 5 3 0 8 9
^ ^
1 2 3 0 5 0 0 8 9
and voila .. we are finished! Now an iteration through the array to ID
the indices of the zeroed elements yields the values.
Perhaps this is what Bill had in mind ... but if so then he didn't
explain it very well 8*). In any case, I think this is the "winning"
solution if we are not dealing with a "const" input array. It is O(n),
it requires only comparison and swap operations rather than arithmetic,
and it works for any number of missing elements.
Whaddaya think?
Dave Moore
|
|
| | From: | Bill Godfrey | | Subject: | Re: array Puzzle (spoiler) | | Date: | 23 Jan 2005 23:43:23 GMT |
|
|
| "dtmoore" wrote:
> Perhaps this is what Bill had in mind ... but if so then he didn't
> explain it very well 8*).
Um, yes, that's exactly what I meant, oh yes.
Bill, hiding.
--
http://billpg.me.uk/
usenet(at)billpg(dot)me(dot)uk
|
|
| | From: | Willem | | Subject: | Re: array Puzzle (spoiler) | | Date: | Mon, 24 Jan 2005 00:10:46 +0000 (UTC) |
|
|
| dtmoore wrote:
) OTOH, I think the algo can be "fixed" so that it will work. Instead of
) proceeding through the list from front to back to perform the swaps,
) you need to "follow your tail". It is a little hard to explain in
) words, but I'll try, following with a worked example. You start with
) the first incorrectly placed element, swapping it into its proper place
) (as Bill said). You then examine the new value of the swapped element
) .. if is now correct (or zero) then you proceed to the next element,
) otherwise you keep swapping until it is correct. This will in fact
) find the values of M zeroed integers in a shuffled, consecutive
) sequence of N integers (where N>M).
It's not entirely obvious that that's O(N).
There can be at most N swaps (each puts one item in its proper place), and
additionally there can be at most N more comparisons that don't lead to a
swap (each moving your pointer one step closer to the end of the list).
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
|
|
|
