Количество элементов, удовлетворяющих отношению

Даны два массива:

2 5 6 4 3 7 1
5 1 6 2 3 7 4

подсчитайте количество элементов x, y, которые удовлетворяют условию, что x предшествует y в обоих массивах.

Прогресс на данный момент:

Отсортируйте массивы по их индексам. Например, это будет:

                     object: 1 2 3 4 5 6 7
indexes in the first array:  6 0 4 3 1 2 5
indexes in the secnod array: 1 3 4 6 0 2 5

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

Это имеет временную сложность (N ^ 2)/2, поэтому O (N ^ 2), что слишком медленно. Я понимаю, что лучшей сложности при наихудшем сценарии быть не может, но меня в основном интересует средний результат. Итак: есть ли лучший способ/алгоритм?

Я думал об использовании транзитивных свойств (если и (x,y), и (y,z) удовлетворяют условию, то и (x,z) ему удовлетворяет), но безуспешно.

Тестовые случаи

Для массивов:

2 5 6 4 3 7 1
5 1 6 2 3 7 4

Пары, удовлетворяющие условию:

(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7)

Для массивов:

1 2 3 4 5 6 7
1 2 3 4 5 6 7

Пары, удовлетворяющие условию:

(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7)

arrays computer-science computation-theory computer-science-theory
person FigsHigs    schedule 09.10.2016    source источник
comment
(x,y) принимает значения (2,5), (5,1), ..., (1,4) в вашем примере?   -  person Daniel Jour    schedule 09.10.2016
comment
В первом массиве 2 предшествует 5, а в следующем 5 намного раньше 2. Однако (5,1) верно. (1,4) нет. (6,7), (5,6) и т. д. правильно.   -  person FigsHigs    schedule 09.10.2016
comment
Ах хорошо. У вас есть несколько тестовых случаев?   -  person Daniel Jour    schedule 09.10.2016
comment
Дайте мне минуту, и я сгенерирую несколько.   -  person FigsHigs    schedule 09.10.2016
comment
Добавлены два теста с полным списком кортежей, удовлетворяющих условиям.   -  person FigsHigs    schedule 09.10.2016
comment
Извините, если это сбивает с толку. Правильно (5,1) должно быть, но из-за оптимизации - нас интересует только количество таких пар, получить (1,5) быстрее, чем получить (5,1). Однако исправил.   -  person FigsHigs    schedule 09.10.2016
comment
Вы приняли текущий ответ. Действительно ли это ответ на ваш вопрос? Для меня это звучит так, как будто вы спросили Как поймать зебру?, а ответ: Покрасьте ее в черный цвет, тогда она будет похожа на лошадь, не отвечая, как поймать зебру или лошадь. Я имею в виду, что вычисление результата из одного массива тоже не тривиально, или я упускаю из виду что-то очевидное?   -  person Marco13    schedule 10.10.2016
comment
Пожалуйста, смотрите мой другой комментарий (под ответом)   -  person FigsHigs    schedule 10.10.2016
comment
@FigsHigs Вы можете обновить вопрос в соответствии с вашим текущим подходом (для одного массива). (Кстати: если вы хотите ответить на комментарий, то использование @ уведомит человека, к которому вы обращаетесь. В противном случае комментарий, подобный вашему выше, может остаться незамеченным)   -  person Marco13    schedule 10.10.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

Принцип Beach Boys

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

В этом случае было бы неплохо, если бы верхний массив был упорядочен и просто [1, 2, 3 ...]? Это сделало бы решение этой проблемы намного проще, поскольку превращает проблему с двумя массивами в проблему с одним массивом.

Что ж, может быть и так! Вы можете сопоставить любую из этих задач с упорядоченным первым массивом.

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

2 5 6 4 3 7 1
5 1 6 2 3 7 4

Я утверждаю, что проблема выше эквивалентна проблеме ниже:

1 2 3 4 5 6 7
2 7 3 1 5 6 4

Сопоставления

Я просто делаю простую замену шифра 2->1 5->2 6->3 4->4 3->5 7->6 1->7 (Почему это конкретное сопоставление?). Это оставляет основную структуру проблемы прежней. Затем вы можете решить это, а затем отменить сопоставление.

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

Теперь у вас есть проблема с одним массивом, чтобы найти все пары:

2 7 3 1 5 6 4

Временную сложность этого я оставляю читателю в качестве упражнения.

P.S. Не забывайте о временной сложности отмены вашего сопоставления. Иногда вы будете решать проблему, думая, что будет легко обнаружить, что построение и деконструкция вашего отображения чрезвычайно дороги, и вам нужно вернуться к чертежной доске.

person Liyan Chang    schedule 09.10.2016
comment
Спасибо за ваш ответ. Я постараюсь над этим поработать. PS: В эквивалентной задаче, которую вы создали, опечатка, должно быть 2 7 3 1 5 6 4 вместо 2 6 3 1 5 6 4. В остальном это выглядит очень правильно. - person FigsHigs; 09.10.2016
comment
Хороший улов! Исправлено. - person Liyan Chang; 09.10.2016
comment
Извините, я не вижу, как это помогает. Вы трансформировали проблему в другую, и эта трансформация смутно оправдывается тем, что она упрощает задачу. Но, в конце концов, у вас есть один массив, и вычисление решения для этого по-прежнему сложно (т.е. O(n*2)), если только вы не примените некоторые методы, которые вы могли бы в равной степени применить к массиву. оригинальные массивы. - person Marco13; 10.10.2016
comment
Использование, например, транзитивного свойства намного проще в задаче с одним массивом. Тем не менее, я должен признать, что хотя я и заставил программу работать немного быстрее, я все еще далек от заветной временной сложности. - person FigsHigs; 10.10.2016