Graeme_Grant Ответов: 4

Задача кодирования: сортировка списка с помощью свопов и всплывающих окон


Примечание: В Отсутствие Криса[^] Я сделал шаг вперед, чтобы опубликовать вызов на этой неделе. Наслаждайтесь!

Рассмотрим рандомизированный список целых чисел от 1 до N. Вы хотите отсортировать его, используя только следующие действия:

Поменяйте местами первый и последний элементы списка. (С)
Выделите первый элемент и добавьте его в конец списка. (П)

С помощью С и П вы можете поменять местами любые соседние элементы, вызвав П до тех пор, пока два рассматриваемых элемента не станут первым и последним элементами в списке, затем вызов С чтобы поменять их местами, затем звоните П снова до тех пор, пока они не окажутся в исходных индексах (теперь поменялись местами).

Создайте метод, который принимает перестановку чисел от 1 до N (N > 1). Он может быть представлен в виде списка, строки или чего угодно, что вам удобно. Он должен вывести последовательность S и P, которая сортировала бы перестановку при применении слева направо. Эта последовательность не обязательно должна быть оптимально короткой, но чем она короче, тем лучше.

Вы не можете жестко кодировать свою программу в соответствии с любыми данными.

Что я уже пробовал:

Пример

Если вход был [2, 1, 3], то выход мог бы быть SP, потому что

С примененный к [2, 1, 3] делает его [3, 1, 2],
и П примененный к [3, 1, 2] делает его [1, 2, 3], который сортируется.

Тестовые данные
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]

Баллы начисляются за наименьшее количество Пиндекс S &амп; Сс.

PIEBALDconsult

Я не вижу смысла в использовании Соз; свопов должно быть достаточно для кого угодно.
Учитывая [ 2, 1, 3 ], Определите новый (под) Список [ 2, 1], своп, готово.

Patrice T

Привет Грэм,
Интересный вызов, потому что он открыт.
К сожалению, я не представлю решение, не хватит времени поработать над ним (работа займет слишком много времени на этой неделе).

Graeme_Grant

Да, я так и думал...

Я бы предложил решение, но так как я сам спрашиваю, то не могу. Может быть, Крис продлит его еще на неделю.

У меня есть еще кое-что интересное ... может быть, перешлю их Крису, чтобы использовать позже...

Patrice T

Привет Грим,
Я опубликовал свое решение, так что если никто больше не работает над проблемой, я думаю, вы можете опубликовать свое решение.

Patrice T

Привет,
Рад снова видеть тебя в сети.
Мне все еще любопытно увидеть ваш подход к этому вызову. :)

Graeme_Grant

Один день скоро... все еще в середине большого проекта... ;)

Graeme_Grant

Вот, держи...

4 Ответов

Рейтинг:
2

Patrice T

Я думаю, что получил свое решение (наконец-то):
Я снова использовал свой любимый язык Clipper (FoxPro alike).

- Сначала я использую список чисел как круговой буфер: данные не перемещаются, указатели есть.
- Затем я строю вспомогательный массив с конечной позицией в отсортированном массиве, поэтому я не делаю предположений о данных: непрерывные значения, дыры в значениях, повторы.

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

- Затем я выбираю 1 значение в массиве и использую его в качестве стержня, а все остальные значения перемещаются.
- Чтобы получить наилучший результат, я тестирую каждый возможный разворот

Вся проблема заключается в том, чтобы сделать арифметику указателей правильной.

Исходный код:
*   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)
	aadd(mx,seq)
	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
			aadd(mx,seq)
		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
				*	already ordered
			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


- Первая версия сортировочного кода:
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
    *   already ordered
otherwise
    swapC(lst)
endcase

- Результат первой версии:
 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


- Код сортировки второй версии:
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
    *   already ordered
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

- Результат второй версии:
 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

Я знал, что на первой версии нужно было хорошо побриться. Все еще возможна некоторая тонкая настройка.
[Обновление 20140710]
- Третья версия сортировочного кода: простая настройка улучшила решение на 25000 ходов.
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
    *   already ordered
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

- Результат третьей версии:
 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      2503


Maciej Los

Я вижу результат вашей работы, но где же код?

Patrice T

Последнее предложение: "все еще есть пара оптимизаций для тестирования перед публикацией моего решения"
Код приходит после того, как я протестировал оптимизацию.

Maciej Los

ОК. Мы ждем :)

Patrice T

Завершил свое решение :)

Maciej Los

Выглядит хорошо для меня ;)

Patrice T

Спасибо.
Пытались ли вы сами решить эту проблему ?

Maciej Los

Нет. Я немного занят. Это длится несколько месяцев...

Рейтинг:
1

Tomas Takac

Это в основном реализация пузырьковой сортировки: циклическое прохождение последовательности, замена элементов, если они не в порядке.

class Sorter {
    private readonly int[] data;
    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;
        sortSequence.Add('S');
    }

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

    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; }
    }
}

И вот мои результаты (входная длина против выходной длины):
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

Я знаю, что они не являются оптимальными. У меня есть еще одна реализация, которая ищет лучшее решение, но это, конечно, не заканчивается в разумные сроки для чего-то большего, чем 7 пунктов.


PIEBALDconsult

"который ищет лучшее решение"
Да, я думал, что стоимость анализа, необходимого для поиска оптимального решения, перевешивает стоимость решения грубой силы.
https://xkcd.com/1445/

Tomas Takac

Мне это нравится :)

Рейтинг:
1

Graeme_Grant

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 --");
            Console.ReadKey();
        }

        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;
        }
    }
}

Выход:
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

Судя по выходу, он чертовски эффективен.

Graeme_Grant

;)

Рейтинг:
0

Jon McKee

ОБНОВЛЕННЫЙ: Исправлена пара ошибок, включая ошибку взвешивания, которая могла привести к бесконечному изменению одной и той же позиции. Обрабатывает первые два примера входных данных, как показано ниже, но все равно сталкивается с переполнением стека для больших наборов данных. Я проверил, и он не застрял в цикле на одном свопе, алгоритм просто не кажется достаточно "умным", чтобы решить большой набор до того, как рекурсия вызовет переполнение стека. Сейчас мы работаем над улучшением алгоритма.

Должен сказать, что это, наверное, мой самый любимый вызов до сих пор. Когда вы действительно погружаетесь в проблему, она становится довольно сложной для оптимизации.

Это моя первая попытка найти оптимальное решение. Хорошо работает для небольших чисел массивов, сталкивается с переполнением стека при более высоких числах массивов. В настоящее время я работаю над тем, чтобы исправить это, но не знаю, успею ли я вовремя, так как начал так поздно. Идея проста:
1) Создайте ISort реализация для вашего типа данных.
2) зарегистрируйте эту реализацию с помощью SortRegistry.
3) вызов SPSorter.Solve(arrayToSort).

Это вызовет SPOptimizer который взвешивает свопы на основе того, насколько положительно они влияют на результирующий массив по сравнению с конечным результатом. Это продолжается до тех пор, пока не будет найдено решение. Программа имеет сортировку по умолчанию LSD Radix для целых чисел.

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
    Console.ReadKey();
}

public class SPSorter
{
    public SortRegistry Registry { get; private set; }

    public SPSorter()
    {
        Registry = new SortRegistry();
        Registry.Register(new RadixSort());
    }
    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);
}

public class RadixSort : IIndexSort<int>
{
    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++)
            indexValuePairs.Add(new KeyValuePair<int, int>(i, list[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
    {
        get { return head.Data; }
        set { if (value != null) head.Data = value; }
    }

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

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

        //Change head and tail next Node references
        head.PreviousNode.NextNode = head.NextNode;
        head.NextNode = head.PreviousNode;

        //Change head and tail previous Node references
        head.PreviousNode = head.PreviousNode.PreviousNode;
        head.NextNode.PreviousNode = head;

        //Change head
        Pop();
    }

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

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

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


Graeme_Grant

Я подумал, что это интересная проблема... Я ожидал, что еще несколько разработчиков предложат свои решения.

Мне понравилось смотреть на ваше решение.

Может быть, написать Крису напрямую и посмотреть, готов ли он продлить его.

Jon McKee

Будет сделано! Я сомневаюсь, что какое-либо из решений будет "новаторским" (O(n) - это лучшее, что вы можете попросить), но оно все равно может привести к некоторым очень интересным решениям!

Patrice T

Как он работает с данными из вопроса ?

Jon McKee

Кроме переполнения стека? Хе-хе. Я вычислил область, которая вызывает переполнение, но был слишком устал, чтобы понять, что было не так, поэтому я пошел спать. Сегодня я его починю :большой палец вверх: