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

Всем привет!
Недавно столкнулся с такой задачей:
Есть массив, размер которого степень двойки (8, 16, 32 и т.д.). Необходимо переставить элементы массива, не меняя при этом их порядок следования, так, чтобы все элементы первой половины стали нечётными, а второй половины - чётными. При этом использовать динамическую память запрещается.

Пример:
Есть массив из 16 чисел: 0 1 2 3 4 5 6 7 8 9 a b c d e f
Первая половина: 0 1 2 3 4 5 6 7
Вторая половина: 8 9 a b c d e f
Результат перестановки: 0 8 1 9 2 a 3 b 4 c 5 d 6 e 7 f

Мне удалось решить эту задачу за O(N*log2(N)). Есть ли возможность её решить за O(N)?

З.Ы. Вообще, под такие вещи хотелось бы отдельный раздел WASM.ALGO или что-то вроде того.

 

За O(N) эту задачу можно решить при использовании дополнительного массива флагов. Сначала флаги очищаются, далее перебираем последовательно все индексы и если соответствующий флаг очищен, то с него начинаем делать перестановку помечая участвовавшие в ней элементы. Если делать без массива, то, чтобы не случилось повторной перестановки той же цепочки, начинать перестановку нужно с тех элементов которые имеют скажем максимальный индекс в цепочке. Проверить, что индекс максимальный можно предварительно сгенерировав все индексы цепочки, но это уже будет N*log(N). Про максимальные индексы точно можно сказать, что заканчиваться они обязательно должны на 0, а начинаться с самой длинной группы 1. Можно еще проверить что в индексе нет групп 1 длиннее чем в начале, а для таких же длинных уже сдвигать и проверять не получается ли большее значение.

 

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

Код (Text):

1.  
2. 0 - 0000 -> 0 - 0000
3. 1 - 0001 -> 2 - 0010
4. 2 - 0010 -> 4 - 0100
5. 3 - 0011 -> 6 - 0110
6. 4 - 0100 -> 8 - 1000
7. 5 - 0101 -> A - 1010
8. 6 - 0110 -> C - 1100
9. 7 - 0111 -> E - 1110
10. 8 - 1000 -> 1 - 0001
11. 9 - 0001 -> 3 - 0011
12. A - 0010 -> 5 - 0101
13. B - 0011 -> 7 - 0111
14. C - 0100 -> 9 - 1001
15. D - 0101 -> B - 1011
16. E - 0110 -> D - 1101
17. F - 0111 -> F - 1111
18.  

Отсюда можно сделать выводы о свойствах:
1. Новый индекс элемента есть индекс старого элемента, который был циклически сдвинут влево на один бит.
Пояснение: 0101 ROL 1 = 1010, 1111 ROL 1 = 1111
2. Отдельные элементы образуют замкнутые кольца обмена, которые можно преобразовать за операцию O(n), где n - длина кольца.
Пояснение: для нашего примера существует 6 колец обмена (далее - в двоичном виде):

Код (Text):

1.  
2. A: 0000 -> 0000
3. B: 1111 -> 1111
4. C: 0101 -> 1010 -> 0101
5. D: 0001 -> 0010 -> 0100 -> 1000 -> 0001
6. E: 0011 -> 0110 -> 1100 -> 1001 -> 0011
7. F: 0111 -> 1110 -> 1101 -> 1011 -> 0111
8.  

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

Код (Text):

1.  
2. Исходный массив 0 1 2 3 4 5 6 7 8 9 A B C D E F
3. По кольцу заменены элементы с номерами 1 -> 2 -> 4 -> 8 -> 1
4. Результат замены: 0 *8 *1 3 *2 5 6 7 *4 9 A B C D E F
5. Сопоставляем с ожидаемым результатом: 0 8 1 9 2 a 3 b 4 c 5 d 6 e 7 f
6.  

Вывод: после замены по кольцу все элементы, участвующие в кольце, встали на свои места.
4. Индекс следующего элемента в кольце обмена - результат циклического сдвига предыдущего индекса на 1 влево (следствие 1 и 2).
5. Размер кольца не превышает log2(N) - очевидное следствие из 4.
6. Количество колец обмена (если не считать кольца A и B из пункта 2) можно оценить по формуле R = floor((N - 2) / log2(N)).
Пояснение: для N = 16 имеем floor((16-2)/log2(16)) = floor(3.5) = 4 кольца обмена (C, D, E, F).
Для N=32 имеем floor((32-2)/log2(32)) = floor(6) = 6 колец обмена
7. Если однозначно определить формулу местонахождения хотя бы одного элемента для каждого кольца, то операцию преобразования массива можно выполнить за O(N) перестановок.

Соответственно, сейчас проблемы с поиском индексов по пункту 7. Если кто знает, как это сделать - задача будет решена.

 

Код (C):

1. for(int P=2;P<=30;P++){
2.     int N=1<<P;
3.     unsigned char *a=new unsigned char[N];
4.     for(int i=0;i<N;i++)
5.         a[i]=i;
6.     unsigned int S=0;
7.     for(int i=N/2;i<N;i+=2){
8.         int j=i;
9.         do{
10.             ++S;
11.             if(j&1) j+=N;
12.             j>>=1;
13.         }while(j<i);
14.         if(j>i) continue;
15.         int v=a[i];
16.         do{
17.             if(j&1) j+=N;
18.             j>>=1;
19.             v^=a[j]^=v^=a[j];
20.         }while(j<i);
21.     }
22.     printf("%u/2^%d=%4.2f\n",S,P,S*1.0/N);
23.     if(P<=6){
24.         for(int i=0;i<N;i++)
25.             printf("%4d",a[i]);
26.         if(N<16)
27.             printf("\n");
28.     }
29.     delete[] a;
30. }

Если отбросить 3/4 всех возможных индексов которые максимальными быть не могут, а во внутреннем цикле проверять является ли выбранный индекс максимальным в цепочке, то logN итераций потребуется только для действительно максимального индекса, если мы начали со второго по величине индекса, то в среднем придётся просмотреть уже только половину цепочки. При больших размерах массива в проверочном цикле требуется порядка 10 итераций на индекс, а с учётом того что внешний цикл перебирает только четверть индексов, коэффициент получается не настолько уж диким. При 32 элементах требуется 35 итераций, при 2^16 требуется 2^17 итераций, а при 2^30 внутренний цикл выполняется 2.56*2^30 раз. Еще можно делать проверку, что в индексе нет такой же длинной группы 1 как начальная, в этом случае сразу переходим к перестановке элементов, проверку что в индексе есть группа длиннее начальной, в этом случае берём следующий индекс, иначе выполняем проверочный цикл и по нему уже решаем нужно переставлять элементы или нет.

 

Динамическую память, увы, нельзя использовать.

У меня решение такое вышло (но это N*log2(N)):

Код (C):

1.  
2. #define RANK  4
3. #define ITEMS  (1 << RANK)
4. #define TOTAL  (ITEMS << 1)
5.  
6. int main()
7. {
8.   int buf[TOTAL];
9.   int tmp;
10.  
11.   for (size_t i=0; i<TOTAL; ++i)
12.   buf[i] = i;
13.  
14.   for (size_t r=1; r < ITEMS; r <<= 1)
15.   {
16.       size_t step = r << 1;
17.       for (size_t i=0; i<ITEMS; i += step)
18.       {
19.           int *a = &buf[i+r];
20.           int *b = &buf[i+ITEMS];
21.  
22.           for (size_t k=0; k<r; ++k)
23.           {
24.               tmp  = *a;
25.               *(a++) = *b;
26.               *(b++) = tmp;
27.           }
28.       }
29.  
30.       printf("r=%d (step=%d):", r, step);
31.       for (size_t i=0; i<TOTAL; ++i)
32.       printf(" %02X", buf[i]);
33.       printf("\n");
34.   }
35.  
36.   printf("Result:");
37.   for (size_t i=0; i<TOTAL; ++i)
38.   printf(" %02X", buf[i]);
39.   printf("\n");
40. }
41.  

P.S. Что-то форма набора текста сильно тормозит.

 

Код:

Код (C):

1. for(int P=1;P<=30;P++){
2.     int N=1<<P;
3.     unsigned char *a=new unsigned char[N];
4.     for(int i=0;i<N;i++)
5.         a[i]=i;
6.     unsigned E=0,//итераций внешнего цикла
7.         FS=0,//индекс явно не максимальный
8.         FW=0,//индекс явно максимальный
9.         C=0,//делаем дополнительную проверку
10.         CS=0,//индекс не максимальный
11.         CW=0,//индекс максимальный
12.         CI=0;//итераций для дополнительной проверки
13.     const int vs[17]={0,0,0x1,0x11,0x21,0x121,0x221,0x321,0x421,0x1421,0x2421,0x3421,0x4421,0x5421,0x6421,0x7421,0x8421};
14.     int p=P/2;
15.     int m=N>>p;
16.     while(p){
17.         int i=N-(N>>p);
18.         int v1=vs[p];
19.         int v2=v1>>4; v1&=15;
20.         int v3=v2>>4; v2&=15;
21.         int v4=v3>>4; v3&=15;
22.         for(int ii=0;ii<m;i+=2,ii+=2){
23.             ++E;
24.             int v=ii*2;
25.             v&=v<<v1;
26.             v&=v<<v2;
27.             v&=v<<v3;
28.             v&=v<<v4;
29.             if(v){
30.                 if(v&ii){
31.                     ++FS;
32.                     continue;
33.                 }
34.                 int j=i;
35.                 ++C;
36.                 do{
37.                     ++CI;
38.                     unsigned d=(v&-v);
39.                     unsigned vv=(i/d+i*(N/d))&(N-1);
40.                     if(vv>i) break;
41.                     v&=v-1;
42.                 }while(v);
43.                 if(v){
44.                     ++CS;
45.                     continue;
46.                 }else
47.                     ++CW;
48.             }else
49.                 ++FW;
50.             int j=i;
51.             v=a[i];
52.             do{
53.                 if(j&1) j+=N;
54.                 j>>=1;
55.                 v^=a[j]^=v^=a[j];
56.             }while(j<i);
57.         }
58.         m=N>>p;
59.         --p;
60.     }
61.     double e=E?1000.0/E:0;
62.     double c=C?1000.0/C:0;
63.     printf("T=%u/2^%d, FS/FW/C=%3.0f/%3.0f/%3.0f, CS/CW=%3.0f/%3.0f, CI=%4.2f\n",
64.         E,P,FS*e,FW*e,C*e,CS*c,CW*c,C?CI*1.0/C:0.0);
65.     if(P<=8){
66.         for(int i=0;i<N;i++)
67.             printf("%4d",a[i]);
68.         printf("\n");
69.     }
70.     delete[] a;
71. }

Консоль:

Код (Text):

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

T=268435456/2^30 означает, что из 2^30 индексов мы проверяли только четверть.
FS/FW/C=811/ 98/ 91 означает, что из 1000 случаев: 811 мы сразу откинули, в 98 перешли к перестановке, в 91 стали делать дополнительную проверку
CS/CW=608/392 означает что по результатам дополнительной проверки в полтора раза чаще приходится переходит к следующему индексу, чем начинать перестановку
CI=1.35 означает, что цикл дополнительной проверки в среднем выполняется чуть более одного раза.
В общем можно считать, что цель достигнута и сложность почти линейная. Еще можно развернуть цикл while(p), сделав вместо него P/2 циклов for(int ii=0;ii<m;i+=2,ii+=2), внутри убрать лишние v&=v<<vх, а в оставшиеся подставить константы из таблицы, только это будет слишком много кода.

 

Ух, жесть. Без поллитры не разберёшься.

 

Такое вот

Код (C):

1.  
2. static void swap_values (int* a, int* b)
3. {
4.     *a ^= *b;
5.     *b ^= *a;
6.     *a ^= *b;
7. }
8. static void swap_items (int* items, int count)
9. {
10.     int src, dst, next, half, value;
11.    
12.     half = count / 2;
13.    
14.     src = 1;
15.     dst = src * 2;
16.     next = src + 2;
17.    
18.     value = items[src];
19.        
20.     while (1)
21.     {
22.         if (dst < src)
23.         {
24.             if (dst < half)
25.             {
26.                 items[dst] = value;
27.                
28.                 if (next >= half)
29.                     break;
30.                    
31.                 src = next;
32.                 next += 2;
33.                 dst = src * 2;
34.                 value = items[src];
35.             }
36.             else
37.             {
38.                 swap_values (&value, &items[dst]);
39.                 src = dst;
40.                 dst -= count - dst - 1;
41.             }
42.         }
43.         else
44.         {
45.             swap_values (&value, &items[dst]);
46.             src = dst;
47.             if (dst < half)
48.                 dst = src * 2;
49.             else
50.                 dst -= count - dst - 1;
51.         }
52.     }
53. }
54.  

Только работает для 16 элементов, потому что рисунок с перестановками именно для них перед глазами висел. На 18 элементах "забывает" вставить один последний, надо над условиями для общего случая подумоть...

 

rmn, массив имеет длину степень двойки. Поэтому надо сразу на 32 элементах проверять.

 

Если убрать из кода все счётчики, то получится:

Код (C):

1. for(int P=1;P<=28;P++){
2.     unsigned N=1<<P,N1=N-1,P1=P-1,P2=P/2;
3.     unsigned *a=new unsigned [N];
4.     for(unsigned i=0;i<N;i++)
5.         a[i]=i;
6.     unsigned T=GetTickCount();
7.     for(unsigned i=N/2;i<N;i+=2){
8.         int v=0;
9.         DWORD p; _BitScanReverse(&p,i^N1); p=P1-p;
10.         if(p<P2){
11.             v=(i&(N1>>p))<<1;
12.             if(p>8){
13.                 v&=v<<(p-8); v&=v<<4; v&=v<<2; v&=v<<1;
14.             }else if(p>4){
15.                 v&=v<<(p-4); v&=v<<2; v&=v<<1;
16.             }else if(p>=2){
17.                 v&=v<<(p-2); v&=v<<1;
18.             }
19.         }
20.         if(v){
21.             if(v&i)
22.                 continue;
23.             do{
24.                 _BitScanReverse(&p,v&-v);
25.                 unsigned vv=((i>>p)+(i<<(P-p)))&N1;
26.                 if(vv>i) break;
27.             }while(v&=v-1);
28.             if(v)
29.                 continue;
30.         }
31.         int j=i;
32.         if(j&1) j+=N; j>>=1;
33.         v=a[j];
34.         do{
35.             int jj=j;
36.             if(j&1) j+=N; j>>=1;
37.             a[jj]=a[j];
38.         }while(j<i);
39.         a[j]=v;
40.     }
41.     printf("N=2^%d time=%u ms\n",P,GetTickCount()-T);
42.     if(P<=8){
43.         for(int i=0;i<N;i++)
44.             printf("%4d",a[i]);
45.         printf("\n");
46.     }
47.     delete[] a;
48. }

Время работы для массива слов:

Код (Text):

1. N=2^20 time=0 ms
2. N=2^21 time=31 ms
3. N=2^22 time=94 ms
4. N=2^23 time=172 ms
5. N=2^24 time=374 ms
6. N=2^25 time=811 ms
7. N=2^26 time=1810 ms
8. N=2^27 time=4056 ms
9. N=2^28 time=8955 ms

Для байтового массива:

Код (Text):

1. N=2^20 time=15 ms
2. N=2^21 time=16 ms
3. N=2^22 time=62 ms
4. N=2^23 time=125 ms
5. N=2^24 time=281 ms
6. N=2^25 time=639 ms
7. N=2^26 time=1357 ms
8. N=2^27 time=2995 ms
9. N=2^28 time=6770 ms
10. N=2^29 time=15928 ms
11. N=2^30 time=34928 ms

Если реальную перестановку не делать, а только определять с какого индекса её нужно начинать, то время выполнения уменьшается в 10-15 раз, отсюда напрашивается вывод что индексы проверяются достаточно быстро и в оптимизации нуждается сам цикл перестановок.

 

В некоторых случаях есть возможность перечислить все цепочки явно. Циклический сдвиг индекса эквивалентен его удвоению вятому по модулю 2^n-1, и в том случае когда 2^n-1 простое, а 2^n-2 делится на n можно просто домножая индекс на 3^n и получать элемент другой цепочки. К примеру для n=5 мы получаем 6 цепочек по 5 элементов которые можно начинать с индексов 1, 26, 25, 30, 5, 6, для n=7 имеем 18 цепочек, которые можно начинать с элементов 1, 28, 22, 108, 103, 90, 107, 75, 68, 126, 99, 105, 19, 24, 37, 20, 52, 59. А вот для n=4 или n=6 в нашем кольце появляются делители нуля и примитивный элемент, который позволил бы легко перечислить все цепочки, там уже не найти.

 

Такое вот

Код (C):

1.  
2. static void swap_items2 (int* items, int count)
3. {
4.     int src, dst, first, half, value;
5.     unsigned int bitmap;
6.    
7.     half = count / 2;
8.     bitmap = 0;
9.    
10.     first = src = 1;
11.     bitmap |= 1 << (src / 2);
12.     value = items[src];
13.  
14.     while (1)
15.     {
16.         if (src < half)
17.         {
18.             dst = src * 2;
19.             swap_values (&value, &items[dst]);
20.             src = dst;
21.         }
22.         else
23.         {
24.             dst = src - (count - src - 1);
25.             if (dst < half)
26.             {
27.                 if (bitmap & (1 << (dst / 2)))
28.                 {
29.                     items[dst] = value;
30.                     for (src=first; src < half && bitmap & (1 << (src / 2)); )
31.                         src += 2;
32.  
33.                     if (src < half)
34.                     {
35.                         first = src;
36.                         bitmap |= 1 << (src / 2);
37.                         value = items[src];
38.                     }
39.                     else
40.                         break;
41.                 }
42.                 else
43.                 {
44.                     swap_values (&value, &items[dst]);
45.                     bitmap |= (dst & 1) << (dst / 2);
46.                     src = dst;
47.                 }
48.             }
49.             else
50.             {
51.                 swap_values (&value, &items[dst]);
52.                 src = dst;
53.             }
54.         }
55.     }
56. }
57.  

Но тут дополнительная память нужна, 1 дворд на каждые 128 элементов. (Этот пример для любого четного N от 4 до 128).

 

Все перестановки состоят из ряда закольцованных цепочек. Любая цепочка начинается в первой половине по нечетному индексу; индекс следующего элемента цепочки равен index * 2, если он в первой половине и index - (count - index - 1), если он во второй половине. Все цепочки заканчиваются на том же элементе, с которого начались.

 

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

Код (Text):

1.  
2. N=4: 1
3. N=6: 1
4. N=8: 1 3
5. N=10: 1 3
6. N=12: 1
7. N=14: 1
8. N=16: 1 3 5 7
9. N=18: 1 3
10. N=20: 1
11. N=22: 1 3 5 7 9
12. N=24: 1 5
13. N=26: 1 5
14. N=28: 1 3 9
15. N=30: 1
16. N=32: 1 3 5 7 11 15
17. N=34: 1 3 5 11
18. N=36: 1 3 5 7 15
19. N=38: 1
20. N=40: 1 3 7 13
21. N=42: 1 3
22. N=44: 1 3 7
23. N=46: 1 3 5 7 9 15 21
24. N=48: 1 5
25. N=50: 1 3 7 21
26. N=52: 1 3 5 9 11 17 19
27. N=54: 1
28. N=56: 1 3 5 11
29. N=58: 1 3 5 19
30. N=60: 1
31. N=62: 1
32. N=64: 1 3 5 7 9 11 13 15 21 23 27 31
33. N=66: 1 3 5 7 11 13
34. N=68: 1
35. N=70: 1 3 5 15 23
36. N=72: 1 7
37. N=74: 1 3 5 9 11 13 17 25
38. N=76: 1 3 5 7 15 25 35
39. N=78: 1 3 7 11 33
40. N=80: 1 3
41. N=82: 1 3 9 27
42. N=84: 1
43. N=86: 1 3 5 7 9 13 15 17 21 29 37
44. N=88: 1 3 5 29
45. N=90: 1 3 5 9 11 13 19 33
46. N=92: 1 3 7 9 11 13 17 19 39
47. N=94: 1 3 5 7 9 11 15 17 21 23 31 33 45
48. N=96: 1 5 7 19
49. N=98: 1 5
50. N=100: 1 3 5 9 11 15 33
51. N=102: 1
52. N=104: 1 3
53. N=106: 1 3 5 7 9 11 13 15 17 21 25 35 45 49
54. N=108: 1
55. N=110: 1 3 9
56. N=112: 1 3 11 37
57. N=114: 1 3 5 9
58. N=116: 1 5 7 23 25
59. N=118: 1 3 5 7 9 13 17 21 25 29 39
60. N=120: 1 3 7 11 13 17 21 51
61. N=122: 1 11
62. N=124: 1 3 7 9 11 23 41
63. N=126: 1 5 25
64. N=128: 1 3 5 7 9 11 13 15 19 21 23 27 29 31 43 47 55 63
65.  

 

Ну и после того, как сам себе пояснил обобщенный алгоритм, упрощенный вариант.

Код (C):

1.  
2. static void swap_items3 (int* items, int count)
3. {
4.     int src, dst, first, half, value;
5.     unsigned int bitmap;
6.    
7.     half = count / 2;
8.     bitmap = 0;
9.    
10.     first = src = 1;
11.     bitmap |= 1 << (src / 2);
12.     value = items[src];
13.    
14.     while (1)
15.     {
16.         if (src < half)
17.             dst = src * 2;
18.         else
19.             dst = src - (count - src - 1);
20.            
21.         swap_values (&value, &items[dst]);
22.         src = dst;
23.  
24.         if (dst == first)
25.         {
26.             for (src=first; src < half && bitmap & (1 << (src / 2)); )
27.                 src += 2;
28.  
29.             if (src < half)
30.             {
31.                 first = src;
32.                 bitmap |= 1 << (src / 2);
33.                 value = items[src];
34.             }
35.             else
36.                 break;
37.         }
38.         else if (dst < half)
39.             bitmap |= (dst & 1) << (dst / 2);
40.     }
41. }
42.  

 

Так. Вернулся на свежую голову. Хочу отдельно поблагодарить rmn за рисунок. Я такие же рисунки рисовал, но его рисовка натолкнула меня на следующую идею.
Следствие 8: Для определения, является ли номер индекса массива первым элементом цепочки обмена, достаточно расчитать предыдущий элемент цепочки обмена и сравнить с текущим значением. Если текущее значение больше предыдущего, то элемент не является первым для цепочки.

Отсюда получаем следующее элегантное решение:

Код (C):

1.  
2. #include <stdio.h>
3.  
4. #define RANK  4
5. #define ITEMS  (1 << RANK)
6. #define TOTAL  (ITEMS << 1)
7.  
8. int main()
9. {
10.   int buf[TOTAL];
11.   int tmp;
12.  
13.   for (size_t i=0; i<TOTAL; ++i)
14.   buf[i] = i;
15.  
16.   for (size_t i=1; i<ITEMS; ++i)
17.   {
18.     // Check that previous element in chain is not less than current
19.     size_t j = (i & 1) ? (i >> 1) | ITEMS : (i >> 1);
20.     if (j < i)
21.       continue;
22.  
23.     size_t k = i;
24.     while (1)
25.     {
26.       k = (k & ITEMS) ? ((k << 1) & (TOTAL - 1)) | 1 : (k << 1);
27.       if (k == i)
28.         break;
29.  
30.       tmp = buf[i];
31.       buf[i] = buf[k];
32.       buf[k] = tmp;
33.     }
34.   }
35.  
36.  
37.   printf("Result:");
38.   for (size_t i=0; i<TOTAL; ++i)
39.   printf(" %02X", buf[i]);
40.   printf("\n");
41. }
42.  

 

Таким алгоритмом цепочка 5 10 20 9 18 будет переставлена два раза, там точно правильный ответ получается?!

 

Мы проверяем, является ли перебираемый индекс (от 0 до длина массива/2 - 1) первым (самым младшим) элементом последовательности. До i=20 цикл просто не дойдёт, так как 20 > 16.
Добавил отладочный вывод в код:

Код (Text):

1.  
2. Shuffle i=1 00 10 01 03 02 05 06 07 04 09 0A 0B 0C 0D 0E 0F 08 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F  
3. Shuffle i=3 00 10 01 11 02 05 03 07 04 09 0A 0B 06 0D 0E 0F 08 18 12 13 14 15 16 17 0C 19 1A 1B 1C 1D 1E 1F  
4. Shuffle i=5 00 10 01 11 02 12 03 07 04 14 05 0B 06 0D 0E 0F 08 18 09 13 0A 15 16 17 0C 19 1A 1B 1C 1D 1E 1F  
5. Shuffle i=7 00 10 01 11 02 12 03 13 04 14 05 0B 06 0D 07 0F 08 18 09 19 0A 15 16 17 0C 1C 1A 1B 0E 1D 1E 1F  
6. Shuffle i=9 00 10 01 11 02 09 03 13 04 0A 12 0B 06 0D 07 0F 08 18 14 19 05 15 16 17 0C 1C 1A 1B 0E 1D 1E 1F  
7. Shuffle i=11 00 10 01 11 02 09 03 13 04 0A 12 15 06 16 07 0F 08 18 14 19 05 1A 0B 17 0C 1C 0D 1B 0E 1D 1E 1F  
8. Shuffle i=13 00 10 01 11 02 09 03 13 04 0A 12 1A 06 0B 07 0F 08 18 14 19 05 0D 15 17 0C 1C 16 1B 0E 1D 1E 1F  
9. Shuffle i=15 00 10 01 11 02 09 03 13 04 0A 12 1A 06 0B 07 17 08 18 14 19 05 0D 15 1B 0C 1C 16 1D 0E 1E 0F 1F  
10. Result: 00 10 01 11 02 09 03 13 04 0A 12 1A 06 0B 07 17 08 18 14 19 05 0D 15 1B 0C 1C 16 1D 0E 1E 0F 1F
11.  

 

при 32х элементах есть 6 цепочек по 5 элементов, а код переставляет 8 цепочек, 2 из них переставляются по 2 раза, и 10 элементов оказываются не там где должны:
Result: 00 10 01 11 02 09 03 13 04 0A 12 1A 06 0B 07 17 08 18 14 19 05 0D 15 1B 0C 1C 16 1D 0E 1E 0F 1F

 

Блин, действительно, что-то не заметил.