«К-трансформированные» перестановки - PullRequest
Новая
       48

«К-трансформированные» перестановки

11 голосов
/ 26 августа 2011

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

Вот проблема (PDF предоставлена ​​UVA) :

Рассмотрим последовательность из nцелые числа <1 2 3 4 ... n>.Поскольку все значения различны, мы знаем, что существует n факторных перестановок.Перестановка называется K-преобразованной, если абсолютная разница между исходной позицией и новой позицией каждого элемента не превышает K. Учитывая n и K, вы должны выяснить общее количество K-преобразованных перестановок.

...

Входные данные: Первая строка ввода представляет собой целое число T (T <20), которое указывает количество тестовых случаев.Каждый случай состоит из строки, содержащей два целых числа n и K. (1 <= n <= 10 ^ 9) и (0 <= K <= 3). </p>

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

Установщик проблемы, Сохель Хафиз , классифицировал эту проблему как " Экспонирование быстрой матрицы ".К сожалению, поиск в Google, на который я ссылался здесь, похоже, не дает никаких релевантных ссылок, кроме страницы Википедии, заполненной математическим жаргоном и нотацией (Википедия оказалась для меня плохой заменой любого учебника по математике).

Вот что я сделал до сих пор:

Этот код будет вычислять по рекурсии число K-преобразованных перестановок для низких значений n и k, но он слишком сложный.Достаточно хорошо построить таблицу для поиска шаблонов: 

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int permute(int * a, int size, int i, int k)
{
  int j;
  int total = 0;
  int x = size-i;
  int low=0;
  int high=size;
  if (i == 0)
  {
/*    for (j=0;j<size;j++)
      printf("%d, ", a[j]);
    printf("\n");
*/    return 1;
  }
  if (x-k>0)
    low = x-k;
  if (x+k+1<size)
    high = x+k+1;
  for (j=low;j<high;j++)
  {
    int b[size];
    memcpy(b,a,size*sizeof(int));
    if (b[j] == 0)
    {
      b[j] = x+1;
      total += permute(b,size,i-1,k);
    }
  }
  return total;
}

int main() 
{
  int n, k, j, y, z;
  int * arr;
  /*scanf("%d %d", &n,&k);*/ k=2;
  for (n=0;n<14;n++)
  {
    int empty[n];
    for (j=0;j<n;j++)
      empty[j] = 0;
    arr = empty;  
    z = permute(arr, n, n, k);
    y = magic(n,k);
    printf("%d %d\n",z, y);
  }
  return 0;
}

Первое, что я понял, было то, что k = 1 - это, очевидно, последовательность Фибоначчи.Магическая функция в основном здесь - кое-что, что я понял позже, почти случайно.Это работает ТОЛЬКО для k = 2, но точно до n = 14.

int magic(int n, int k)
{
  if (n<0)
    return 0;
  if (n==0)
    return 1;
  if (n==1)
    return 1;
  return 2*magic(n-1,k) + 2*magic(n-3,k) - magic(n-5,k);  
}

Очень странно!Я не знаю значимости этой функции, но ее можно упростить для запуска в цикле, чтобы запустить достаточно быстро, чтобы завершить K = 2 для значений до 10 ^ 9.

Все, что осталосьсостоит в том, чтобы найти нерекурсивное уравнение, которое может найти любое значение для K = 3 за разумное количество времени (до 10 с).

РЕДАКТИРОВАТЬ: Меня интересует алгоритм, используемый длярешить проблему для любых заданных n и k в течение разумного периода времени.Я не ожидаю, что кто-то на самом деле подтвердит, что их алгоритм работает, написав код в соответствии со спецификациями правил конкурса, и в ответе я ищу описание того, как подойти к проблеме и применить численные методы для достижения решения.

Ответы [ 2 ]

6 голосов
/ 26 августа 2011

Проблема состоит из двух частей. Сначала выясним формулу повторения для k=0, 1, 2, 3. Вторая часть вычисляет значения для больших n, используя формулу повторения.

Для первой части:

Пусть p(n, k) будет числом перестановок n элементов, которые k -трансформируются. Когда k=0 повторение просто p(n, 0) = 1.

Для k=1 сначала рассмотрим, где 1 переходит в перестановку. Он либо идет в позицию 1, либо в позицию 2. Если он идет в позицию 1, то оставшиеся элементы - это просто исходная проблема с элементами n-1. Итак, у нас есть p(n, 1) = p(n-1, 1) + .... Если первый элемент перейдет в положение 2, то что? В этом случае второй элемент должен перейти в положение 1. На данный момент у вас есть исходная проблема с n-2 элементами. Таким образом, рецидивом является p(n, 1) = p(n-1, 1) + p(n-2, 1), который является последовательностью Фибоначчи.

Для k=2 и k=3 вы получаете больше возможностей, но рассуждения те же. [до сих пор прорабатывают точные повторения]

Вторая часть вычисляет решение для повторений для больших значений n. Для этого вы помещаете повторение в матричную форму и повторяете квадрат / умножение, чтобы получить большие степени матрицы. Для случая k=1 матрица: 

A = [0 1]
    [1 1]

Чтобы получить p(n + 2, 1), вам нужно вычислить A^n * [1, 1].

5 голосов
/ 26 августа 2011

Поскольку K низкое значение, оно естественным образом падает при возведении в матрицу.

Каждый элемент может закончить самое большее K позиций от его начальной позиции. Это дает максимум (2 K - 1) позиций, но некоторые позиции уже могут быть заняты. Вы можете иметь 2 2 K - 1 возможных конфигураций (из ближайших (2 K -1) слотов) при размещении предмета. Каждый новый элемент в любой незанятой позиции будет генерировать новую конфигурацию, новую и новую ...

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

Рассмотрим вектор отсчета v ; Каждая ячейка в ней представляет количество способов добраться до какой-либо конфигурации за n шагов. Начните с начального вектора счета (все нули, кроме одного 1, представляющего пустую конфигурацию, n = 0). Если вы умножите этот вектор на матрицу ( v x A ), вы сдвинете эти значения на один шаг вперед ( n = 1). Повторите для дополнительных шагов.

Теперь самое интересное. Если вы умножите эту матрицу на себя ( A x A ), вы получите матрицу для продвижения вперед на два поколения. Снова ( A 2 x A 2 ), и вы получите матрицу для перемещения 4 поколений. Вы можете использовать эту технику, чтобы продвинуть ее на несколько тысяч (или миллионов) поколений вперед всего за несколько итераций.

Вы можете узнать больше о возведении в степень, возведя в квадрат в Википедии.

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

a & middot; x 1 + b & middot; x 2 = x 3
a & middot; x 2 + b & middot; х 3 = х 4

Решите для a и b . Затем, чтобы сгенерировать последовательность, вы умножаете последние два числа на a и b и добавляете, чтобы получить следующее.

Если это не воспроизводит последовательность, вы можете увеличить размер:

a & middot; x 1 + b & middot; x 2 + c & middot; x 3 = x 4
a & middot; x 2 + b & middot; x 3 + c & middot; x 4 = x 5
a & middot; x 3 + b & middot; x 4 + c & middot; x 5 = x 6

Решите для a , b и c . Увеличивайте дальше, пока не получите то, что работает. Если вы сделаете еще один шаг, вы должны получить недостаточно определенную систему.

Может случиться, что нет рекуррентного отношения (по крайней мере, линейного). В этом случае вы можете увеличить размер, но вы никогда не найдете ничего, что работает.

Взять простой пример. Давайте рассмотрим K = 1. Это даст нам окрестность размера 3 (= 2 K + 1) и 8 различных конфигураций (= 2 2 K + 1 ).

Чтобы выбрать нотацию, я буду использовать # для занятых или недоступных и . бесплатно.

Чтобы сгенерировать матрицу, мы должны рассмотреть, какие шаблоны можно преобразовать в какие, добавив один символ.

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

  • Для шаблона ### у нас нет свободных мест для размещения чего-либо, так что это тупик.

  • Для остальных шаблонов можно поместить символ в любое свободное место, а затем сдвинуть шаблон на один пробел (переместившись в следующую позицию).

Матрица может выглядеть так: 

    ... ..# .#. .## #.. #.# ##. ###
...  1   0   0   0   0   0   0   0
..#  0   0   1   0   0   0   0   0
.#.  0   0   0   0   1   0   0   0
.##  0   0   0   0   0   0   1   0
#..  0   0   1   0   1   0   0   0
#.#  0   0   0   0   0   0   1   0
##.  0   0   0   0   0   0   1   0
###  0   0   0   0   0   0   0   0

В качестве исходного шаблона мы возьмем #...Это потому, что мы не можем поместить первый символ перед началом последовательности.Последовательность из одного символа может быть записана только одним способом, поэтому начальный вектор-счет становится 0 0 0 0 1 0 0 0.

Последний требуемый шаблон - #...После конца последовательности нет символа, но остальные должны быть заполнены.Модель такова после смены.Это означает, что мы хотим посмотреть на положение 5 в векторе (считая от 1).

Первые несколько значений, которые мы получаем: 

n   p(n,1)
1        1
2        2
3        3
4        5
5        8
6       13
7       21
8       34

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

Как только у нас будет несколько значений, мы можем попытаться найти отношение повторения.Сначала давайте попробуем систему размера 1:

1 · a = 2

Это решило бы a =2. Но если мы попробуем следующее значение, мы увидим, что в случае сбоя уже на следующем значении:

2 · a = 2 · 2 = 4 ≠ 3.

Далее, попробуем систему размера 2:

1 · a + 2 · b = 3
2 · a + 3 · b = 5

Это решает до a = b =1. Это фактически сгенерирует всю последовательность.

3 · a + 5 · b = 3 · 1 + 5 · 1 = 8
5 · a + 8 · b = 5 · 1 + 8 · 1 = 13
...

Если мы попробуем четноебольшая система, мы столкнемся с проблемами:

1 · a + 2 · b + 3 · c = 5
2 · a + 3 · b + 5 · c = 8
3 · a + 5 · b + 8 · c = 13

Thявляется решающим для a = 1 - c , b = 2 - c , без значения для c .

Если мы попробуем последовательность для K = 2 (генерируется с помощью вышеуказанного метода): 1 2 6 14 31 73 172 400 932 2177

Это не будетдать правильное решение до размера 5: a = -1, b = 0, c = 2, d = 0, e = 2. Это то же отношение, которое вы нашли.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...