Talk:Sattolo cycle: Difference between revisions
no edit summary
No edit summary |
|||
Line 32:
You can convince yourself of this by tracing the computation of the algorithm: at the beginning, when <code>i=3</code> (zero-indexed), <code>D</code> must be exchanged with <code>C</code> in order for <code>C</code> to be in the last position. Then in the next loop iteration, <code>i=2</code> so <code>j<2</code>, and therefore, <code>D</code> (now in zero-indexed position 2) is necessarily exchanged with either <code>A</code> or <code>B</code>. So the result will never contain <code>D</code> in the penultimate position. This means the permutation <code>BADC</code> is impossible to obtain by the listed algorithm, and the definition "each element ends up in a new position" is not sufficient. --[[User:Dick de Bill|Dick de Bill]] ([[User talk:Dick de Bill|talk]]) 17:44, 26 April 2020 (UTC)
: I think your writeup here has some room for improvement. Specifically: AB -> BA -> AB is a cycle with two unique elements, and CD -> DC -> CD is a cycle with two unique elements, so AB CD -> BA DC -> AB CD is a cycle with two unique elements (with the space added for emphasis, and to show how this relates to the previous ones). That said, you would be right that ABCD -> BADC is not a result which can be produced by this task's Sattolo Cycle algorithm (because j is constrained to be strictly less than i).
: In other words... I think the statement "The Sattolo cycle is an algorithm for randomly shuffling an array in such a way that each element ends up in a new position" should be taken as meaning that the algorithm shuffles an array and guarantees that each element ends up in a new position -- it does not guarantee that it will generate all possible results where each element ends up in a new position. Or, put different -- that's not a definition of the algorithm, it's instead a summary description of the algorithm.
: But, it's true also that it would be nice if there were some concise way of describing all possible results which wasn't the algorithm itself. (And, thanks for calling attention to that issue.) --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 02:04, 27 April 2020 (UTC)
| |||