Перестановка элементов массива

В таком случае, приходится добавлять функцию проверки, что элемент является младшим в последовательности:

Код (C):

1.  
2. #include <stdio.h>
3.  
4. #define RANK   4
5. #define ITEMS  (1 << RANK)
6. #define TOTAL  (ITEMS << 1)
7.  
8. bool validate(size_t i)
9. {
10.         size_t k = i;
11.  
12.         do
13.         {
14.                 k = (k & 1) ? (k >> 1) | ITEMS : (k >> 1);
15.                 if (k < i)
16.                         return false;
17.         } while (k != i);
18.  
19.         return true;
20. }
21.  
22. int main()
23. {
24.         int buf[TOTAL];
25.         int tmp;
26.  
27.         for (size_t i=0; i<TOTAL; ++i)
28.                 buf[i] = i;
29.  
30.         for (size_t i=1; i<ITEMS; ++i)
31.         {
32.                 // Check that previous element in chain is not less than current
33.                 if (!validate(i))
34.                         continue;
35.  
36.                 size_t k = i;
37.  
38.                 while (1)
39.                 {
40.                         k = (k & ITEMS) ? ((k << 1) & (TOTAL - 1)) | 1 : (k << 1);
41.                         if (k == i)
42.                                 break;
43.  
44.                         tmp = buf[i];
45.                         buf[i] = buf[k];
46.                         buf[k] = tmp;
47.                 }
48.  
49.                 printf("Shuffle i=%d", int(i));
50.                 for (size_t i=0; i<TOTAL; ++i)
51.                         printf(" %02X", buf[i]);
52.                 printf("\n");
53.         }
54.  
55.  
56.         printf("Result:");
57.         for (size_t i=0; i<TOTAL; ++i)
58.                 printf(" %02X", buf[i]);
59.         printf("\n");
60. }
61.  

 

В природе существует алгоритм с линейным временем работы и константной памятью, но он очень сложный. См.:
"Stable minimum space partitioning in linear time" Katajainen, Pasanen
http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.25.5554&rep=rep1&type=pdf

 

maxdiver, формулировка этой задачи более общая. У нас частный случай, который, как раз, может выродиться в линейное количество перестановок + затрата времени на проверку, была ли выполнена перестановка ранее.

 

чё-то я не въехал в задачу: чётными/нет по индексу элемента иль содержимому элемента?

 

ежель я ничего не путаю ==>> надо перевести начальную цепочку в цепочку доменов, где каждый элемент домена состоит из итого элемента правой и левой подпоследовательностей? левый элемент домена должен быть по возможности чётом, а правый нечётом?