16,001,721 members
See more:
Note: In Chris' absence[^] I've stepped up to post this week's challenge. Enjoy!

Consider a randomized list of the integers 1 to N. You want to sort it using only the following actions:

Swap the first and last list elements. (S)
Pop off the first element and append it to the end of the list. (P)

Using S and P you can swap any adjacent elements by calling P until the two elements in question are the first and last items in the list, then calling S to swap them, then calling P again until they are in the original indices (now swapped).

Create a method that takes in a permutation of the numbers from 1 to N (N > 1). It can be given as a list or string or whatever is convenient. It should output a sequence of S's and P's that would sort the permutation when applied from left to right. This sequence does not have to be optimally short, but shorter it is the better.

You may not hard code your program to suit any data.

What I have tried:

Example

If the input was [2, 1, 3] the output might be SP because

S applied to [2, 1, 3] makes it [3, 1, 2],
and P applied to [3, 1, 2] makes it [1, 2, 3], which is sorted.

Test data
```1. Length 3
[2, 1, 3]
2. Length 7
[2, 7, 5, 3, 4, 6, 1]
3. Length 41
[7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34]
4. Length 52
[19, 49, 34, 26, 38, 3, 14, 37, 21, 39, 46, 29, 18, 6, 15, 25, 28, 47, 22, 41, 32, 51, 50, 5, 45, 4, 30, 44, 10, 43, 20, 17, 13, 36, 48, 27, 35, 24, 8, 12, 40, 2, 1, 16, 7, 31, 23, 33, 42, 52, 9, 11]
5. Length 65
[12, 53, 4, 5, 17, 32, 58, 54, 18, 43, 21, 26, 51, 45, 9, 2, 35, 28, 40, 61, 57, 27, 62, 39, 24, 59, 36, 25, 20, 33, 63, 56, 64, 47, 38, 7, 13, 34, 16, 30, 49, 22, 37, 3, 48, 11, 52, 1, 29, 42, 50, 23, 6, 8, 60, 65, 46, 10, 41, 31, 44, 15, 14, 19, 55]
6. Length 69
[58, 15, 63, 18, 24, 59, 26, 37, 44, 67, 14, 52, 2, 31, 68, 54, 32, 17, 55, 50, 42, 56, 65, 29, 13, 41, 7, 45, 53, 35, 21, 39, 61, 23, 49, 12, 60, 46, 27, 57, 28, 40, 10, 69, 1, 6, 19, 62, 8, 30, 64, 34, 3, 43, 38, 20, 25, 33, 66, 47, 4, 36, 16, 11, 5, 22, 51, 48, 9]
7. Length 75
[14, 69, 1, 43, 32, 42, 59, 37, 70, 63, 57, 60, 56, 73, 67, 6, 11, 36, 31, 22, 40, 7, 21, 35, 50, 64, 28, 41, 18, 17, 75, 54, 51, 19, 68, 33, 45, 61, 66, 52, 49, 65, 4, 72, 23, 34, 9, 15, 38, 16, 3, 71, 29, 30, 48, 53, 10, 8, 13, 47, 20, 55, 74, 27, 25, 62, 46, 24, 44, 39, 2, 26, 58, 12, 5]
8. Length 80
[3, 65, 44, 14, 19, 6, 11, 29, 79, 35, 42, 16, 68, 7, 62, 30, 38, 46, 15, 9, 75, 5, 52, 32, 22, 70, 64, 13, 21, 47, 10, 4, 55, 40, 45, 56, 77, 27, 23, 72, 17, 71, 53, 20, 18, 25, 73, 59, 36, 34, 37, 57, 1, 69, 24, 58, 33, 76, 2, 12, 49, 61, 78, 67, 66, 63, 50, 80, 28, 48, 26, 51, 41, 60, 31, 54, 39, 8, 74, 43]
9. Length 103
[40, 62, 53, 6, 32, 85, 8, 83, 33, 29, 87, 93, 22, 37, 80, 12, 74, 69, 64, 9, 18, 98, 17, 45, 60, 38, 10, 103, 19, 5, 54, 15, 90, 100, 79, 91, 46, 82, 43, 31, 51, 96, 30, 70, 76, 16, 55, 77, 11, 65, 58, 75, 61, 3, 28, 24, 101, 20, 41, 72, 86, 56, 35, 50, 78, 27, 67, 95, 44, 68, 48, 26, 39, 97, 21, 49, 102, 73, 63, 7, 71, 52, 1, 88, 34, 42, 14, 47, 36, 99, 4, 13, 94, 89, 59, 92, 57, 25, 23, 66, 81, 2, 84]
10. Length 108
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108]
11. Length 109
[48, 89, 25, 64, 8, 69, 81, 98, 107, 61, 106, 63, 59, 50, 83, 24, 86, 68, 100, 104, 56, 88, 46, 62, 94, 4, 47, 33, 19, 1, 77, 102, 9, 30, 44, 26, 16, 80, 67, 75, 70, 96, 108, 45, 79, 51, 12, 38, 73, 37, 65, 31, 60, 22, 28, 3, 43, 71, 105, 91, 93, 101, 13, 97, 29, 72, 82, 87, 27, 5, 17, 10, 34, 84, 53, 15, 78, 41, 85, 6, 14, 57, 76, 7, 23, 99, 32, 95, 49, 2, 21, 109, 74, 39, 11, 103, 18, 90, 35, 40, 58, 20, 55, 52, 36, 54, 42, 92, 66]
12. Length 151
[61, 7, 8, 79, 78, 4, 48, 13, 14, 117, 12, 96, 130, 118, 63, 110, 72, 57, 86, 126, 62, 10, 29, 102, 99, 28, 56, 135, 11, 151, 141, 97, 45, 109, 38, 150, 40, 149, 52, 140, 106, 80, 66, 134, 125, 137, 31, 85, 68, 94, 36, 26, 95, 92, 49, 25, 120, 148, 33, 73, 41, 100, 58, 127, 60, 122, 133, 9, 19, 81, 59, 55, 103, 146, 42, 21, 128, 75, 101, 82, 50, 142, 131, 76, 20, 69, 139, 83, 16, 64, 17, 124, 90, 138, 37, 1, 34, 43, 129, 77, 23, 35, 144, 121, 113, 115, 114, 67, 98, 70, 145, 104, 71, 5, 119, 6, 18, 88, 116, 111, 132, 39, 89, 24, 15, 107, 27, 65, 30, 47, 143, 93, 53, 108, 2, 74, 123, 44, 51, 54, 87, 147, 84, 3, 112, 46, 32, 91, 136, 22, 105]
13. Length 173
[93, 14, 141, 125, 64, 30, 24, 85, 44, 68, 91, 22, 103, 155, 117, 114, 123, 51, 131, 72, 67, 61, 5, 41, 10, 20, 129, 86, 154, 108, 161, 2, 82, 153, 96, 50, 136, 121, 128, 126, 120, 111, 89, 113, 104, 84, 18, 109, 42, 83, 162, 124, 173, 116, 12, 54, 52, 39, 122, 49, 46, 1, 130, 71, 152, 73, 56, 34, 149, 75, 133, 8, 74, 45, 88, 23, 7, 60, 115, 134, 53, 119, 106, 81, 112, 31, 35, 172, 159, 38, 59, 69, 142, 146, 110, 170, 160, 166, 43, 58, 4, 107, 78, 156, 47, 33, 145, 63, 163, 27, 70, 77, 36, 16, 100, 26, 19, 151, 57, 32, 15, 13, 40, 169, 98, 132, 135, 62, 66, 90, 102, 171, 99, 148, 80, 144, 147, 168, 94, 143, 17, 3, 140, 97, 11, 65, 55, 92, 95, 127, 167, 150, 87, 118, 28, 137, 9, 29, 105, 157, 25, 165, 158, 21, 164, 101, 79, 76, 6, 138, 48, 37, 139]
14. Length 177
[68, 117, 61, 159, 110, 148, 3, 20, 169, 145, 136, 1, 120, 109, 21, 58, 52, 97, 65, 168, 34, 134, 111, 176, 13, 156, 172, 53, 55, 124, 177, 88, 92, 23, 72, 26, 104, 121, 133, 73, 39, 140, 25, 71, 119, 158, 146, 128, 18, 94, 113, 45, 60, 96, 30, 5, 116, 153, 90, 115, 67, 80, 112, 154, 9, 17, 10, 33, 81, 38, 95, 118, 35, 160, 151, 150, 76, 77, 14, 147, 173, 135, 162, 114, 27, 100, 167, 74, 69, 165, 108, 79, 91, 48, 105, 125, 129, 75, 93, 11, 12, 64, 24, 170, 142, 98, 44, 37, 43, 78, 16, 28, 166, 155, 138, 164, 122, 163, 107, 130, 86, 56, 2, 161, 63, 126, 131, 144, 82, 106, 103, 32, 132, 54, 41, 171, 70, 85, 19, 143, 137, 87, 84, 66, 99, 102, 15, 49, 123, 175, 89, 51, 141, 62, 50, 36, 152, 47, 42, 8, 7, 46, 29, 22, 149, 139, 4, 40, 83, 6, 59, 57, 174, 31, 127, 101, 157]
15. Length 192
[82, 130, 189, 21, 169, 147, 160, 66, 133, 153, 143, 116, 49, 13, 63, 61, 94, 164, 35, 112, 141, 62, 87, 171, 19, 3, 93, 83, 149, 64, 34, 170, 129, 182, 101, 77, 14, 91, 145, 23, 32, 92, 187, 54, 184, 120, 109, 159, 27, 44, 60, 103, 134, 52, 122, 33, 78, 88, 108, 45, 15, 79, 137, 80, 161, 69, 6, 139, 110, 67, 43, 190, 152, 59, 173, 125, 168, 37, 151, 132, 1, 178, 20, 114, 119, 144, 25, 146, 42, 136, 162, 123, 31, 107, 131, 127, 51, 105, 2, 65, 28, 102, 76, 24, 135, 174, 9, 111, 98, 39, 74, 142, 70, 121, 154, 38, 113, 75, 40, 86, 100, 106, 181, 117, 95, 85, 138, 41, 167, 172, 4, 186, 17, 16, 104, 71, 81, 73, 57, 8, 140, 118, 158, 12, 148, 53, 29, 185, 18, 150, 22, 188, 72, 128, 84, 96, 47, 192, 126, 56, 163, 50, 157, 165, 97, 166, 180, 7, 46, 30, 191, 124, 5, 48, 175, 68, 36, 89, 177, 11, 176, 183, 99, 90, 55, 26, 10, 58, 115, 155, 179, 156]
16. Length 201
[23, 8, 58, 24, 19, 87, 98, 187, 17, 130, 116, 141, 129, 166, 29, 191, 81, 105, 137, 171, 39, 67, 46, 150, 102, 26, 163, 183, 170, 72, 160, 43, 9, 197, 189, 173, 196, 68, 100, 16, 93, 175, 74, 28, 133, 122, 27, 79, 107, 162, 62, 192, 108, 104, 97, 12, 60, 155, 161, 82, 167, 158, 149, 30, 124, 22, 168, 115, 134, 94, 34, 184, 127, 121, 177, 112, 142, 95, 164, 41, 59, 55, 143, 85, 176, 3, 156, 148, 153, 42, 180, 145, 78, 147, 119, 109, 139, 178, 61, 181, 136, 157, 91, 84, 47, 71, 70, 118, 18, 63, 80, 56, 123, 194, 117, 195, 152, 66, 48, 11, 99, 201, 128, 151, 138, 64, 21, 131, 159, 103, 75, 49, 169, 113, 53, 114, 69, 54, 165, 38, 101, 76, 200, 199, 140, 125, 193, 88, 32, 51, 126, 14, 13, 77, 52, 50, 198, 172, 5, 92, 96, 15, 106, 182, 31, 83, 120, 57, 135, 65, 7, 154, 20, 25, 45, 1, 6, 73, 40, 174, 132, 10, 111, 186, 190, 4, 36, 188, 185, 146, 44, 110, 179, 2, 90, 86, 35, 37, 33, 89, 144]
17. Length 201
[97, 146, 168, 5, 56, 147, 189, 92, 154, 13, 185, 109, 45, 126, 17, 10, 53, 98, 88, 41, 163, 99, 157, 35, 125, 34, 173, 171, 138, 104, 149, 172, 60, 183, 36, 65, 32, 180, 87, 167, 59, 84, 188, 11, 69, 57, 174, 61, 66, 7, 8, 111, 91, 58, 128, 94, 141, 139, 31, 78, 156, 70, 16, 162, 26, 33, 106, 175, 103, 21, 164, 110, 159, 80, 200, 82, 123, 144, 44, 148, 4, 55, 179, 184, 186, 124, 63, 107, 54, 112, 137, 165, 121, 25, 132, 196, 90, 89, 71, 160, 95, 117, 197, 37, 108, 39, 115, 12, 52, 119, 120, 79, 29, 49, 93, 22, 122, 161, 76, 38, 72, 169, 85, 178, 77, 105, 190, 100, 9, 86, 177, 194, 2, 136, 114, 51, 68, 19, 47, 195, 113, 193, 67, 96, 182, 170, 50, 83, 143, 166, 3, 192, 24, 127, 140, 176, 134, 158, 116, 199, 1, 135, 118, 145, 14, 15, 155, 48, 42, 73, 46, 102, 191, 28, 201, 181, 75, 133, 153, 6, 131, 130, 81, 20, 198, 64, 142, 150, 27, 101, 18, 30, 40, 23, 129, 43, 62, 187, 152, 151, 74]
18. Length 205
[161, 197, 177, 118, 94, 112, 13, 190, 200, 166, 127, 80, 115, 204, 186, 60, 50, 97, 175, 32, 26, 65, 16, 4, 55, 120, 143, 187, 121, 29, 18, 82, 17, 21, 144, 20, 88, 195, 99, 67, 203, 23, 176, 126, 137, 77, 70, 30, 103, 182, 113, 119, 36, 47, 90, 98, 54, 3, 49, 105, 57, 135, 153, 142, 174, 155, 158, 11, 157, 22, 171, 110, 28, 196, 129, 163, 79, 63, 38, 145, 140, 2, 128, 180, 106, 59, 25, 184, 81, 164, 95, 39, 68, 78, 178, 156, 72, 51, 202, 66, 48, 101, 71, 108, 130, 5, 107, 147, 199, 12, 27, 150, 167, 91, 64, 170, 191, 151, 149, 168, 34, 125, 188, 181, 139, 58, 75, 189, 124, 152, 183, 7, 111, 89, 84, 52, 141, 83, 69, 62, 73, 43, 123, 14, 179, 162, 114, 138, 117, 159, 74, 85, 10, 96, 86, 31, 132, 1, 104, 109, 45, 165, 148, 172, 154, 92, 173, 40, 19, 56, 37, 205, 44, 193, 122, 185, 93, 133, 53, 9, 169, 6, 61, 136, 46, 76, 33, 15, 116, 198, 160, 194, 131, 41, 42, 35, 146, 134, 192, 8, 87, 201, 100, 24, 102]
19. Length 211
[200, 36, 204, 198, 190, 161, 57, 108, 180, 203, 135, 48, 134, 47, 158, 10, 41, 11, 23, 127, 167, 121, 109, 211, 201, 1, 42, 40, 86, 104, 147, 139, 145, 101, 144, 166, 176, 92, 118, 54, 182, 30, 58, 123, 124, 67, 125, 154, 187, 168, 103, 17, 72, 98, 12, 184, 59, 87, 174, 93, 45, 116, 73, 69, 74, 80, 56, 14, 34, 85, 38, 185, 165, 110, 164, 151, 43, 192, 62, 4, 140, 170, 197, 111, 173, 141, 65, 77, 70, 136, 206, 83, 100, 148, 25, 183, 209, 189, 150, 33, 46, 16, 64, 114, 71, 102, 91, 39, 177, 196, 169, 128, 129, 44, 75, 188, 146, 26, 84, 138, 162, 194, 105, 37, 35, 88, 156, 130, 193, 19, 179, 82, 106, 181, 153, 28, 53, 21, 195, 66, 159, 115, 113, 112, 191, 172, 63, 143, 178, 94, 160, 186, 31, 29, 90, 68, 205, 155, 119, 117, 157, 107, 60, 79, 171, 149, 6, 24, 27, 50, 51, 126, 15, 133, 2, 131, 7, 49, 207, 163, 18, 120, 199, 61, 52, 32, 208, 20, 210, 13, 78, 55, 137, 202, 152, 8, 81, 76, 9, 97, 22, 99, 132, 95, 122, 89, 175, 5, 3, 96, 142]
20. Length 226
[204, 79, 88, 98, 197, 32, 40, 117, 153, 167, 29, 74, 170, 115, 127, 210, 22, 109, 65, 47, 41, 132, 110, 158, 192, 99, 96, 224, 190, 143, 33, 225, 195, 19, 70, 73, 54, 161, 75, 179, 181, 207, 26, 221, 66, 130, 152, 131, 30, 35, 155, 69, 68, 38, 129, 95, 116, 214, 7, 186, 62, 27, 212, 125, 216, 86, 148, 164, 141, 4, 140, 222, 16, 46, 12, 215, 78, 219, 211, 134, 118, 171, 121, 52, 123, 56, 220, 15, 25, 100, 137, 163, 51, 91, 10, 83, 55, 187, 182, 201, 149, 160, 8, 14, 218, 77, 3, 184, 114, 43, 122, 135, 142, 104, 120, 198, 45, 108, 85, 189, 151, 175, 136, 165, 226, 97, 124, 200, 60, 172, 20, 67, 1, 174, 87, 102, 119, 188, 223, 199, 103, 89, 49, 213, 57, 9, 101, 112, 36, 176, 194, 92, 145, 180, 168, 111, 94, 178, 39, 166, 193, 17, 2, 154, 58, 156, 217, 13, 80, 202, 206, 169, 107, 177, 144, 205, 139, 93, 34, 64, 106, 150, 146, 126, 185, 208, 63, 203, 105, 18, 191, 53, 183, 209, 6, 23, 84, 5, 61, 59, 162, 128, 37, 50, 28, 159, 173, 196, 24, 31, 72, 138, 82, 48, 133, 147, 42, 113, 81, 90, 71, 21, 11, 157, 76, 44]
21. Length 227
[197, 52, 91, 42, 29, 113, 82, 68, 147, 225, 80, 167, 117, 142, 140, 216, 65, 195, 97, 61, 133, 209, 214, 58, 152, 71, 56, 182, 201, 163, 227, 186, 63, 171, 207, 102, 161, 136, 224, 146, 92, 175, 45, 217, 6, 99, 20, 119, 210, 93, 77, 211, 21, 70, 90, 96, 115, 100, 183, 173, 69, 98, 172, 75, 111, 203, 19, 129, 35, 155, 74, 37, 23, 51, 192, 212, 33, 64, 59, 194, 112, 135, 1, 184, 5, 166, 185, 84, 199, 138, 144, 86, 128, 26, 190, 73, 179, 27, 118, 223, 46, 95, 159, 153, 226, 25, 180, 132, 189, 60, 32, 208, 123, 89, 87, 22, 181, 143, 47, 18, 198, 219, 156, 148, 193, 122, 110, 28, 106, 39, 30, 103, 4, 176, 114, 3, 131, 107, 204, 218, 141, 169, 16, 206, 36, 188, 174, 54, 94, 50, 205, 104, 170, 160, 72, 165, 78, 24, 222, 8, 108, 81, 76, 15, 13, 126, 79, 7, 105, 125, 162, 83, 41, 145, 139, 66, 127, 38, 12, 187, 130, 221, 48, 164, 191, 157, 88, 168, 196, 10, 9, 53, 124, 150, 31, 116, 49, 34, 200, 134, 220, 121, 2, 62, 149, 158, 101, 17, 202, 11, 109, 85, 55, 67, 120, 43, 154, 44, 215, 177, 178, 40, 57, 14, 213, 151, 137]
22. Length 230
[69, 204, 215, 61, 97, 149, 9, 11, 137, 71, 37, 219, 92, 115, 156, 159, 200, 222, 3, 89, 172, 177, 203, 45, 54, 82, 147, 176, 168, 6, 26, 81, 25, 132, 212, 70, 228, 122, 225, 141, 100, 12, 124, 30, 146, 73, 19, 49, 52, 62, 217, 166, 191, 102, 163, 50, 181, 7, 134, 58, 76, 199, 179, 169, 197, 108, 174, 22, 186, 171, 114, 103, 173, 68, 65, 4, 13, 117, 64, 10, 126, 77, 206, 133, 121, 60, 40, 38, 59, 178, 224, 211, 187, 80, 220, 140, 8, 34, 130, 41, 95, 105, 227, 66, 210, 180, 192, 106, 209, 107, 157, 188, 170, 101, 131, 87, 14, 165, 78, 182, 136, 193, 190, 20, 67, 125, 36, 5, 145, 218, 99, 138, 154, 16, 29, 152, 194, 53, 148, 93, 202, 229, 198, 109, 43, 214, 150, 51, 128, 216, 1, 83, 196, 135, 74, 119, 75, 42, 142, 72, 226, 185, 116, 162, 63, 2, 112, 33, 184, 158, 15, 213, 144, 223, 98, 57, 160, 143, 90, 44, 205, 35, 21, 48, 151, 85, 123, 32, 47, 39, 189, 161, 56, 207, 84, 94, 230, 46, 164, 113, 175, 18, 195, 110, 127, 96, 129, 88, 17, 153, 104, 91, 86, 31, 118, 111, 120, 201, 28, 221, 23, 139, 24, 27, 167, 208, 183, 155, 79, 55]
23. Length 238
[202, 18, 122, 135, 11, 57, 103, 35, 86, 2, 84, 232, 208, 186, 54, 77, 145, 101, 105, 137, 210, 234, 207, 93, 55, 63, 230, 66, 160, 10, 223, 36, 34, 216, 104, 174, 121, 25, 166, 75, 167, 176, 61, 32, 118, 89, 68, 5, 14, 27, 204, 99, 149, 88, 91, 222, 37, 144, 108, 78, 128, 131, 190, 17, 65, 168, 225, 165, 41, 49, 38, 72, 43, 147, 158, 74, 130, 7, 82, 64, 97, 69, 100, 22, 152, 85, 48, 33, 218, 47, 228, 113, 40, 185, 219, 112, 180, 120, 4, 213, 179, 194, 51, 96, 221, 44, 238, 31, 117, 114, 229, 81, 164, 193, 236, 26, 59, 30, 151, 12, 115, 170, 24, 70, 227, 159, 133, 52, 134, 203, 15, 197, 155, 83, 50, 111, 195, 139, 109, 127, 188, 87, 62, 157, 226, 142, 98, 76, 211, 138, 58, 140, 198, 220, 16, 46, 183, 107, 106, 29, 163, 173, 209, 217, 215, 1, 177, 233, 199, 110, 172, 23, 212, 79, 94, 102, 39, 20, 178, 150, 175, 119, 8, 13, 42, 156, 201, 73, 200, 124, 53, 161, 92, 123, 224, 143, 196, 28, 9, 6, 80, 56, 148, 125, 214, 60, 171, 153, 231, 181, 205, 19, 95, 206, 154, 132, 169, 116, 3, 126, 187, 162, 191, 67, 136, 45, 192, 189, 235, 129, 21, 141, 237, 184, 90, 146, 182, 71]
24. Length 241
[2, 33, 49, 83, 207, 204, 13, 57, 115, 86, 102, 219, 232, 44, 177, 197, 171, 227, 191, 10, 25, 162, 62, 11, 76, 214, 163, 201, 130, 91, 233, 194, 112, 179, 66, 139, 183, 116, 196, 193, 150, 211, 30, 144, 209, 97, 174, 3, 68, 38, 120, 165, 56, 64, 87, 15, 79, 131, 206, 96, 188, 7, 99, 195, 129, 8, 186, 78, 212, 125, 161, 230, 225, 239, 47, 107, 53, 218, 164, 106, 198, 215, 181, 226, 6, 175, 167, 236, 67, 80, 210, 128, 155, 40, 63, 74, 113, 89, 18, 190, 124, 221, 59, 149, 103, 42, 156, 157, 200, 168, 34, 77, 65, 146, 5, 187, 222, 231, 140, 141, 172, 234, 100, 94, 132, 237, 24, 216, 152, 22, 51, 69, 35, 43, 105, 23, 61, 1, 72, 135, 104, 9, 12, 21, 46, 192, 159, 205, 158, 109, 28, 98, 50, 122, 111, 71, 166, 229, 37, 114, 173, 134, 136, 81, 121, 185, 118, 223, 20, 14, 108, 82, 178, 54, 26, 153, 36, 39, 117, 147, 95, 90, 16, 17, 170, 119, 199, 19, 84, 213, 88, 93, 151, 4, 101, 142, 110, 184, 55, 138, 75, 133, 148, 145, 45, 70, 217, 143, 224, 241, 31, 240, 182, 52, 238, 126, 85, 154, 137, 160, 27, 180, 60, 29, 32, 169, 235, 123, 176, 48, 220, 203, 228, 127, 41, 58, 73, 92, 189, 202, 208]
25. Length 241
[105, 160, 132, 32, 10, 117, 76, 2, 190, 108, 178, 51, 71, 237, 232, 47, 14, 124, 100, 31, 169, 196, 8, 184, 21, 151, 223, 86, 42, 127, 55, 58, 229, 4, 219, 46, 238, 179, 24, 194, 203, 122, 66, 15, 81, 146, 172, 106, 129, 135, 216, 120, 92, 231, 144, 195, 181, 162, 69, 45, 137, 136, 9, 30, 5, 188, 91, 49, 147, 233, 198, 17, 241, 163, 36, 18, 183, 59, 16, 29, 116, 182, 41, 48, 23, 39, 154, 210, 68, 167, 95, 213, 79, 225, 37, 157, 109, 143, 78, 142, 173, 155, 200, 110, 20, 73, 141, 168, 156, 126, 150, 201, 114, 1, 230, 211, 217, 131, 140, 204, 209, 149, 103, 199, 165, 175, 35, 107, 74, 63, 193, 239, 218, 234, 197, 224, 174, 121, 60, 88, 22, 171, 133, 207, 152, 34, 43, 228, 125, 115, 101, 7, 12, 220, 82, 153, 134, 52, 130, 70, 72, 44, 177, 89, 65, 98, 94, 53, 208, 227, 161, 3, 123, 236, 221, 87, 102, 50, 90, 180, 185, 186, 67, 77, 26, 212, 27, 222, 6, 145, 11, 13, 84, 25, 164, 64, 85, 139, 214, 189, 61, 96, 191, 128, 93, 138, 148, 19, 119, 202, 75, 176, 159, 56, 104, 206, 40, 187, 215, 62, 166, 240, 112, 226, 170, 83, 97, 57, 99, 38, 28, 113, 205, 158, 235, 111, 54, 192, 118, 80, 33]
26. Length 244
[89, 13, 154, 161, 235, 225, 92, 188, 215, 194, 54, 58, 128, 21, 165, 85, 144, 205, 142, 77, 109, 24, 83, 69, 72, 7, 224, 240, 191, 204, 183, 203, 68, 70, 63, 95, 206, 170, 153, 180, 45, 178, 35, 27, 190, 132, 222, 41, 40, 156, 97, 20, 217, 177, 167, 65, 23, 136, 216, 234, 38, 201, 236, 164, 82, 241, 10, 141, 148, 229, 5, 125, 113, 159, 193, 187, 130, 179, 52, 108, 86, 196, 174, 123, 56, 116, 227, 30, 239, 98, 186, 67, 135, 118, 163, 43, 32, 50, 231, 226, 232, 172, 200, 99, 6, 143, 39, 93, 107, 34, 129, 157, 100, 127, 15, 84, 81, 73, 121, 220, 44, 8, 57, 105, 91, 171, 162, 211, 244, 104, 112, 238, 212, 133, 71, 192, 145, 160, 87, 181, 60, 184, 119, 4, 55, 96, 53, 12, 213, 124, 94, 22, 42, 3, 48, 131, 117, 140, 138, 228, 219, 155, 59, 29, 202, 169, 114, 101, 47, 233, 176, 139, 207, 33, 79, 16, 51, 66, 75, 90, 198, 168, 166, 31, 151, 49, 208, 150, 111, 14, 25, 197, 17, 76, 80, 78, 9, 173, 26, 137, 19, 120, 199, 106, 152, 88, 147, 36, 158, 28, 243, 221, 110, 74, 175, 237, 61, 2, 62, 214, 189, 134, 195, 218, 18, 102, 46, 103, 11, 122, 146, 185, 182, 209, 1, 149, 115, 64, 37, 126, 230, 223, 242, 210]
27. Length 246
[28, 186, 214, 18, 220, 73, 20, 88, 234, 187, 27, 102, 22, 129, 10, 228, 196, 56, 47, 2, 16, 67, 124, 137, 177, 179, 223, 147, 188, 23, 103, 109, 149, 60, 229, 99, 222, 90, 49, 80, 158, 93, 171, 71, 175, 143, 19, 212, 40, 226, 219, 120, 146, 66, 167, 232, 94, 174, 237, 9, 173, 70, 122, 241, 58, 82, 191, 211, 180, 104, 53, 36, 83, 37, 131, 25, 162, 32, 210, 144, 145, 69, 135, 63, 154, 165, 46, 57, 50, 74, 128, 140, 112, 118, 125, 231, 221, 233, 95, 200, 153, 6, 166, 98, 208, 91, 89, 141, 4, 26, 134, 86, 8, 30, 157, 156, 224, 201, 243, 7, 161, 1, 84, 115, 44, 230, 78, 79, 5, 17, 194, 148, 152, 121, 193, 107, 240, 181, 29, 43, 65, 164, 45, 110, 64, 195, 216, 127, 59, 197, 178, 151, 139, 85, 75, 11, 204, 184, 77, 54, 51, 205, 108, 142, 130, 138, 238, 87, 38, 101, 96, 31, 215, 244, 242, 172, 213, 136, 97, 35, 39, 76, 42, 245, 123, 227, 24, 168, 33, 159, 217, 239, 55, 176, 68, 207, 106, 132, 15, 116, 61, 198, 62, 182, 225, 202, 105, 150, 183, 81, 170, 13, 41, 199, 3, 185, 235, 14, 155, 21, 126, 119, 169, 72, 12, 236, 48, 209, 190, 113, 218, 100, 52, 111, 189, 92, 192, 114, 117, 160, 133, 203, 163, 34, 206, 246]
28. Length 250
[119, 57, 59, 181, 212, 120, 236, 121, 99, 247, 138, 187, 175, 108, 107, 197, 123, 101, 141, 77, 201, 3, 52, 60, 56, 240, 157, 39, 42, 199, 23, 18, 136, 74, 137, 143, 229, 170, 20, 160, 206, 219, 191, 185, 46, 223, 150, 190, 116, 96, 198, 221, 220, 159, 238, 48, 176, 113, 168, 33, 44, 142, 67, 244, 13, 218, 122, 246, 214, 234, 237, 27, 165, 24, 153, 90, 84, 154, 235, 196, 80, 111, 102, 231, 228, 135, 16, 148, 26, 45, 10, 71, 156, 224, 183, 232, 72, 94, 132, 54, 58, 248, 144, 213, 139, 129, 245, 115, 25, 164, 87, 19, 193, 81, 32, 78, 91, 167, 171, 40, 92, 226, 109, 69, 86, 38, 61, 5, 14, 118, 145, 103, 53, 93, 172, 178, 225, 68, 163, 210, 179, 192, 208, 169, 17, 12, 50, 233, 6, 55, 243, 158, 88, 188, 242, 36, 173, 126, 155, 184, 216, 149, 47, 76, 200, 1, 112, 28, 161, 174, 41, 73, 222, 66, 37, 63, 64, 124, 89, 205, 9, 186, 202, 70, 203, 127, 105, 250, 182, 79, 43, 133, 8, 241, 114, 128, 51, 83, 98, 49, 209, 7, 95, 151, 162, 189, 180, 75, 195, 62, 207, 21, 104, 30, 117, 110, 140, 29, 227, 249, 82, 152, 11, 34, 85, 106, 217, 211, 2, 35, 215, 4, 230, 134, 31, 194, 97, 22, 125, 130, 100, 239, 131, 166, 65, 15, 146, 177, 204, 147]
29. Length 253
[46, 245, 174, 180, 85, 29, 141, 70, 252, 119, 214, 225, 86, 91, 41, 67, 219, 118, 127, 243, 2, 71, 157, 114, 55, 92, 5, 200, 199, 139, 191, 235, 153, 102, 206, 171, 117, 58, 223, 249, 11, 211, 202, 175, 156, 133, 57, 163, 47, 65, 213, 247, 189, 111, 177, 49, 124, 154, 164, 145, 80, 15, 232, 142, 39, 69, 201, 185, 229, 215, 170, 42, 3, 248, 169, 136, 149, 218, 237, 90, 135, 7, 242, 246, 23, 186, 31, 4, 167, 207, 173, 132, 195, 196, 78, 212, 22, 35, 194, 54, 184, 183, 222, 230, 88, 43, 144, 151, 34, 97, 6, 109, 37, 147, 72, 158, 134, 33, 51, 238, 165, 162, 9, 63, 166, 113, 137, 198, 50, 121, 106, 224, 19, 104, 95, 129, 193, 79, 192, 122, 30, 12, 234, 168, 76, 103, 73, 66, 188, 178, 172, 176, 250, 182, 110, 231, 155, 26, 197, 10, 152, 98, 131, 25, 36, 81, 138, 150, 227, 24, 112, 120, 204, 75, 8, 179, 94, 17, 140, 32, 77, 61, 233, 38, 205, 93, 99, 27, 208, 56, 216, 48, 241, 20, 130, 240, 115, 83, 60, 108, 28, 13, 89, 128, 160, 82, 40, 126, 16, 253, 21, 251, 228, 59, 159, 64, 203, 236, 52, 18, 181, 105, 107, 239, 220, 44, 74, 125, 209, 84, 226, 217, 210, 190, 101, 100, 68, 116, 161, 148, 244, 221, 96, 45, 123, 187, 62, 87, 53, 1, 146, 143, 14]
30. Length 256
[159, 248, 75, 43, 111, 38, 4, 17, 155, 87, 81, 208, 53, 230, 65, 11, 108, 228, 146, 212, 137, 225, 144, 189, 86, 105, 84, 128, 97, 50, 223, 15, 83, 169, 217, 47, 88, 236, 114, 181, 115, 177, 102, 250, 246, 104, 80, 45, 240, 14, 196, 52, 247, 41, 198, 32, 182, 206, 226, 101, 70, 94, 113, 49, 254, 59, 42, 154, 77, 253, 112, 215, 99, 25, 134, 92, 95, 150, 64, 178, 118, 79, 130, 63, 129, 131, 57, 218, 85, 204, 3, 163, 158, 186, 10, 199, 24, 125, 251, 51, 74, 160, 207, 120, 233, 30, 19, 9, 56, 167, 58, 117, 164, 54, 220, 229, 234, 203, 211, 103, 205, 69, 39, 5, 31, 191, 106, 180, 116, 245, 21, 222, 91, 235, 8, 2, 214, 29, 238, 176, 135, 61, 227, 202, 122, 252, 231, 89, 187, 37, 149, 96, 190, 172, 73, 18, 71, 1, 179, 46, 156, 201, 165, 256, 151, 27, 242, 188, 126, 124, 244, 100, 107, 143, 170, 72, 255, 40, 67, 192, 185, 219, 20, 157, 98, 237, 136, 168, 141, 224, 232, 44, 139, 132, 22, 60, 109, 90, 175, 171, 62, 23, 161, 12, 76, 210, 68, 184, 93, 243, 48, 209, 174, 200, 121, 123, 36, 173, 140, 133, 145, 6, 110, 152, 142, 241, 55, 138, 147, 193, 213, 127, 7, 34, 66, 153, 26, 13, 162, 183, 239, 78, 249, 221, 28, 194, 16, 35, 33, 82, 195, 148, 216, 119, 166, 197]```

Points awarded for the least number of Ps & Ss.
Posted
Updated 27-Jul-17 8:48am
v3
PIEBALDconsult 24-Mar-17 9:37am
I see no point in using Pops; Swaps should be enough for anybody.
Given [ 2 , 1 , 3 ], define new (sub) list [ 2 , 1 ], Swap, done.
Patrice T 31-Mar-17 5:12am
Hi Graeme,
Interesting challenge, because it is open.
Unfortunately, I will not submit a solution, not enough time to work on it (job take too much time this week).
Graeme_Grant 31-Mar-17 5:17am
Yeah, I thought so...

I would submit a solution but as I am the one asking, I can't. Maybe Chris will extend it for another week.

I have some other interesting ones ... might forward them to Chris to use at a later time...
Patrice T 14-Apr-17 22:19pm
Hi Greame,
I posted my solution, so if no one else is working on the challenge, I think you can post your solution.
Patrice T 25-Jul-17 18:25pm
Hi,
Nice to see you back online.
I am still curious to see your approach to this challenge. :)

## Solution 1

This is basically a bubble sort implementation: looping through the sequence, swapping items if they are not in order.
C#
```class Sorter {
private readonly List<char> sortSequence = new List<char>();

public Sorter(int[] data) {
this.data = data;
}

public string Sort() {
while (!IsSorted())
if(IsInSequence(LastItem, FirstItem))
Pop(); // if the two elements are sorted move on
else
Swap(); // swap them if they are not in order

return new string(sortSequence.ToArray());
}

private bool IsInSequence(int x, int y) {
return x < y                         // must be a rising sequence
|| (x == data.Length && y == 1); // except for last/first item boundary
}

private void Swap() {
var tmp = FirstItem;
FirstItem = LastItem;
LastItem = tmp;
}

private void Pop() {
var first = FirstItem;
Array.Copy(data, 1, data, 0, data.Length - 1);
LastItem = first;
}

private bool IsSorted() {
for (int i = 1; i < data.Length; i++)
if (data[i - 1] > data[i])
return false;

return true;
}

private int FirstItem  {
get { return data[0]; }
set { data[0] = value; }
}

private int LastItem {
get { return data[data.Length - 1]; }
set { data[data.Length - 1] = value; }
}
}```

And here are my results (input length vs. output length):
```input output
3     2
7    19
41  1642
52  3336
65  4913
69  4966
75  6780
80  6246
103 12142
108     0
109 13986
151 24976
173 34061
177 38171
192 42372
201 48316
201 47674
205 49845
211 51551
226 58859
227 56824
230 59450
238 64227
241 66250
241 66287
244 71345
246 73426
250 72260
253 68629
256 77677```

I know these are not optimal. I have another implementation which searches for best solution but this of course doesn't finish in reasonable time for anything bigger than 7 items.

PIEBALDconsult 24-Mar-17 18:48pm
"which searches for best solution"
Yeah, my thought was that the cost of the analysis required to find the optimal solution outweighs the cost of a brute-force solution.
https://xkcd.com/1445/
Tomas Takac 25-Mar-17 8:36am
I like that :)

## Solution 2

UPDATED: Fixed a couple bugs including a weighting bug that could cause infinitely swapping the same position. Handles the first two example inputs as shown below but still runs into a stack overflow for larger data sets. I checked and it isn't stuck looping on a single swap, the algorithm just doesn't seem "smart" enough to solve the large set before recursion causes a stack overflow. Working on improving the algorithm now.

I gotta say, this is probably my favorite challenge so far. When you really dive into the problem it gets quite complex to optimize.

This is my first try at an optimal solution. Works well for small array numbers, runs into stack overflows at higher array numbers. Currently working to fix that but dunno if it'll be in time since I started so late. The idea is simple:
1) Create an `ISort` implementation for your data type.
2) Register this implementation with `SortRegistry`.
3) Call `SPSorter.Solve(arrayToSort)`.

This will call `SPOptimizer` which weights the swaps based on how positively they affect the resulting array compared to the final result. This continues until a solution is found. The program has a default LSD Radix Sort for integers.
C#
```static void Main(string[] args)
{
SPSorter sorter = new SPSorter();
int[][] testValues = new int[][] {
new int[] { 2, 1, 3 },
new int[] { 2, 7, 5, 3, 4, 6, 1 },
new int[] { 7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34 }
};
Console.WriteLine(sorter.Solve(testValues[0])); //PS
Console.WriteLine("-----");
Console.WriteLine(sorter.Solve(testValues[1])); //PSPPPPPPSPPPSPS
Console.WriteLine("-----");
Console.WriteLine(sorter.Solve(testValues[2])); //Overflow
}```

C#
```public class SPSorter
{
public SortRegistry Registry { get; private set; }

public SPSorter()
{
Registry = new SortRegistry();
}
public SPSorter(SortRegistry registry)
{
Registry = registry;
}

public string Solve<T>(IEnumerable<T> items)
{
T[] sortedItems = items.ToArray();
int[] sortedIndices = Registry.Sort<T>().Execute(sortedItems);
return SPOptimizer.Optimize(sortedIndices);
}

private class SPOptimizer
{
public static string Optimize(int[] sortedIndices) =>
Analyze(CalculateShiftOffsets(sortedIndices));

private static SPList<int> CalculateShiftOffsets(int[] sortedIndices)
{
int arrayLength = sortedIndices.Length;
int[] shiftOffsets = new int[arrayLength];
int rawShift = 0;
for (int i = 0; i < arrayLength; i++)
{
if (sortedIndices[i] >= i)
rawShift = sortedIndices[i] - i;
else
rawShift = arrayLength + sortedIndices[i] - i;
shiftOffsets[(i + rawShift) % arrayLength] = (arrayLength - rawShift) % arrayLength;
}
return new SPList<int>(shiftOffsets);
}

private static string Analyze(SPList<int> shiftOffsets)
{
StringBuilder solution = new StringBuilder();
int listCount = shiftOffsets.Count;
int minimumShiftConstant = shiftOffsets.Count * 2;
int swapLocation = 0;
//Weight and compare swaps in the shift list
for (int i = 0; i < listCount; i++)
{
int currentOffset = shiftOffsets.Data;
shiftOffsets.Pop();
int nextOffset = shiftOffsets.Data;
int shiftConstant = (listCount - (nextOffset + 1)) + ((currentOffset == 0)?listCount:currentOffset) - 1;
if (shiftConstant < minimumShiftConstant)
{
minimumShiftConstant = shiftConstant;
swapLocation = (i + 1) % listCount;
}
}
//Shift to the chosen swap
for (int i = 0; i < swapLocation; i++)
{
shiftOffsets.Pop();
solution.Append('P');
}
//Swap and update shift offsets
if (++shiftOffsets.Data >= listCount)
shiftOffsets.Data = 0;
shiftOffsets.Swap();
if (--shiftOffsets.Data < 0)
shiftOffsets.Data = listCount - 1;
solution.Append('S');

//Check if offsets are satisfied
bool complete = true;
for (int i = 0; i < listCount; i++)
{
if (shiftOffsets.Data != 0)
complete = false;
shiftOffsets.Pop();
}
if (!complete)
solution.Append(Analyze(shiftOffsets));
return solution.ToString();
}
}
}

public class SortRegistry
{
private readonly Dictionary<Type, object> _registeredSorts = new Dictionary<Type, object>();

public IIndexSort<T> Sort<T>() =>
_registeredSorts[typeof(T)] as IIndexSort<T>;

public void Register<T>(IIndexSort<T> typeSort) =>
_registeredSorts[typeof(T)] = typeSort;
}

public interface IIndexSort<T>
{
int[] Execute(T[] list);
}

{
private int bits = sizeof(int) * 8;
public int BitGroupingCount { get; set; } = 8;

public int[] Execute(int[] list)
{
List<KeyValuePair<int, int>> indexValuePairs = new List<KeyValuePair<int, int>>(list.Length);
for (int i = 0; i < list.Length; i++)
int groups = (int)Math.Ceiling((double)bits / BitGroupingCount);
int groupMask = (1 << BitGroupingCount) - 1;
int[] itemCount = new int[1 << BitGroupingCount];
int[] itemOrder = new int[1 << BitGroupingCount];
KeyValuePair<int, int>[] tempList = new KeyValuePair<int, int>[list.Length];

for (int i = 0, groupOffset = 0; i < groups; i++, groupOffset += BitGroupingCount)
{
for (int j = 0; j < itemCount.Length; j++)
itemCount[j] = 0;
for (int j = 0; j < list.Length; j++)
{
int groupValue = (list[j] >> groupOffset) & groupMask;
itemCount[groupValue]++;
}
itemOrder[0] = 0;
for (int j = 1; j < itemCount.Length; j++)
itemOrder[j] = itemOrder[j - 1] + itemCount[j - 1];
for (int j = 0; j < list.Length; j++)
{
int groupValue = (list[j] >> groupOffset) & groupMask;
int orderValue = itemOrder[groupValue]++;
tempList[orderValue] = indexValuePairs[j];
}
indexValuePairs = new List<KeyValuePair<int, int>>(tempList);
}
int[] results = new int[indexValuePairs.Count];
for (int i = 0; i < indexValuePairs.Count; i++)
results[i] = indexValuePairs[i].Key;
return results;
}
}

public class SPList<T> : IEnumerable<T>
{
private class Node
{
public Node NextNode { get; set; } = null;
public Node PreviousNode { get; set; } = null;
public T Data { get; set; }
}

private Node head = new Node();
public int Count { get; private set; } = 0;
public T Data
{
set { if (value != null) head.Data = value; }
}

public SPList(IEnumerable<T> list)
{
Node newNode;
foreach (T item in list)
{
newNode = new Node();
newNode.Data = item;
Count++;
}
}

public void Pop() =>
public void UnPop() =>
public void Swap()
{
//Change surrounding Node references to head and tail

//Change head and tail next Node references

//Change head and tail previous Node references

Pop();
}

public List<T> ToList()
{
List<T> returnList = new List<T>();
foreach (T data in this)
return returnList;
}

public SPList<T> Copy() =>
new SPList<T>(this);

public IEnumerator<T> GetEnumerator()
{
for (int i = 0; i < Count; i++)
{
Pop();
}
}
IEnumerator IEnumerable.GetEnumerator() =>
GetEnumerator();
}```

v7
Graeme_Grant 31-Mar-17 5:19am
I thought it was an interesting problem... Was expecting a few more devs to offer solutions.

Maybe email Chris directly and see if he is willing to extend it.
Jon McKee 31-Mar-17 5:35am
Will do! I doubt any of the solutions will be "ground-breaking" (O(n) is about the best you can ask for) but it could still lead to some very interesting solutions!
Patrice T 31-Mar-17 11:54am
How does it perform with data from question ?
Jon McKee 31-Mar-17 15:26pm
Besides the stack overflows? Hehe. I figured out the area that's causing the overflow but was too tired to figure out what was wrong so I went to bed. Will be fixing it up today :thumbsup:

## Solution 3

I think I got my solution (finally):
I used again my beloved Clipper language (FoxPro alike).

- First I use the list of numbers like a circular buffer: data don't move, pointers are.
- Then I build a helper array with final position in sorted array, so I don't make assumption on data: continuous values, holes in values, repeats.
VB
```dest= array(size)
for scan= 1 to size
dest[scan]= 1
for scanp=1 to scan-1
if lst[scan]<lst[scanp]
dest[scanp]++
else
dest[scan]++
endif
next
next
```

- Then I choose 1 value in array and use it as a pivot and all other values are moving around.
- In order to get best result, I test every possible pivot

The whole problem is about making the pointers arithmetic right.

Source code:
VB
```*   CCCP Code Challenge Code Project
*    Sort list with swaps and Rotates
procedure cccp8()
set printer to cccp8.log
set color to w/n
clear
set printer on
? "      Size", "           ", "          S", "         P", "     Total", "     seconds"
set printer off
tot_nb_s= 0
tot_nb_p= 0

SR_Sort({2, 1, 3})
SR_Sort({2, 7, 5, 3, 4, 6, 1})
SR_Sort({7, 12, 17, 2, 14, 15, 33, 20, 37, 18, 9, 25, 41, 26, 39, 29, 16, 5, 23, 24, 35, 38, 32, 6, 11, 21, 27, 8, 40, 3, 10, 36, 13, 30, 31, 28, 1, 4, 19, 22, 34})
/* removed other datasets */
set printer on
? 0, 0, tot_nb_s, tot_nb_p, tot_nb_s+ tot_nb_p
set printer off
set printer to
return

procedure SR_Sort (lst)
ltmp= aclone(lst)
seq=""
mx= SR_SortC1 (ltmp, 1)
for fx=2 to len(lst)
ltmp= aclone(lst)
seq=""
tmp= SR_SortC1 (ltmp, fx)
if tmp[5]>0 .and. tmp[5] < mx[5]
mx= tmp
endif
next

set color to w/n
set printer on
? mx[1], mx[2], mx[3], mx[4], mx[5], mx[6]
set console off
?? "  ", RLE(mx[7])
set console on
set printer off
tot_nb_s += mx[3]
tot_nb_p += mx[4]
return

function SR_SortC1 (lst, fx)
t_db= seconds()
*	Init
size= len(lst)
nb_s= 0
nb_p= 0
pntr= size

*	calc final position
dest= array(size)
for scan= 1 to size
dest[scan]= 1
for scanp=1 to scan-1
if lst[scan]<lst[scanp]
dest[scanp]++
else
dest[scan]++
endif
next
next

fix_d= fx
fix_f= fx
fix_l= 1
heat= size-1
do while heat > 0 .and. dest[(fix_d+ size- 2)% size +1]%size+1 = dest[fix_d]
fix_d = (fix_d+ size- 2)% size +1
fix_l++
heat--
enddo
do while heat > 0 .and. dest[fix_f]%size+1 = dest[fix_f%size+1]
fix_f= fix_f% size+ 1
fix_l++
heat--
enddo

*	Sort Swap Rot
if fx>1 .and. fix_d<>fx
heat=-1
else
do while heat > 0
nxt= pntr%size+1
rst= (size-(fix_f- fix_d+size)%size)/2

do case
case (nxt-fix_d+size)%size < fix_l
*	*	sorted pivot range
do while pntr != fix_f
rotat(lst)
enddo
nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
case (fix_d-nxt+size)%size < rst .and. (dest[nxt]-dest[fix_f]+size)%size < rst
*	The quick for jump over the lazy dog.
*	Moves intersting values over the pivot
do while nxt != fix_f
rotat(lst)
swapC(lst)
nxt= pntr%size+1
enddo
fix_d = (fix_d+ size- 2)% size +1
fix_f = (fix_f+ size- 2)% size +1
otherwise
swapC(lst)
endcase

do while heat > 0 .and. dest[(fix_d+ size- 2)% size +1]%size+1 = dest[fix_d]
fix_d = (fix_d+ size- 2)% size +1
fix_l++
heat--
enddo
do while heat > 0 .and. dest[fix_f]%size+1 = dest[fix_f%size+1]
fix_f= fix_f% size+ 1
fix_l++
heat--
enddo
if heat > 0
rotat(lst)
endif
enddo

*	Rotation finale
do while lst[pntr] < lst[pntr%size+1]
rotat()
enddo

heat=1
for scan= 1 to size-1
if dest[scan]<dest[scan+1]
heat ++
endif
next
if dest[size]<dest[1]
heat ++
endif
endif
t_fn= seconds()
return {size, heat, nb_s, nb_p, nb_s+ nb_p, t_fn-t_db}

procedure swapC(lst,pos)
*	swap
nxt= pntr% size+ 1

tmp= lst[pntr]
lst[pntr]= lst[nxt]
lst[nxt]= tmp

tmp= dest[pntr]
dest[pntr]= dest[nxt]
dest[nxt]= tmp

nb_s++
seq += "S"
return

procedure rotat()
pntr= pntr% size+ 1
seq += "R"
nb_p++
return

function RLE(st)
rep=""
scan=1
do while scan<= len(st)
if st[scan]="S"
rep+= "S"
scan++
else
rpt= 1
do while scan+rpt<= len(st) .and. st[scan+rpt]="R"
rpt++
enddo
if rpt>2
rep+= str(rpt,,,.T.)+"R"
scan+= rpt
else
rep+= "R"
scan++
endif
endif
enddo
return rep```

- First version sorting code:
VB
```do case
case (nxt-fix_d+size)%size < fix_l
*   sorted pivot range
do while pntr != fix_f
rotat(lst)
enddo
nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
otherwise
swapC(lst)
endcase
```

- First version result:
``` Size      Swaps    Rotates      Total
3          1          1          2
7          4          7         11    RSRRSRS3RS
41        339       1002       1341
52        559       1683       2242
65        840       2894       3734
69        939       3086       4025
75       1210       3607       4817
80       1533       4297       5830
103       2471       8013      10484
108          0          0          0
109       2870       8742      11612
151       5200      17928      23128
173       6534      24153      30687
177       7529      25225      32754
192       9128      28512      37640
201       8894      30321      39215
201       9188      30706      39894
205       9906      33120      43026
211      10146      33665      43811
226      11707      40712      52419
227      12796      40664      53460
230      12178      42334      54512
238      13056      46223      59279
241      13947      47465      61412
241      13614      46258      59872
244      13968      49137      63105
246      14339      47365      61704
250      13941      51463      65404
253      15587      51119      66706
256      15631      52136      67767
Total      228055     771838     999893
```

- Second version sorting code:
VB
```do case
case (nxt-fix_d+size)%size < fix_l
*   sorted pivot range
do while pntr != fix_f
rotat(lst)
enddo
nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
case (fix_d-nxt+size)%size < rst .and. (dest[nxt]-dest[fix_f]+size)%size < rst
*   The quick for jump over the lazy dog.
*   Moves intersting values over the pivot
do while nxt != fix_f
rotat(lst)
swapC(lst)
nxt= pntr%size+1
enddo
fix_d = (fix_d+ size- 2)% size +1
fix_f = (fix_f+ size- 2)% size +1
otherwise
swapC(lst)
endcase
```

- Second version result:
``` Size          S          P      Total
3          1          2          3
7          8         13         21
41        327        801       1128
52        576       1274       1850
65        972       1983       2955
69        929       2035       2964
75       1222       2805       4027
80       1274       2948       4222
103       2245       5664       7909
108          0          0          0
109       2550       6153       8703
151       5060      12861      17921
173       6850      15963      22813
177       6721      17632      24353
192       8251      19719      27970
201       8300      22685      30985
201       8228      22504      30732
205       8604      23742      32346
211       9928      24425      34353
226      10558      29269      39827
227      10954      30734      41688
230      12049      29365      41414
238      11240      33305      44545
241      12029      34980      47009
241      12284      33438      45722
244      13220      33725      46945
246      13036      35086      48122
250      12840      35810      48650
253      13801      35492      49293
256      13986      37625      51611
Total     208043     552038     760081
```

I knew there was a good shave to do on first version. There is still some fine tuning possible.
[Update 20140710]
- Third version sorting code: a simple tweak improved the solution of 25000 moves.
VB
```do case
case (nxt-fix_d+size)%size < fix_l
*   sorted pivot range
do while pntr != fix_f
rotat(lst)
enddo
nxt= pntr%size+1
case (dest[pntr]-dest[fix_d]+size)%size < (dest[nxt]-dest[fix_d]+size)%size
case (fix_d-nxt+size)%size + (dest[nxt]-dest[fix_f]+size)%size < rst
*   The quick for jump over the lazy dog.
*   Moves intersting values over the pivot
do while nxt != fix_f
rotat(lst)
swapC(lst)
nxt= pntr%size+1
enddo
fix_d = (fix_d+ size- 2)% size +1
fix_f = (fix_f+ size- 2)% size +1
otherwise
swapC(lst)
endcase
```

- Third version result:
``` Size          S          P      Total
3          1          1          2
7          4          7         11
41        249        808       1057
52        501       1277       1778
65        694       2132       2826
69        891       2170       3061
75       1138       2712       3850
80       1223       3267       4490
103       1913       5566       7479
108          0          0          0
109       2154       5935       8089
151       4532      12721      17253
173       5760      16136      21896
177       6043      17811      23854
192       6608      20708      27316
201       8280      22200      30480
201       7746      22276      30022
205       8422      22664      31086
211       8426      25033      33459
226       9482      29323      38805
227       9650      29888      39538
230      10468      30360      40828
238      10705      31880      42585
241      10487      31610      42097
241      11392      33375      44767
244      11778      34161      45939
246      11636      34200      45836
250      11548      35876      47424
253      12497      35736      48233
256      13152      37089      50241
Total     187380     546922     734302
```

[Update 20170411]
- Fourth version sorting code: looks like the range defined by `rst` have big effect on efficiency.
VB
`rst= (size-(fix_f- fix_d+size)%size)*2/3-1`

- Fourth version result:
``` Size          S          P      Total
3          1          1          2
7          4          7         11
41        301        676        977
52        482       1226       1708
65        742       1994       2736
69        901       1967       2868
75       1020       2567       3587
80       1169       2947       4116
103       2009       5146       7155
108          0          0          0
109       2084       5610       7694
151       4454      11592      16046
173       5724      14568      20292
177       5997      15871      21868
192       7039      18195      25234
201       8178      19600      27778
201       7646      20060      27706
205       7868      20866      28734
211       8314      21875      30189
226       9583      25736      35319
227      10144      25966      36110
230      10430      27498      37928
238      10938      28561      39499
241      11111      28697      39808
241      11538      29703      41241
244      11871      30516      42387
246      11567      31199      42766
250      12022      31536      43558
253      12199      31434      43633
256      12820      33499      46319
Total     188156     489113     677269
```

v9
Maciej Los 9-Apr-17 14:20pm
I see the result of your job, but where is a code?
Patrice T 9-Apr-17 14:31pm
Last sentence is "Still have a couple optimization to test before publishing my solution"
Code is coming after I tested the optimizations.
Maciej Los 9-Apr-17 15:31pm
OK. We're waiting :)
Patrice T 14-Apr-17 22:17pm
Completed my solution :)
Maciej Los 15-Apr-17 14:50pm
Looks good to me ;)

## Solution 4

C#
```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SwapAndPop
{
internal static class Program
{
private static void Main()
{
var lists = new List<int[]>
{
new int[] { 2, 1, 3 },
new int[] { 2, 7, 5, 3, 4, 6, 1 },
// trimmed
};

int tlMoves = 0, tlSwap = 0, tlPop = 0;

Console.WriteLine("SIZE      SWAP       POP     TOTAL");

for (int i = 0; i < lists.Count; i++)
{
var listCount = lists[i].Length;
var moves = Solve(lists[i]);
var movesCount = moves.Length;
var types = moves.GroupBy((x) => x).ToDictionary(x => x.Key, x => x);
var countSwap = types.Keys.Contains('S') ? types['S'].Count() : 0;
var countPop = types.Keys.Contains('P') ? types['P'].Count() : 0;

tlMoves += movesCount;
tlSwap += countSwap;
tlPop += countPop;

Console.WriteLine(\$"{listCount,4:N0}{countSwap,10:N0}{countPop,10:N0}{movesCount,10:N0}");
}

Console.WriteLine(\$"Total: {tlSwap,7:N0}{tlPop,10:N0}{tlMoves,10:N0}");
Console.WriteLine("\n  --Press any key to exit --");
}

private static string Solve(int[] list)
{
var count = list.Length;
var optimalMoves = Solve(list, 0);
var optimalCount = optimalMoves.Length;

for (int i = 1; i < count; i++)
{
var moves = Solve(list, i - 1);
var moveCount = moves.Length;
if (moveCount < optimalCount)
{
optimalCount = moveCount;
optimalMoves = moves;
}
}
return optimalMoves;
}

private static string Solve(int[] list, int PivotIdx)
{
var count = list.Length;
var work = new int[count];
Array.Copy(list, work, count);

var moves = new StringBuilder();

void swap()
{
int tmp = work[0];
work[0] = work[count - 1];
work[count - 1] = tmp;
moves.Append("S");
}

void pop()
{
int temp = work[0];
Array.Copy(work, 1, work, 0, count - 1);
work[count - 1] = temp;
if (--PivotIdx < 0) PivotIdx += count;
moves.Append("P");
}

float dist2Home(int ndx, int i)
{
var home = (PivotIdx + i) % count;
var dist1 = ndx - home;
var dist2 = home - ndx;
if (dist1 < 0) dist1 += count;
if (dist2 < 0) dist2 += count;
return Math.Min(dist1, dist2 * Math.Max(1F, count / 50F));
}

while (!work.IsSolved())
{
var distP = Math.Max(dist2Home(0, work[0]), dist2Home(count - 1, work[count - 1]));
var distS = Math.Max(dist2Home(count - 1, work[0]), dist2Home(0, work[count - 1]));

if (distS < distP)
swap();
else
pop();

}
return moves.ToString();
}

private static bool IsSolved(this int[] list)
{
int count = list.Length - 1;
if (count < 1) return true;
int item = list[0], i = 1;
while (i <= count && item <= (item = list[i])) i++;
return i > count;
}
}
}```

Output:
```SIZE      SWAP       POP     TOTAL
3         1         1         2
7         4         7        11
41       257       636       893
52       433     1,113     1,546
65       686     1,857     2,543
69       719     1,967     2,686
75       886     2,505     3,391
80     1,017     2,711     3,728
103     1,631     4,852     6,483
108         0         0         0
109     1,816     5,287     7,103
151     3,758    10,613    14,371
173     4,936    13,727    18,663
177     5,085    14,643    19,728
192     6,200    16,624    22,824
201     6,628    18,200    24,828
201     6,492    18,260    24,752
205     6,750    18,823    25,573
211     7,096    20,413    27,509
226     8,609    23,612    32,221
227     8,448    23,480    31,928
230     8,631    24,999    33,630
238     9,426    25,177    34,603
241     9,683    26,993    36,676
241     9,682    26,823    36,505
244     9,671    28,088    37,759
246     9,786    28,320    38,106
250    10,228    28,036    38,264
253    10,341    29,699    40,040
256    10,715    30,690    41,405
Total: 159,615   448,156   607,771

--Press any key to exit --```

Patrice T 27-Jul-17 15:08pm
From the output, it is damn efficient.
Graeme_Grant 27-Jul-17 20:56pm
;)