Timeline for Cycle detection with Mathematica
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2020 at 5:59 | vote | accept | lesobrod | ||
| Aug 10, 2020 at 5:59 | answer | added | lesobrod | timeline score: 1 | |
| Aug 6, 2020 at 16:25 | comment | added | lesobrod |
@Bill Sorry, but in my case, we do not know in advance either the length of the cycle, or where it starts. So SequencePosition not work (
|
|
| Aug 6, 2020 at 15:52 | comment | added | lesobrod |
@J. M. First, the repetition of the same state is a cycle with a period 1, and it must be detected. NestWhileList do this. Secondly, I changed the test case, now it is period 2. Third, to see the difference of Timing, one should test matrices with size ~10^2 - 10^3
|
|
| Aug 6, 2020 at 15:50 | history | edited | lesobrod | CC BY-SA 4.0 |
added 107 characters in body
|
| Aug 6, 2020 at 13:33 | comment | added | J. M.'s missing motivation♦ | Your example doesn't exhibit cycling behavior. Could you perhaps give an example that does so? | |
| Aug 6, 2020 at 10:40 | history | edited | lesobrod | CC BY-SA 4.0 |
added 122 characters in body
|
| Aug 6, 2020 at 10:39 | comment | added | lesobrod | @J. M., all post completely rewritten | |
| Aug 6, 2020 at 10:38 | comment | added | lesobrod | @Bill timings are added. But what "-10" means? | |
| Aug 6, 2020 at 10:32 | history | edited | lesobrod | CC BY-SA 4.0 |
added 352 characters in body
|
| Aug 5, 2020 at 23:53 | comment | added | J. M.'s missing motivation♦ | I wrote up implementations of Floyd's and Brent's algorithms, but you don't seem to have provided a concrete example I could try them out on. | |
| Aug 5, 2020 at 16:43 | history | edited | lesobrod | CC BY-SA 4.0 |
added 398 characters in body
|
| Aug 5, 2020 at 16:30 | comment | added | flinty | Alternatively, if you need to avoid storing lots of data, you can run one process 1 step at a time and a copy of this process 2 steps at a time. At each stage check if their states are equal - then you know there's a cycle. This is like the old Tortoise and Hare trick with linked lists: en.wikipedia.org/wiki/… | |
| Aug 5, 2020 at 16:26 | comment | added | flinty |
Save the states in a list and use FindTransientRepeat. See here: mathematica.stackexchange.com/questions/175338/…
|
|
| Aug 5, 2020 at 16:16 | history | asked | lesobrod | CC BY-SA 4.0 |