Talk:Sattolo cycle: Difference between revisions

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, aka ''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 an ~~''n''-~~cycle, and therefore is not a valid output of Sattolo's algorithm.

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, aka ''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 (according to the Wikipedia definition), 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)

Line 39:

: 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)

:: <code>AB -> BA -> AB</code> is ''not'' a cycle; <code>BA</code> is. Similarly, <code>ABCD -> BADC -> ABCD</code> is not a cycle, but ''neither'' is <code>BADC</code>. If don't believe me, you can read the first paragraph of the Wikipedia page on cyclic permutations (I won't bother linking it; I trust you can find it yourself). [[User:Dick de Bill|Dick de Bill]] ([[User talk:Dick de Bill|talk]]) 14:11, 1 May 2020 (UTC)

:: I have made mistakenly said "it's not a cycle" when I should have said "it's not an ''n''-cycle". Anyway, let me paraphrase my original formulation and explain what I meant:

::: the resulting permutation (of length ''n'') is a length-''n'' cycle

:: Meaning, it is a single cycle of length ''n''. In the example you gave, BADC is a permutation of 4 elements, so ''n'' = 4. And indeed, BADC is ''not'' a single 4-cycle, but consists of two 2-cycles. I hope I've made that clear. [[User:Dick de Bill|Dick de Bill]] ([[User talk:Dick de Bill|talk]]) 14:02, 1 May 2020 (UTC)