|
OK, I'll give it a shot. The basic algorithm moves two pointers through a linked list. One pointer takes single steps and the other takes double steps. If there's a cycle, the two pointers will eventually point to the same node. The algorithm doesn't tell where the loop is.
Here's my extension to Floyd's Algorithm. You mentioned O(n^2) so I assume time is more important to you than space.
1. Count the number of times the single-step pointer is advanced. When the loop is detected you know its length is definitely less than or equal to this counter.
2. When the loop is detected, you know the node both pointers reference is definitely in the loop. Save this pointer.
3. At this point create a hash table big enough to hold pointers to all nodes in the loop. (You can do this because the counter gives you an upper bound on the loop size.)
4. Continue chaining through the loop in single steps. Add each node pointer to the hash table. Compare each node pointer to the saved pointer. When you find a match, you know the whole loop is in the hash table.
5. Go back to the start of the list, and chain through it again, checking if each node pointer is in the hash table. When this happens, you've identified where the cycle begins.
Alternative: If you have a tiny loop at the end of a very very long linked list and you want to optimize space, after Step 2 go through the loop again and count the number of nodes in the loop. The hash table only has to hold this number of pointers, which is much smaller than the count from Step 1. (It will be a bit slower because you have to traverse the loop an extra time to count its length.)
The running time is O(n). We can call this the Floyd-Balkany Algorithm.
|
|
|
|
|
Hi,
if you have the memory for a big hash table, you probably can also add a single bool to each
node (call it "visited"); initialize at false, test for false and set true on each visit,
until a true is revisited. No need for two pointers, and certainly not O(n^2).
However, not reentrant.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
But then you have to carry the overhead for the extra bool throughout the whole use of the linked list, instead of a one-time test.
|
|
|
|
|
bools aren't that expensive nowadays; of course they don't generate revenue when compared
to a sophisticated algorithm that carries your name...
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
What if, we want to reinitialize the boolean (to false),we'll need to traverse the list (hence getting caught in the loop)....it's like a Catch-22 situation...
Also, as mentioned,we have a large overhead...
here's a page i found... http://ostermiller.org/find_loop_singly_linked_list.html discussing some Incorrect "Solutions" (including the Boolean Method)...
But, still no Brent's Algorithm?? eh?  
modified 20-Oct-19 21:02pm.
|
|
|
|
|
st0le wrote: if we want to reinitialize the boolean (to false),we'll need to traverse the list
if you need it more than once, use one of the following:
1. a collection that allows you to iterate all the nodes without following the normal links;
2. a generation number that increments every time you start a cycle test; it gets initialized
only once (at node creation time), and it gets compared and stored during a cycle test.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Making 'b' the subject
square root( ( b+1 ) / b )= a
We know the answer is
1/(a<sup>2</sup> - 1)
Our workings
Get rid of square
(b+1) / b = a<sup>2</sup>
Then - get rid of single b
b+1 = b.a<sup>2</sup>
Then the 1
b = (b.a<sup>2</sup>) - 1
then..... stuck. No idea.
we tried
(b / a<sup>2</sup> -1 ) = b which is as near as I got.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
modified on Sunday, February 24, 2008 8:40 AM
|
|
|
|
|
|
Hi Malcolm,
Malcolm Smart wrote: My boys (not mine - honest!!)
Seems to me the difference is only a matter of time.
Malcolm Smart wrote: b+1 = b.a2
almost there. It is hard to believe you get stuck at this point.
Move all the terms containing b to one side, all other to the other and you get
b.a2 - b = 1
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Hi Luc! Had a sneeky feeling you might turn up.
Luc Pattyn wrote: Seems to me the difference is only a matter of time.
 Can't believe how much I've forgotten (or never knew!)
Luc Pattyn wrote: almost there. It is hard to believe you get stuck at this point.
Move all the terms containing b to one side, all other to the other and you get
b.a2 - b = 1
We've been here - we can't the get a2 - 1. You managed to tease an answer out me before regarding lemmings so I know you're not gonna give me the answer, but there is some obvious algebraic rule I am missing.
I need to get down to a single b on one side of the equation. If I take the a2 over to get 1/a2, I am left on the left hand side with b-b, which equals zero, so that seems wrong. We took the a2-b over, giving us b= 1/a2-b, which is very nearly there, except it should ne a2-1, not a2-b. (maths isn't my main thing - you can tell!)
My son is convinced the book is wrong - can you at least confirm
b = 1 / (a<sup>2</sup> - 1)
is correct?
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
|
I'll never forget those lemmings that approach a lethal ravine at high speed, suddenly
fall down strictly vertically, at a constant speed, and survive it all.
Malcolm Smart wrote: b = 1 / (a2 - 1)
is correct.
Fact: you can't "take a2-b over", taking over basically means you add something both
left and right in such a way that it cancels out something on one side. Now what would you add
to get rid of b.a2? certainly not a2!
Hint: if x.y = z how much is x? so try bringing your equation in a similar form.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
I either get b-b on the left, or b back on both sides!
(a2 = a2) <-- saves typing html tags for sup
b.a2-b=1
(b.a2)-b=1
b.a2 = 1 + b
b = (1 + b) / a2
but don't know how this then gets to
b = 1 / (a2 -1) There must be something so obvious I am missing, but I have to give up at this point (my son already has - he will learn soon that isn't an option sometimes in the real world) - my own work is pressing as I am having to work weekends at the moment. I will get this solved, but have to leave it until in the week.
Thanks Luc - appreciate your help.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
|
You can factor the lefthand side b.a2-b=1 into b and something,
then you have the form x.y=z which just requires a division.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Luc Pattyn wrote: You can factor the lefthand side b.a2-b=1 into b and something
Waheeeyyy!!! I just called him down and asked him to factorise
b.a2-b
b(a<sup>2</sup>-1) which gives
b(a<sup>2</sup>-1) = 1
b = 1 / (a<sup>2</sup> - 1) It's all about applying what he knows. He didn't think to factorise ( I didn't know you could!). Thanks a million Luc. He only has another 12 to do!! I'm going to have to really get into this stuff - it's actually quite cool.
so you answer don't be scared of failure
The only failure is never to try
Things You've Never Done - Passenger -2008
|
|
|
|
|
You're welcome.
Malcolm Smart wrote: It's all about applying what he knows
Of course. Don't apply what you don't know, but don't forget to apply what you do know; what is
the purpose of knowing something, if you don't apply it...
Malcolm Smart wrote: I'm going to have to really get into this stuff
Knowledge is hereditary, it will find its way up or down. 
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Of course this is probably way too late to help but...
The key here is that you need to isolate b
starting from your step:
(b+1) / b = a^2
this is equal to:
(b+1) * (1/b) = a^2
multiply out left side:
(b/b) + (1/b) = a^2
reduce (b/b):
1 + (1/b) = a^2
subtract 1 from both sides:
1/b = a^2 - 1
multiply both sides by b:
b/b = (a^2 - 1) * b
multiply both sides by 1/(a^2 -1):
(1/(a^2 - 1))*(b/b) = (a^2 - 1) * (1/(a^2 - 1)) * b
reduce both sides:
1/(a^2 - 1) = b
|
|
|
|
|
Simpler way
(b+1)/b=a^2
(b/b) + (1/b)=a^2
1 + (1/b) =a^2
(1/b)= a^2 - 1
=> b= 1/(a^2-1)
|
|
|
|
|
Thats the same thing as I posted. I just included all the steps that you left out which would be required by a math teacher who is actually teaching this stuff
Although I could have sworn that the entire other thread didn't exist from 2 weeks before walking them through it when I posted this....
|
|
|
|
|
Hello
Does anyone have a good idea of a decent line segment detection algorithm to be used on binary images (black and white)? The images are pages from newspapers, so they contain a lot of text.
The algorithm should detect almost straight vertical lines (maximum deviation of 5 degrees).
It should also be able to detect dotted lines, and some imperfect lines (with noise pixels, either white or black).
I've tried using Hough transform, but didn't get reasonable results.
Also tried some straight-forward methods, but they don't seem to give the same accuracy on different images.
I'm not so knowledgeable in this domain, and if there's someone to point me in the right direction, I would greatly appreciate it.
Thank you.
|
|
|
|
|
The Hough transform is probably the right approach, since it handles noise and imperfections. The problem is that the last step involves interpreting the transform results, which isn't straightforward.
It may help to do some noise removal before processing to get clearer results.
|
|
|
|
|
|
It looks very impressive. What does it do?
|
|
|
|
|
Found out about SheetCalculator[^] today.
Very nice!
There are II kinds of people in the world, those who understand binary and those who understand Roman numerals. Web - Blog - RSS - Math
|
|
|
|
|
Looks very interesting
"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon
|
|
|
|
|
Yeah, and the perfect excuse to learn Java.
There are II kinds of people in the world, those who understand binary and those who understand Roman numerals. Web - Blog - RSS - Math
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
