минимальные проверки, чтобы найти повторы в списке - PullRequest
Новая
       3

минимальные проверки, чтобы найти повторы в списке

3 голосов
/ 27 сентября 2011

Учитывая последовательность (d1, d2, ..., dn), я хочу оценить произведение (1 - Dij) для всех i! = J, где Dij = 1, если di = dj, и 0 в противном случае.

Код, который у меня есть, проверяет Dij только тогда, когда я 

prod = 1;
for (int i=1; i<n; ++i) {
    for (int j=i; j<=n; ++j) {
        prod *= (1 - Dij);
    }
}

Я знаю, что могу остановиться, когда получаю Dij = 1, но я пытаюсь получить минимальное выражение для проверки Dij.Таким образом, у меня есть одно выражение, а затем я могу использовать разностные последовательности и оценивать его.Так что я знаю, что могу сделать i<j вместо i != j.Поэтому я хочу расширить этот продукт и получить что-то подобное для n = 3: 

(1 - D12) (1 - D13) (1 - D23) = 1 - D12 - D13 - D23 + D12*D13 + D12*D23 + D13*D23 - D12*D13*D23

Но я могу сделать еще кое-что.На самом деле это выражение всегда равно 

1 - D12 - D13 - D23 + 3 * D12*D13 - D12*D13*D23

Мои вопросы:

  1. Почему D12 * D13 = D12 * D23?Это всегда верно (то есть не имеет значения, что такое d-последовательность), но я не совсем понимаю, почему, потому что мне кажется, что это означает D13 = D23, что не всегда верно (это зависит от d-последовательности).,Это отношение помогает уменьшить выражение.

  2. Как мне найти все подобные отношения и получить минимальное выражение?Является ли выражение выше минимальным?Я даже не знаю.

Ответы [ 3 ]

3 голосов
/ 27 сентября 2011

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

2 голосов
/ 27 сентября 2011

Я могу ответить 1 для вас.Рассмотрим эти два случая:

Случай 1: D13 = D23

Здесь вы можете просто умножить на D12 с обеих сторон, чтобы получить D12 * D13 = D12 * D23.

Случай 2: D13 != D23

Это означает, что либо d1 = d3 XOR d2 = d3, но не оба .Поэтому мы знаем, что d1 != d2.Это означает, что D12 = 0.Поэтому 

D12 * D13 = 0 * D13 = 0 = 0 * D23 = D12 * D23

Проблема с вашей логикой, когда вы думаете, что это подразумевает D13 = D23, заключается в том, что вы не можете разделить на 0, а D12 может быть 0 (как всегда происходит во втором случае).

Ваш второй вопрос интересен, и я не знаю ответа на макушку, но вот некоторые замечания, которые могут быть полезны.

Нарисуйте числа 1, 2, ..., n подряд: 

1  2  3 ... n

Учитывая выражение D_(i1,j1) * D_(i2,j2) * ... * D_(ik,jk), сделайте дугу из i1 to j1 и i2 to j2 и так далее.Это превращает эту строку в граф (вершины - это числа, ребра - это дуги).

Каждый связанный компонент этого графа представляет собой подмножество числа 1, 2, ..., n, и в целом это дает нам установить раздел из {1, 2, ..., n}.

Факт: Любые два термина, которые имеют одинаковый соответствующий набор разделов, равны.

Пример: 

D12 * D23 = D12 * D13

               ---------
              |         |
1 -- 2 -- 3 = 1 -- 2    3

Иногда этот факт будет означатьСтепень та же, что и в случае выше, и иногда степень будет уменьшаться, как в 

D12 * D13 * D23

 ---------
|         |
1 -- 2 -- 3

В результате теперь вы можете выразить произведение (1 - Dij) как сумму по заданным разделам:

\prod_{i<j} ( 1 - Dij ) = \sum_{P set partition of \{1,2,...,n\}} c_P * m_P

, где мономиальный термин задается как 

mP = mP1 * mP2 * ... * mPk

при P = P1 union P2 union ... union Pk, а если Pi = { a < b < c < ... < z }, то 

m_Pi = Dab * Dac * ... * Daz

Наконец, коэффициент коэффициента равенпросто 

c_P = \prod (#P1)! (#P2)! ... (#Pn)!

Поработав, я теперь уверен, что это относится к http://math.stackexchange.com, а не сюда.

0 голосов
/ 27 сентября 2011

Я не следил за математикой, но разве это не то, что вы бы закодировали с использованием хеш-таблицы, или, возможно, даже разреженного битового массива, если вы знаете, что размер di ограничен? Просто выполните итерацию по списку, заполнив структуру данных «1» в позиции, соответствующей значению di - если это уже 1, верните 0. Если вы завершите (за n шагов), верните 1. Это должно быть O (п).

...