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

Тема в разделе "WASM.A&O", создана пользователем SadKo, 29 дек 2016.

  1. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Всем привет!
    Недавно столкнулся с такой задачей:
    Есть массив, размер которого степень двойки (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 или что-то вроде того.
     
  2. Black_mirror

    Black_mirror Active Member

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

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Я, когда исследовал проблему, обнауржил несколько интересных свойств.
    Если битово представить значения старого и нового индекса элемента, то получим следующее:
    Код (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. Если кто знает, как это сделать - задача будет решена.
     
  4. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Код (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 как начальная, в этом случае сразу переходим к перестановке элементов, проверку что в индексе есть группа длиннее начальной, в этом случае берём следующий индекс, иначе выполняем проверочный цикл и по нему уже решаем нужно переставлять элементы или нет.
     
  5. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Динамическую память, увы, нельзя использовать.

    У меня решение такое вышло (но это 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. Что-то форма набора текста сильно тормозит.
     
  6. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Код:
    Код (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х, а в оставшиеся подставить константы из таблицы, только это будет слишком много кода.
     
  7. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Ух, жесть. Без поллитры не разберёшься.
     
  8. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    Такое вот :)
    Код (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 элементах "забывает" вставить один последний, надо над условиями для общего случая подумоть...
     
  9. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    rmn, массив имеет длину степень двойки. Поэтому надо сразу на 32 элементах проверять.
     
  10. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Если убрать из кода все счётчики, то получится:
    Код (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 раз, отсюда напрашивается вывод что индексы проверяются достаточно быстро и в оптимизации нуждается сам цикл перестановок.
     
  11. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    В некоторых случаях есть возможность перечислить все цепочки явно. Циклический сдвиг индекса эквивалентен его удвоению вятому по модулю 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 в нашем кольце появляются делители нуля и примитивный элемент, который позволил бы легко перечислить все цепочки, там уже не найти.
     
  12. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    Такое вот :)
    Код (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).
     
  13. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    [​IMG]


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

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    Начальные индексы цепочек для разных 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.  
     
  15. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    Ну и после того, как сам себе пояснил обобщенный алгоритм, упрощенный вариант.
    Код (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.  
     
  16. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Так. Вернулся на свежую голову. Хочу отдельно поблагодарить 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.  
     
  17. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Таким алгоритмом цепочка 5 10 20 9 18 будет переставлена два раза, там точно правильный ответ получается?!
     
  18. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Мы проверяем, является ли перебираемый индекс (от 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.  
     
    Последнее редактирование: 2 янв 2017
  19. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    при 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
     
  20. SadKo

    SadKo Владимир Садовников

    Публикаций:
    8
    Регистрация:
    4 июн 2007
    Сообщения:
    1.610
    Адрес:
    г. Санкт-Петербург
    Блин, действительно, что-то не заметил.