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

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

  1. SadKo

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

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

    maxdiver Max

    Публикаций:
    0
    Регистрация:
    18 июл 2006
    Сообщения:
    308
    Адрес:
    Саратов
  3. SadKo

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

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

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    чё-то я не въехал в задачу: чётными/нет по индексу элемента иль содержимому элемента?
     
  5. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.241
    ежель я ничего не путаю ==>> надо перевести начальную цепочку в цепочку доменов, где каждый элемент домена состоит из итого элемента правой и левой подпоследовательностей? левый элемент домена должен быть по возможности чётом, а правый нечётом?