Найти все триплеты в массиве с суммой, меньшей или равной заданной сумме

Ответ 1

С точки зрения асимптотики в худшем случае лучшего алгоритма не существует, поскольку размер вывода потенциально равен O (n ³).

например Пусть массив будет числами от 1 до n. Пусть S = 3n. Очевидно, что любое подмножество из трех элементов массива будет меньше, чем S, и есть подмножества (n choose 3) = O(n³).

Есть несколько способов ускорить не худшие случаи. Например, попробуйте сначала отсортировать массив. Это должно дать вам несколько советов.

Ответ 2

У меня есть идея, но я не уверен, что она работает.

Preprocess (удалить элементы > S) и сначала отсортировать массив.

Затем после того, как вы подберете arr[i] и arr[j], где i < j, вы можете выполнить двоичный поиск S - arr[i] - arr[j] в оставшемся array[j+1...n]. После того, как вы выполнили двоичный поиск индекса m, k может находиться между j+1 и m.

Я думаю, что это может уменьшить сложность. Как вы думаете?

Ответ 3

Какова была бы сложность этого?

Если применяется к отсортированному списку (по возрастанию), f просто перечисляет триплеты, сумма которых меньше или равна s, один за другим, без создания дубликатов или сканирования мимо первого слишком большого элемента.

Код Haskell:

f []     s result = if length result == 3 then [result] else []
f (x:xs) s result
  | length result == 3   = [result]
  | x + sum result > s   = []
  | otherwise            = f xs s (x:result) ++ f xs s result

Вывод:

*Main> length $ f [1..300] 300 []
731375
(5.09 secs, 402637784 bytes)

*Main> f [1..10] 13 []
[[3,2,1],[4,2,1],[5,2,1],[6,2,1],[7,2,1],[8,2,1],[9,2,1],[10,2,1],[4,3,1]
,[5,3,1],[6,3,1],[7,3,1],[8,3,1],[9,3,1],[5,4,1],[6,4,1],[7,4,1],[8,4,1]
,[6,5,1],[7,5,1],[4,3,2],[5,3,2],[6,3,2],[7,3,2],[8,3,2],[5,4,2],[6,4,2]
,[7,4,2],[6,5,2],[5,4,3],[6,4,3]]

Ответ 4

Это может быть решено в сложности O (n ²).

Сначала отсортируйте числа → O (nlog (n))

Теперь, начиная с фронта, зафиксируйте по одному номеру за раз. Теперь проблема сводится к тому, чтобы найти 2 числа в отсортированном массиве, сумма которого & lt; = заданная сумма. Используя 2 указателя, один с начала и один с конца, это можно решить за O (n). Таким образом, общая сложность равна O (n ²)

Ответ 5

Я оставляю свой первоначальный ответ ниже, но на самом деле это можно решить с помощью O (n). Мое новое решение использует очередь для отслеживания триплетов. Он только возвращает количество триплетов, но вы можете создать список, чтобы довольно легко отслеживать списки триплетов, если это то, что требуется.

    class Queue (object):
      def __init__ (self):
        self.queue = []
        self.itemCount = 0

      def enqueue (self, item):
        self.queue.append (item)
        self.itemCount += 1

      def dequeue (self):
        self.itemCount += 1
        return (self.queue.pop(0))


    def findAllTriplets(li,S):
      if len(li) < 3:
        return "Not enough elements for triplets"
      tQ = Queue() # Queue to keep track of data
      tripletNum = 0 # Integer to track number of triplets to be returned
      tripletSum = 0 # Value of sum of consecutive list items for tripletNum evaluation
      for number in li:
        # Add the number to the queue immediately and add it to the current triplet sum
        tQ.enqueue(number)
        tripletSum += number
        # For the first 3 numbers only enqueue and add to the sum
        if tQ.itemCount < 3:
          continue
        # Afterwards, check if the sum of the latest three is less than S
        else:
          if(tripletSum <= S):
            tripletNum += 1
          # Dequeue the oldest element in the queue and subtract it from the tracked triplet sum
          tripletSum -= tQ.dequeue()
      return tripletNum

Я полагаю, что этот алгоритм должен добиться цели в O (N ²). Вы должны отсортировать массив заранее, хотя.

По сути, я просто нахожу все возможные триплеты, где первый индекс i равен нулю, а следующий индекс равен j, просматривая оставшиеся индексы (k) для всех сумм, меньших или равных x (или S в вашем случае). После этого я увеличиваю j на 1 и повторяю процесс. Как только j подходит к концу массива, я начинаю процесс заново с моего i, равным i + 1, и продолжаю, пока я не равняюсь значению индекса от второго до последнего (поскольку в этот момент не осталось возможных триплетов).

Код Python

def numTriplets(a,x):
   if len(a) < 3:
       return None
   i = 0
   j = 1
   triplets = []
   while True:
      for k in range(j+1,len(a)):
         if a[i] + a[j] + a[k] <= x:
            triplets.append([i,j,k])
      j += 1
      if j == len(a) - 1:
         i += 1
         j = i + 1
      if i == len(a) - 2:
         return triplets