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

Question

Учитывая массив 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 элементов в хэш-таблицу и затем продолжить с 2 вложенными циклами.Однако сложность остается той же, и мы просто используем больше памяти.

Если предположить, что входные данные будут довольно случайными (поэтому нет хеширования в худшем случае), существует ли алгоритм, который может решить эту проблему в 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), вы увидите, что он работает относительно быстро.Тем не менее, нетрудно найти входы, для которых это занимает много времени.Даже если мы не сможем запустить его достаточно быстро для всех равных чисел, какие оптимизации мы можем сделать?

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

Answer 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 не обязательно различаются.По сути, вы можете использовать решение Морона следующим образом:

• Создать отсортированный массив сумм {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 подсчитайте, сколько в массиве пар элементов, которые суммируются с Se.Как и в решении Морон, у вас есть два указателя, один направо, а другой налево.Если сумма слишком мала, переместите первый указатель, увеличив сумму;если сумма слишком велика, переместите второй указатель, уменьшив ее.

  Предположим, что сумма верна.Это означает, что один указывает на (a, x), а второй на (b, y), где a + b = Se.Увеличьте счетчик на 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] + х [J] + х [к] + х [л] + х [м] = 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 ₁₂ |- в пять раз с i = j
• X ₂ = |A ₁₂ ∩ A ₂₃ |- в пять раз с i = j = k
• X ₃ = | A ₁₂ ∩ A ₂₃ ∩ A ₃₄ |- в пять раз с i = j = k = l
• X ₄ = | A ₁₂ ∩ A ₂₃ ∩ A ₃₄ ∩ A ₄₅ |- в пять раз с i = j = k = l = m
• X ₅ = | A ₁₂ ∩ A ₃₄ |- пятерок с i = j, k = l
• X ₆ = | A ₁₂ ∩ A ₂₃ ∩ A ₄₅ |- пятерок с i = 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 ₆ .

Проверка:

Сколько существует пятерок в [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 ( _n log _n ): Вычислить (x ^{a ₁} + ... + x ^{a _n} ) ⁵ с использованием БПФ, результатом является коэффициент при x ^S .Это позволяет использовать _i дважды, но вы можете вычесть многочлены, такие как (x ^{2a ₁} + ... + x ^{2a _n} ) ⁵ * (x ^{a ₁} + ... + x ^{a _n} ) ³ и т. Д. В соответствии с принципом включения-исключения.

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

Answer 2

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

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

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

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

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

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

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

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

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

Answer 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];
}

Answer 4

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

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

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

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

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 | ² ), внутренний цикл for - с O (| B |), поскольку B имеет только отличные значения. Так что, очевидно, это в O (| B | ⁵ ). Но его O (N), если все элементы в A имеют одинаковое значение и если все значения различны и достаточно случайны, возможно, можно связать число индексов на сумму в C константой, что привело бы к O (N * 1 038 * 3 * +1039 *).

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

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

Может, попробуем;).