Anonymous user
Talk:Sattolo cycle: Difference between revisions
corrected mistake, explained
No edit summary |
(corrected mistake, explained) |
||
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
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 38:
: 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)
:: 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)
| |||