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

Ответ 1

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

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

Ответ 2

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

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

Итак, вам нужно будет подсчитать одновременно несколько действительных подблоков. Проверка правильности подблока - O (n). Проверка того, является ли подблоком полностью отсортированным, является O (n). Полностью отсортированный подблок содержит n & middot; (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) будет похож (надеюсь, вы увидите шаблон). В настоящее время я не вижу трюка, чтобы поймать этот худший случай, но, похоже, он требует других методов расщепления.

Ответ 3

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

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

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

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

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

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

Ответ 4

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

STEP = 2//количество пройденного номера

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

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

VALID (A, B) - если не действителен, переместите один

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

VALID (A, B) - если действительный переместить один и шаг

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

VALID (A, B)

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

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

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

Ответ 5

(Это попытка сделать это 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 */
};

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

queue: ([7,7] [3,3] [4,4] [1,1] [2,2] [6,6] [5,5] [8,8])

Значения {index, width, lo_value, p_above} для subbblock [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) субблока базового уровня.

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

Ответ 6

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

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

• Foreach я в [1, N], вычислить B [A [i]] = i.

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

• Прежде всего, рассмотрим 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 - я + 1) такие подблоки, поэтому назовите это число Eliminated. (Другие случаи, оставшиеся как упражнение для читателя, также как и те, которые относятся к краям). Set Count = Count - Eliminated.

• Возврат.

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

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

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

Начальное value = (4 * 3)/2 = 6

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

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

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

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

Конечный счет = 4, соответствующий подблокам [1,3,2,4], [1,3,2], [3,2,4] и [3,2].

Ответ 7

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

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