Алгоритм подсчета количества допустимых блоков в перестановке

Хорошо, у меня осталось 1 представительство, потому что я назначил 200 вознаграждений за связанный вопрос: Поиск отсортированных подпоследовательностей в перестановке, поэтому я некоторое время не могу оставлять комментарии.

У меня есть идея: 1) Найдите все группы перестановок. Это: (78), (34), (12), (65). В отличие от теории групп, их порядок и положение, а также то, являются ли они смежными, имеют значение. Итак, группу (78) можно представить как структуру (7, 8, false), а (34) — как (3,4,true). Я использую нотацию Python для кортежей, но на самом деле может быть лучше использовать целый класс для группы. Здесь истинное или ложное означает смежное или нет. Две группы являются "соседними", если (max(gp1) == min(gp2) + 1 or max(gp2) == min(gp1) + 1) and contigous(gp1) and contiguos(gp2). Это не единственное условие непрерывности union(gp1, gp2), потому что (14) и (23) прекрасно сочетаются в (14). Это отличный вопрос для домашней работы в классе алгоритмов, но ужасный для собеседования. Подозреваю, что это домашнее задание.

Просто некоторые мысли:

На первый взгляд это кажется невозможным: полностью отсортированный массив будет иметь O(n²) допустимых подблоков.

Таким образом, вам нужно будет подсчитывать более одного действительного подблока за раз. Проверка достоверности подблока занимает O(n). Проверка того, полностью ли отсортирован подблок, также занимает O(n). Полностью отсортированный подблок содержит n(n - 1)/2 допустимых подблоков, которые можно подсчитать, не разбивая этот подблок дальше.

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

Всегда выбирая экстремум, который дает более равномерное разделение, это должно работать достаточно хорошо (в среднем O(n log n)) для "случайных" массивов. Однако я вижу проблемы, когда вы вводите что-то вроде (1 5 2 6 3 7 4 8), что, кажется, приводит к поведению O(n²). (1 4 7 2 5 8 3 6 9) будет похоже (надеюсь, вы видите закономерность). В настоящее время я не вижу способа поймать такой худший случай, но кажется, что для этого требуются другие методы разделения.

Этот вопрос включает в себя немного «математического трюка», но он довольно прост, как только вы его поймете. Однако остальная часть моего решения не соответствует критериям O (n log n).

Математическая часть:

Для любых двух последовательных чисел их сумма равна 2k+1, где k — наименьший элемент. Для трех это 3k+3, 4 : 4k+6 и для N таких чисел это Nk + sum(1,N-1). Следовательно, вам нужны два шага, которые можно выполнить одновременно:

1. Создайте сумму всех подмассивов.
2. Определить наименьший элемент подмассива.

Часть динамического программирования

Создайте две таблицы, используя результаты записей предыдущей строки, чтобы построить записи каждой последующей строки. К сожалению, я совершенно не прав, так как это все равно потребует n ^ 2 проверок подмассива. Фу!

Мое предложение

STEP = 2 // количество проверенных номеров

B [0,0,0,0,0,0,0,0]

B [1,1,0,0,0,0,0,0]

ДЕЙСТВИТЕЛЬНО(A,B) - если недействительно, переместите один

B [0,1,1,0,0,0,0,0]

ДЕЙСТВИТЕЛЬНО(A,B) - если действительно, переместите один и шаг

B [0,0,0,1,1,0,0,0]

ДЕЙСТВИТЕЛЬНО (А, В)

B [0,0,0,0,0,1,1,0]

ШАГ = 3

B [1,1,1,0,0,0,0,0] не в порядке

B [0,1,1,1,0,0,0,0] ok

B [0,0,0,0,1,1,1,0] не в порядке

ШАГ = 4

B [1,1,1,1,0,0,0,0] не в порядке

B [0,1,1,1,1,0,0,0] ok

.....

CON <- 0
STEP <- 2
i <- 0
j <- 0
WHILE(STEP <= LEN(A)) DO
 j <- STEP
 WHILE(STEP <= LEN(A) - j) DO
  IF(VALID(A,i,j)) DO
   CON <- CON + 1
   i <- j + 1
   j <- j + STEP
  ELSE
   i <- i + 1
   j <- j + 1
  END
 END
 STEP <- STEP + 1
END

Действительный метод проверяет, что все элементы являются последовательными

Никогда не проверял, но, может быть, все в порядке

Исходный массив не содержит дубликатов, поэтому сам должен быть последовательным блоком. Назовем этот блок (1 ~ n). Мы можем проверить, является ли блок (2 ~ n) последовательным, проверив, равен ли первый элемент 1 или n, который равен O (1). Точно так же мы можем проверить блок (1 ~ n-1), проверив, равен ли последний элемент 1 или n.

Я не могу превратить это в решение, которое работает, но, возможно, это поможет кому-то...

Как и все остальные, я просто выбрасываю это ... это работает для одного примера ниже, но YMMV!

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

1. Для каждого i в [1,N] вычислить B[A[i]] = i.

2. Пусть Count = общее количество подблоков с длиной> 1, что составляет N-выбор-2 (по одному для каждой возможной комбинации начального и конечного индекса).

3. Для каждого i рассмотрим A[i]. Игнорируя крайние случаи, пусть x=A[i]-1 и пусть y=A[i]+1. A[i] не может участвовать ни в одном подблоке, который не включает x или y. Пусть iX=B[x] и iY=B[y]. Здесь есть несколько случаев, которые следует рассматривать независимо друг от друга. Общий случай таков, что iX<i<iY<i. В этом случае мы можем удалить подблок A[iX+1 .. iY-1] и все промежуточные блоки, содержащие i. Таких подблоков (i - iX + 1) * (iY - i + 1) таких подблоков, поэтому назовем это число Исключенным. (Другие случаи оставлены читателю в качестве упражнения, как и крайние случаи.) Установите Count = Count — исключено.

4. Возврат счетчика.

Общая стоимость составляет N * (стоимость шага 2) = O(N).

WRINKLE: На шаге 2 мы должны быть осторожны, чтобы не исключить каждый подинтервал более одного раза. Мы можем добиться этого, только исключив подынтервалы, которые полностью или частично лежат справа от позиции i.

Пример:
A = [1, 3, 2, 4] B = [1, 3, 2, 4]

Начальный счет = (4*3)/2 = 6

i=1: A[i]=1, поэтому нужны подблоки с 2 в них. Мы можем исключить [1,3] из рассмотрения. Исключено = 1, Счет -> 5.

i=2: A[i]=3, поэтому нужны подблоки с 2 или 4 в них. Это исключает [1,3], но мы уже учли это, если смотреть прямо с i=1. Устранено = 0.

i=3: A[i] = 2, поэтому нужны подблоки с [1] или [3] в них. Мы можем исключить [2,4] из рассмотрения. Исключено = 1, Счет -> 4.

i=4: A[i] = 4, поэтому нам нужны подблоки с [3] в них. Это исключает [2,4], но мы уже учли это, если смотреть прямо с i=3. Устранено = 0.

Final Count = 4, что соответствует подблокам [1,3,2,4], [1,3,2], [3,2,4] и [3,2].

(Это попытка сделать N.log(N) наихудший случай. К сожалению, это неправильно — иногда он недосчитывается. Он ошибочно предполагает, что вы можете найти все блоки, просматривая только соседние пары меньших допустимых блоков. На самом деле у вас есть смотреть на тройки, четверки и т. д., чтобы получить все большие блоки.)

Вы делаете это со структурой, которая представляет подблок и очередь для подблоков.

  struct
c_subblock
{
  int           index   ;  /* index into original array, head of subblock */
  int           width   ;  /* width of subblock > 0 */
  int           lo_value;
  c_subblock *  p_above ;  /* null or subblock above with same index */
};

Выделите массив подблоков того же размера, что и исходный массив, и инициализируйте каждый подблок так, чтобы в нем был ровно один элемент. Добавляйте их в очередь по ходу. Если вы начнете с массива [ 7 3 4 1 2 6 5 8 ], вы получите такую ​​очередь:

очередь: ( [7,7] [3,3] [4,4] [1,1] [2,2] [6,6] [5,5] [8,8] )

Значения { index, width, lo_value, p_above } для подблока [7,7] будут {0, 1, 7, null}.

Теперь это легко. Простите псевдокод c-ish.

loop {
  c_subblock * const p_left      = Pop subblock from queue.
  int          const right_index = p_left.index + p_left.width;
  if ( right_index < length original array ) {
    // Find adjacent subblock on the right.
    // To do this you'll need the original array of length-1 subblocks.
    c_subblock const * p_right = array_basic_subblocks[ right_index ];
    do {
      Check the left/right subblocks to see if the two merged are also a subblock.
        If they are add a new merged subblock to the end of the queue.
      p_right = p_right.p_above;
    }
    while ( p_right );
  }
}

Это найдет их всех, я думаю. Обычно это O (N log (N)), но это будет O (N ^ 2) для полностью отсортированного или антисортированного списка. Я думаю, что на этот вопрос есть ответ: когда вы строите исходный массив подблоков, вы ищете отсортированные и антисортированные последовательности и добавляете их в качестве подблоков базового уровня. Если вы ведете счет, увеличьте его на (ширина * (ширина + 1))/2 для базового уровня. Это даст вам счет, ВКЛЮЧАЯ все подблоки длины 1.

После этого просто используйте описанный выше цикл, выталкивая и проталкивая очередь. Если вы считаете, вам нужно будет иметь множитель как для левого, так и для правого подблоков и перемножить их вместе, чтобы вычислить приращение. Множитель — это ширина самого левого (для p_left) или самого правого (для p_right) подблока базового уровня.

Надеюсь, это понятно и не слишком глючит. Я просто стучу, так что это может быть даже неправильно. [Позднее примечание. Это не работает в конце концов. См. примечание ниже.]