Mathematics desk
< May 8	<< Apr \| May \| Jun >>	May 10 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 9

Puzzle: order a digit sequence by reversing initial subsequences

(Note: this isn't homework. I'm trying to solve an old ZX Spectrum computer game.)

Could someone please advise on an optimal strategy for this puzzle? Thanks.

We are given a jumbled sequence of the ten digits, e.g. 8053641279.
We want to order this sequence, i.e. produce 0123456789.
Our only permissible move is to reverse a subsequence of length n that starts at the beginning. So in my example, I might choose to reverse for n=5, which would reverse the first five digits and yield 6350841279.

2A00:23C5:FE0C:2100:6C82:680C:F7DD:B0C9 (talk) 02:32, 9 May 2020 (UTC)[reply]

This is the pancake sorting problem; see there for some more information. There are still some open questions about optimality, so I'm not sure what kind of algorithm other than brute force would be able to do best for a specific jumble. OEIS: A058986 gives that 11 flips are always sufficient for 10 numbers. –Deacon Vorbis (carbon • videos) 02:45, 9 May 2020 (UTC)[reply]

8053641279

7214635089

0536412789

6350412789

2140536789

5041236789

3214056789

4123056789

0321456789

3021456789

1203456789

2103456789

0123456789

Not the optimal solution but the method used should be straightforward to work out. --RDBury (talk) 04:48, 9 May 2020 (UTC)[reply]

Selection sort is not optimal, but it is easy to understand and execute for a relatively short string like this. —SeekingAnswers (reply) 12:59, 9 May 2020 (UTC)[reply]

Article improvement: Pancake sorting

From the Pancake sorting lede, with emphasis added:

It is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence. Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom.

I'm fine with "variant" in the second sentence above, but "variation" in the first seems incorrect. I was going to substitute equivalent to for a variation of, but wanted to check here that I wasn't missing something. -- ToE 08:56, 14 May 2020 (UTC)[reply]

It's not a variation or any like thing of the problem, but an approach to getting a solution which has certain restrictions. The leter use of "variant" is exactly the right word.2A00:23C6:AA08:E500:445C:8CB2:E9E:9DDD (talk) 10:12, 15 May 2020 (UTC)[reply]

Pardon me, but I'm not following you. I've no problem with the latter use of ~~"vairant"~~ ~~"varmint"~~ "variant". My point is that pancake sorting is isomorphic to "the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence", and thus equivalent to is more correct than a variation of. Are you saying otherwise? -- ToE 10:33, 15 May 2020 (UTC) ... and in my mind a "variation" implies a difference beyond simple isomorphism, but I sometimes read too much into colloquial terms within a mathematical context. -- ToE 17:59, 15 May 2020 (UTC)[reply]

vairant ≠ variant :) --CiaPan (talk) 12:20, 15 May 2020 (UTC)[reply]