Floyd' Cycle Algorithm is just a way of detecting a cycle. You then
would have to find the exact beginning (and length, if you care), by
nosing around where the cycle was detected.
Linked lists are not essential. In your case you would have something like
'p v' =. ,@:(1&((>:`f`(f^:2))\))^:(~:/@}.)^:_ (0,y,y)
which would set p to the place where the cycle was detected, and v to
the value detected. Then carry on as required.
Henry Rich
On 11/22/2011 6:16 AM, David Vaughan wrote:
> I see that the algorithm you suggested only works on linked lists. Is there a
> way to model linked lists in J?
>
> On 20 Nov 2011, at 15:05, Henry Rich wrote:
>
>> You have to use ~. so that the list doesn't keep growing when a match is
>> found. ^:_ would run forever then, since it stops when two successive
>> results are identical.
>>
>> This method takes O(*:n) time because of the ~.@, . If that's a
>> problem, you might want to look into the very elegant Floyd's Cycle
>> Algorithm.
>>
>> Henry Rich
>>
>> On 11/20/2011 8:51 AM, David Vaughan wrote:
>>> This seems to have the behaviour I'm looking for, thanks.
>>>
>>> I don't understand why though. I can see that each result of f is being
>>> stored in a list as the verb is being applied each time, but I don't
>>> understand why ~.@, enables this.
>>>
>>> On 20 Nov 2011, at 13:31, Raul Miller wrote:
>>>
>>>> You can do
>>>> (~.@, f@{:)^:_ y
>>>>
>>>> But I am not sure how to work<x into this.
>>>>
>>>> --
>>>> Raul
>>>>
>>>> On Sun, Nov 20, 2011 at 5:36 AM, David Vaughan<[email protected]
>>>>> wrote:
>>>>
>>>>> If I'm doing f^:(<x) y, can I write an expression so that f is repeatedly
>>>>> applied to y until the result has come up before?
>>>>> ----------------------------------------------------------------------
>>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>>>
>>>> ----------------------------------------------------------------------
>>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>
>>> ----------------------------------------------------------------------
>>> For information about J forums see http://www.jsoftware.com/forums.htm
>>>
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
