Anonymous user
Talk:Sattolo cycle: Difference between revisions
m
→Definition "each element ends up in a new position"
(remarks about the problem definition) |
|||
Line 29:
== Definition "each element ends up in a new position" ==
The definition "each element ends up in a new position" is insufficient. In addition to each element being in a new position, it also holds that the resulting permutation (of length ''n'') is a length-''n'' cycle (consult Wikipedia for explanation). Consider input <code>ABCD</code> and its permutation <code>BADC</code>. Each element is in a new position, yet the permutation is not a cycle, and therefore is not a valid output of Sattolo's algorithm.
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)
| |||