Talk:Sattolo cycle

Yet another task needing a description

Linking to a wikipedia page really is not good enough. Those pages change over time, and are not written specifically for our site. Anyways, this task needs an adequate description. --Rdm (talk) 07:21, 5 September 2016 (UTC)

Done. --Smls (talk) 08:40, 5 September 2016 (UTC)

Not sure this is a worthwhile issue

Given that the Sattolo cycle is almost identical to the Knuth Shuffle - with the only difference being an otherwise invisible implementation detail - what makes this task worth doing?

Should we be looking forward to tasks like "bubble sort with descending iteration"? --Rdm (talk) 14:52, 5 September 2016 (UTC)

It's not invisible, as it affects the algorithm's behavior. For example, for [10, 20, 30] the Knuth shuffle has six possible outputs, but the Sattolo cycle only two, because it cannot output permutations that have elements in their original place. That makes it interesting, at least. I suppose the two algorithms could have been covered by a single combined task, but it's too late for that now that Knuth shuffle has existed for so long and has so many solutions. --Smls (talk) 17:19, 7 September 2016 (UTC)

Some formulae in Spec notes section invisible to most browsers

The majority of browsers (those which display server side graphic files for formulae, rather than using local MathML processing and locally installed fonts) are unable to display various formula elements in the Specification, particularly in its notes section. Unexpected content within <math> tags has choked the MediaWiki processor, leading it to generate syntactically ill-formed HTML - specifically tags which lack a semicolon between the height and vertical-align attributes. The unexpected content may include the use of naked < or > characters, or other anomalies such as redundant flanking space, or literal elements which do not constitute well-formed Latex. Hout (talk) 19:09, 21 September 2016 (UTC)

Visibility of task description math expressions now restored Hout (talk) 22:24, 24 November 2016 (UTC)

each element ends up in a new position

You need an array with at least two elements to make sure each element ends up in a new position. The single element in an array with one element cannot end up in new position. The possible output array shown for the test case [10] doesn't meet the task description, as all elements in that array did end up in their original position. Dedalus (talk) 12:29, 3 April 2017 (UTC)

The pseudocode in the task description performs this operation zero times for that case. The reason for this is the same reason it does not shuffle the two element array twice (resulting in an identity operation). --Rdm (talk) 15:39, 3 April 2017 (UTC)

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 ABCD and its permutation BADC. 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 i=3 (zero-indexed), D must be exchanged with C in order for C to be in the last position. Then in the next loop iteration, i=2 so j<2, and therefore, D (now in zero-indexed position 2) is necessarily exchanged with either A or B. So the result will never contain D in the penultimate position. This means the permutation BADC is impossible to obtain by the listed algorithm, and the definition "each element ends up in a new position" is not sufficient. --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.) --Rdm (talk) 02:04, 27 April 2020 (UTC)

AB -> BA -> AB is not a cycle; BA is. Similarly, ABCD -> BADC -> ABCD is not a cycle, but neither is BADC. If you 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). --Dick de Bill (talk) 14:14, 1 May 2020 (UTC)

I think you should re-read the wikipedia entry on cyclic permutations --Rdm (talk) 19:44, 1 May 2020 (UTC)

No Rdm, you should :) I see you're having trouble understanding that article, so let me quote the most relevant part for you:

(...) given X = {1, 2, 3, 4}, the permutation (1, 3, 2, 4) that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 (so S = X) is a 4-cycle, and the permutation (1, 3, 2) that sends 1 to 3, 3 to 2, 2 to 1 and 4 to 4 (so S = {1, 2, 3} and 4 is a fixed element) is a 3-cycle. On the other hand, the permutation that sends 1 to 3, 3 to 1, 2 to 4 and 4 to 2 is not a cyclic permutation because it separately permutes the pairs {1, 3} and {2, 4}.

You will notice that you can replace the set X = {1, 2, 3, 4} with X' = {A, C, B, D} and the above stated still holds. Then you can re-read the last sentence of the quoted text (in bold for emphasis, to show how it relates to the example I gave which you're confused about):

On the other hand, the permutation that sends A to B, B to A, C to D and D to C is not a cyclic permutation because it separately permutes the pairs {A, B} and {C, D}.

I hope it's all clear now. If not, write me a personal message or something... Dick de Bill (talk) 21:10, 1 May 2020 (UTC)

Which is the part which states that showing a sequence of permuted states for a cycle does not or cannot represent that cycle? --Rdm (talk) 23:02, 1 May 2020 (UTC)

Literally the first sentence of the article. It says "a cyclic permutation (or cycle) is a permutation of the elements". Meaning: BA is the cycle, not AB -> BA -> AB. Anyways, this point is moot; my complaint which you didn't understand was that BADC is not a cycle, and I believe that has been clarified. I see no reason to take this discussion any further. --Dick de Bill (talk) 00:18, 2 May 2020 (UTC)

BA is a cyclic permutation of AB, but it's not a cyclic permutation of BA. It's not usually necessary to emphasize this issue, but there are contexts where it can be important. Anyways, this has drifted away from the original point which is that there's a distinction between cycles and sattalo cycles, in the sense that some cycles are not sattalo cycles. --Rdm (talk) 01:05, 2 May 2020 (UTC)