Выбирая пять чисел, которые суммируются с S

Учитывая массив A из N неотрицательных чисел, мне интересно найти количество способов выбрать 5 чисел (из разных позиций в массиве), чтобы их сумма была S.

В O(N^3) есть простое решение:

Let H be a hash table of (sum, position of leftmost element of sum)
for i = 0, N
    for j = i + 1, N
        H.add(A[i] + A[j], i)

numPossibilities = 0
for i = 0, N
    for j = i + 1, N
        for k = j + 1, N
            numPossibilities += H.get(S - (A[i] + A[j] + A[k]), k)

Где H.get(x, y) возвращает количество элементов в хеше, сумма которых имеет тот же хеш, что и x, а самый левый элемент которого больше k.

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

Предполагая, что входы будут довольно случайными (так что хеширование наихудшего случая), есть ли алгоритм, который может решить это в O(N^2) или, может быть, O(N^2 log N) или даже O(N^3), если он выполняется во всех случаях? Я думаю, что двоичный поиск может помочь, но я не вижу, как справляться с перекрывающимися индексами.

Вышеупомянутое решение на практике намного лучше, чем наивное решение для 5-для-петель, однако у меня есть чувство, что мы можем сделать намного лучше, следовательно, этот вопрос.

Если вы можете доказать, что такой алгоритм не существует, как можно оптимизировать вышеуказанное решение?

Разъяснение:

Вышеупомянутый алгоритм действительно O(N^5) в худшем случае, например, когда данный массив содержит ничего, кроме числа 1, и мы имеем S = 5. В среднем, однако, метод H.get намного ближе к O(1), поэтому моя средняя кубическая сложность.

Если вы реализуете это и запускаете его на 1000 случайных чисел в большом интервале (скажем 0 до Int32.MaxValue), вы увидите, что он работает относительно быстро. Тем не менее, нетрудно найти входы, для которых это занимает много времени. Даже если мы не сможем добиться этого достаточно быстро для всех равных чисел, какие оптимизации мы могли бы сделать?

При тех же предположениях, можем ли мы сделать лучше, асимптотически или, по крайней мере, на практике?

Ответ 1

Я думаю, что факт, что цифры должны иметь разные позиции, - это красная селедка. Вы можете использовать принцип включения-исключения для подсчета числа всех позиций (i, j, k, l, m), где x [i] + x [j] + x [k] + x [l] + x [m] = S и i, j, k, l, m различны:

 sums with i!=j,i!=k,i!=l...,l!=m  = all sums 
                                   - sums with i=j
                                   - ...
                                   - sums with l=m
                                   + sums with i=j and j=k
                                   + ...
                                   + sums with k=l and l=m
                                   - ...
                                   + sums with i=j=k=l=m

Вычисление сумм справа, кроме первого, выполняется в O (N ^ 2 log N). Например, чтобы найти число позиций (i, i, k, l, m) таких, что x [i] + x [i] + x [k] + x [l] + x [m] = S вы можете создать отсортированные массивы с суммами {2a + b} и {c + d} и проверить, имеют ли они элементы x, y такие, что x + y = S.

Основной алгоритм

Итак, достаточно вычислить, сколько из них есть (i, j, k, l, m), где x[i]+x[j]+x[k]+x[l]+x[m]=S и i, j, k, l, m необязательно различаются. В принципе, вы можете использовать решение Moron таким образом:

Создайте отсортированный массив сумм {a + b: a, b - числа из массива}; группировать равные элементы в один, помня счетчик. Например, для массива [1,1,3] вы получаете девять сумм [2,2,2,2,4,4,4,4,6] формы a + b. Затем вы группируете одни и те же элементы, запоминая подсчеты: [(2,4), (4,4), (6,1)]. Этот шаг равен O (N ^ 2 log N).
Для каждого e подсчитывайте, сколько пар есть пары элементов, которые суммируются с S-e. Как и в решении Морона, у вас есть два указателя: один идет вправо, один идет влево. Если сумма слишком низкая, переместите первый указатель, увеличивая сумму; если сумма слишком высока, переместите второй указатель, уменьшающий ее.

Предположим, что сумма верна. Это означает, что один указывает на (a, x) и второй на (b, y), где a + b = S-e. Увеличьте счетчик на x * y и переместите оба указателя (вы можете переместить только один указатель, но на следующем шаге не будет совпадения, а второй указатель будет перемещен затем.).

Например, для массива [(2,4), (4,4), (6,1)] и Se = 8 первый указатель указывает на (2,4), а второй на (6,1). Так как 2 + 6 = 8, вы добавляете 4 и перемещаете оба указателя. Теперь они оба указывают на (4,4), поэтому вы увеличиваете счетчик на 16. Не останавливайтесь! Указатели переходят друг к другу, и вы получаете сначала на (6,1), секунду на (2,4), увеличиваете счетчик на 4.

Итак, в конце есть 4 + 16 + 4 = 24 способа получить 8 как сумму из 4 элементов из [1,1,3]:

>>> len([k for k in itertools.product([1,1,3],repeat=4) if sum(k) == 8])
24

Prelude Control.Monad> length [k | k <- replicateM 4 [1,1,3], sum k == 8]
24

Повторяя это для каждого e, вы получите количество способов получить S как сумму из 5 элементов.

Для [1,1,1,1,1] и Se = 4 массив сумм будет [(2,25)], и вы получите, что существует 625 способов получить сумму 4.

Для каждого e этот шаг является линейным по размеру массива (так что O (N ²)), поэтому цикл принимает O (N ³).

О включении-исключении:

Вызовите пятизначную (i, j, k, l, m) "правильную", если x [i] + x [j] + x [k] + x [l] + x [m] = S. Цель состоит в том, чтобы подсчитать количество собственных пятикратных (i, j, k, l, m), где i, j, k, l, m попарно различны. Основной алгоритм может рассчитывать в O (N ^ 3), сколько из них имеет правильные пятистрочные числа, которые не обязательно являются отдельными компонентами. Остальное дело в том, чтобы считать эти "неправильные" кортежи.

Рассмотрим подмножества собственных пятикратных чисел

A _xy= {(i, j, k, l, m): индексы на x-м и y-м месте одинаковы}

Например, A ₂₄ - это набор правильных пятикратных (i, j, k, l, m), где j = l.

Набор неправильных пятикратных чисел:

A ₁₂ ∪ A ₁₃ ∪... ∪ A ₄₅

Подсчет его мощности с помощью включения-исключения:

| A ₁₂ ∪ A ₁₃ ∪... ∪ A ₄₅ | = | A ₁₂ | + | A ₁₃ | +... + | A ₄₅ | - | A ₁₂ ∩ A ₂₃ | -... - | A ₃₄ ∩ A ₄₅ | +... + | A ₁₂ ∩ A ₂₃ ∩... ∩ A ₃₅ ∩ A ₄₅ |

Здесь есть 2 ¹⁰= 1024 слагаемых. Но много мощностей одинаково.

Единственное, что вы должны учитывать:

X ₁= | A ₁₂ | - пятикратные с я = j
X ₂= | A ₁₂ ∩ A ₂₃ | - пятикратные с я = j = k
X ₃= | A ₁₂ ∩ A ₂₃ ∩ A ₃₄ | - пятикратные с я = j = k = l
X ₄= | A ₁₂ ∩ A ₂₃ ∩ A ₃₄ ∩ A _{45суб > | - пятикратные с я = j = k = l = m}
X ₅= | A ₁₂ ∩ A ₃₄ | - пятикратные с я = j, k = l
X ₆= | A ₁₂ ∩ A ₂₃ ∩ A ₄₅ | - пятикратные с я = j = k, l = m

Вы можете наблюдать, переставляя, все остальные наборы представлены здесь. Например, A ₂₄ имеет ту же мощность, что и A ₁₂.

Подсчет мощностей этих 6 наборов довольно прост. Для первого вы создаете массивы {2a + b} и {c + d} и подсчитываете, сколько общих элементов; для других есть только 3 или менее свободных переменных, поэтому даже простой цикл даст вам O (N ^ 3).

Чтобы упростить сумму, я написал следующую программу Haskell:

import Control.Monad
import Data.List
import qualified Data.Map as Map

-- Take equivalence relation, like [(1,2),(2,3)] and return its partition, like [3,1,1]
f xs = sort $ map length $ foldr f (map return [1..5]) xs
       where f (x,y) a = let [v1] = filter (x `elem`) a
                             [v2] = filter (y `elem`) a
                         in if v1 == v2 then a else (a \\ [v1,v2]) ++ [v1++v2]

-- All 1024 subsets of [(1,2),(1,3), ..., (4,5)]
subsets = filterM (const [False, True]) [(i,j) | i <- [1..5], j <- [i+1..5]]

res = Map.fromListWith (+) $ map (\k -> (f k, (-1)^(length k))) subsets

*Main> res
Loading package array-0.3.0.1 ... linking ... done.
Loading package containers-0.3.0.0 ... linking ... done.
fromList [([1,1,1,1,1],1),([1,1,1,2],-10),([1,1,3],20),([1,2,2],15),([1,4],-30),([2,3],-20),([5],24)]

что означает, что формула

все подмножества - 10X ₁ + 20X ₂ - 30X ₃ + 24X ₄ + 15X ₅ - 20X ₆.

Check:

Сколько из них есть пять строк в [0,0,0,..., 0], суммируя до 0? Один из способов вычислить это прямо, второй способ - использовать формулу (и не заботиться о разных позициях):

direct x = x*(x-1)*(x-2)*(x-3)*(x-4)
indirect x = x^5 - 10 * x^4 + 20 * x^3 + 15 * x^3 - 30 * x^2 - 20*x^2 + 24*x

*Main> direct 100
9034502400
*Main> indirect 100
9034502400

Другие замечания:

Кроме того, существует решение O (a _n log a _n): Вычислить (x ^{a ₁} +... + x ^{a _n}) ⁵ с использованием FFT, результатом является коэффициент при x ^S. Это позволяет использовать несколько _i, но вы можете вычесть такие многочлены, как (x ^{2a ₁} +... + x ^{2a _n}) ⁵ * (x ^{a ₁} +... + x ^{a _n}) ³ и т.д. в соответствии с принципом включения-исключения.

В некоторых ограниченных моделях вычислений было показано для решения этой проблемы требуется O (N ^ 3) время.

Ответ 2

O (N ^ 3) представляется возможным (хотя я не пытался его доказать).

Возьмите все возможные пары и создайте новый массив (скажем, B) размера O (N ^ 2), который содержит сумму всех возможных пар. Также отслеживайте индекс двух элементов из исходного массива, который дал эту сумму. - O (N ^ 2)

Теперь отсортируйте массив - O (N ^ 2LogN).

Теперь для каждого элемента a в исходном массиве попробуйте найти два элемента из B, которые суммируются с S-a. Так как B сортируется, это можно сделать в O (B) времени: Начните с двух указателей, один на макс и один на мин.

Если сумма этих двух > S-a, уменьшите указатель около макс.

Если сумма этих двух < S-a, увеличьте указатель около мин.

Если сумма равна, то вы нашли одну пару кандидатов и новый отсортированный подматрица, в котором будет искать следующую возможную пару кандидатов. (Вы должны убедиться, что два элемента B входят из четырех элементов A). (Здесь могут быть потенциальные проблемы)

Таким образом, вы можете подсчитать количество раз, когда S-a встречается как сумма двух элементов B, которые исходят из четырех элементов исходного массива (не включая a).

So O (N ^ 2) время для O (N) элементов - O (N ^ 3).

Надеюсь, что это поможет.

Ответ 3

Вы можете сделать это в O (N * S) с динамическим программированием:

static int count(int[] A, int S) {
    final int K = 5;
    // In count[n][s] we'll count the number of ways you can pick n numbers such that their sum is s
    int[][] count = new int[K+1][S+1];

    count[0][0] = 1;  // The base case
    for (int i = 0; i < A.length; i++)
        for (int n = K; n >= 1; n--)
            for (int s = A[i]; s <= S; s++)
                count[n][s] += count[n-1][s - A[i]];

    return count[K][S];
}

Ответ 4

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

1) Сортировка массива A O (N log N)

2) Создайте новый массив B, где все значения различны. Также сохраните счетчик значения значения в исходном массиве A для каждого элемента в B. O (N)

3) Создайте новый массив C с суммами из двух элементов B. Включая суммы одного и того же элемента, если count > 1. Также сохраните оба индекса элементов из B. O (| В | ²)

4) Сортируйте массив C суммами O (| B | ² (log | B | ²))

5) Для каждого элемента из B найдите два действительных элемента из C, чтобы три значения суммировались до S и индексы находятся в одном порядке. В псевдокоде:

num=0
for (i=0; i<n; i++)
  j=i
  k=|C|-1
  while (j <= k)
    if (c[j].sum + c[k].sum = S - b[i].value)
      for (m=0; m<c[j].index.length; m++)
        for (n=0; n<c[k].index.length; n++)
          if (i < c[j].index[m].left < c[j].index[m].right < c[j].index[k].left < c[j].index[k].right)
            num+=b[i].count * b[c[j].index[m].left].count * b[c[j].index[m].right].count * b[c[j].index[k].left].count * b[c[j].index[k].right].count
          else if (b[i].count > 1 && i = c[j].index[m].left < c[j].index[m].right < c[j].index[k].left < c[j].index[k].right)
            num+= binomialcoefficient(b[i].count, 2) * b[c[j].index[m].right].count * b[c[j].index[k].left].count * b[c[j].index[k].right].count
          else if (b[c[j].index[m].left].count > 1 && i < c[j].index[m].left = c[j].index[m].right < c[j].index[k].left < c[j].index[k].right)
            num+= b[i].count * binomialcoefficient(b[c[j].index[m].left].count, 2) * b[c[j].index[k].left].count * b[c[j].index[k].right].count
          [..]
          else if (b[i].count > 2 && i = c[j].index[m].left = c[j].index[m].right < c[j].index[k].left < c[j].index[k].right)
            num+= binomialcoefficient(b[i].count, 3) * b[c[j].index[k].left].count * b[c[j].index[k].right].count
          [..]
          else if (b[i].count > 1 && b[c[j].index[m].right].count > 1 && i = c[j].index[m].left < c[j].index[m].right = c[j].index[k].left < c[j].index[k].right)
            num+= binomialcoefficient(b[i].count, 2) * binomialcoefficient(b[c[j].index[m].right].count, 2) * b[c[j].index[k].right].count
          [..]
          else if (b[i].count > 4 && i = c[j].index[m].left = c[j].index[m].right = c[j].index[k].left = c[j].index[k].right)
            num+= binomialcoefficient(b[i].count, 5)
    if (c[j].sum + c[k].sum >= S - b[i].value)
      k--
    if (c[j].sum + c[k].sum <= S - b[i].value)
      j++

Я не уверен, какой временной сложностью это имеет. Внешний цикл for связан O (| B |), цикл while - O (| B | ²), внутренний для циклов O (| B |), поскольку B имеет только отдельные значения. Таким образом, это очевидно в O (| B | ⁵). Но его O (N), если все элементы в A имеют одинаковое значение, и если все значения различны и достаточно случайны, возможно, возможно связать количество индексов на сумму в C от константы, что приведет к O (N ³).

Наихудший случай может быть где-то с половиной значений, равными, а другая половина случайной или со всеми числами, отличными, но с множеством дублированных сумм. Но это также приведет к значительно более короткому циклу. Я чувствую, что while и две внутренние для петель связаны O (N ²), поэтому O (N ³) в общем случае для всех случаев, но я не может это доказать.

Также интересным вопросом является то, каково максимальное количество возможностей для получения 5 чисел, которые суммируются с S для массива из N разрозненных чисел. Если он находится в O (N ⁵), то худшим случаем этого алгоритма также является O (N ⁵).

Возможно, попробуй это;).