Алгоритм формирования K подмножеств элементов в порядке их суммы

Если у меня есть несортированный большой набор n целых чисел (скажем, 2^20 из них) и я хотел бы генерировать подмножества с элементами k Каждый (где k мал, скажем 5) в порядке возрастания их сумм, каков наиболее эффективный способ сделать это?

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

Кроме того, какова будет сложность алгоритма?

Здесь есть аналогичный вопрос: алгоритм для получения каждого возможного подмножества списка, в порядке их произведения, без построения и сортировки всего списка (т. е. генераторов) о генерации подмножеств в порядке их произведения, но это не соответствовало бы моим потребностям из-за чрезвычайно большого размера множества n

Я намерен реализовать алгоритм в Mathematica, но мог бы сделать это в C++ или И питон тоже.

5 3
sorting algorithm dynamic-programming

5 ответов:

Если желаемое свойство малых подмножеств (назовем его P) достаточно распространено, то вероятностный подход может хорошо работать:

  1. сортируйте целые числа n (для миллионов целых чисел, то есть от 10 до 100 МБ оперативной памяти, это не должно быть проблемой) и суммируйте наименьшие числа k-1. Назовем это итогом offset.
  2. сгенерируйте случайное k-подмножество (скажем, путем выборки k случайных чисел, mod n) и проверьте его на P-ness.
  3. на совпадении обратите внимание на общую сумму подмножества. Вычтите offset из этого, чтобы найти верхнюю границу на самом большом элементе любого k-подмножества эквивалентной суммы.
  4. ограничьте набор n целых чисел теми, которые меньше или равны этой границе.
  5. повторяйте (goto 2) до тех пор, пока совпадения не будут найдены в пределах некоторого фиксированного числа итераций.

Обратите внимание на первоначальной сортировки O(n log n). Бинарный поиск, подразумеваемый в шаге 4, является O(log n).

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

1

Даже если только 1 из 1000 наборов k-размера соответствует вашему условию, это все равно слишком много комбинаций для проверки. Я считаю, что время выполнения масштабируется с помощью nCk (n выберите k), где n-размер вашего несортированного списка. Ответ Эндрю Мао имеет связь с этим значением. 10^28/1000 еще 10^25. Даже при 1000 тестах в секунду это все равно 10^22 секунды. =10^14 лет.

Если вам это разрешено, я думаю, что вам нужно исключить повторяющиеся числа из вашего большого набора. Каждый дубликат, который вы удалите, будет резко сократите количество оценок, которые вам нужно выполнить. Отсортируйте список, а затем убейте дураков.

Кроме того, вы ищете единственный лучший ответ здесь? Кто будет проверять ответ, и сколько времени это займет? Я предлагаю реализовать генетический алгоритм и запустить кучу экземпляров в одночасье (пока у вас есть время). Это даст очень хороший ответ, за гораздо меньшее время, чем продолжительность Вселенной.

1

Вы имеете в виду 20 целых чисел или 2^20? Если это действительно 2^20, то вам, возможно, потребуется пройти через значительное количество (2^20 выберите 5) подмножеств, прежде чем вы найдете то, что удовлетворяет вашему условию. На современном процессоре 100k MIPS, предполагая, что только 1 команда может вычислить набор и оценить это условие, прохождение всего этого набора все равно займет 3 квадриллиона лет. Так что если вам даже нужно пройти через часть этого, это не закончится в вашей жизни.

Даже если число целых чисел меньше,это, кажется, довольно грубый способ решить эту проблему. Я предполагаю, что вы можете выразить свое условие в виде ограничения в смешанной целочисленной программе, и в этом случае решение следующего может быть гораздо более быстрым способом получить решение, чем перебор перебора. Предполагая, что ваши целые числа w_i, i от 1 до N: 

min sum(i) w_i*x_i
    x_i binary
    sum over x_i = k
subject to (some constraints on w_i*x_i)

Если окажется, что линейное программирование релаксации вашего МИП является жестким, то вы было бы в удаче и иметь очень эффективный способ решить проблему, даже для 2^20 целых чисел (пример: max-flow/min-cut problem.) Кроме того, вы можете использовать подход генерации столбцов, чтобы найти решение, так как у вас может быть очень большое количество значений, которые не могут быть решены одновременно.

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

1

Вот приблизительный способ, чтобы делать то, что ты говоришь.

Сначала отсортируйте список. Затем рассмотрим некоторый индексный вектор длины 5 v, соответствующий позициям в отсортированном списке, где максимальным индексом является некоторое число m, и некоторый другой индексный вектор v', имеющий некоторый максимальный индекс m' > m. Наименьшая сумма для всех таких векторов v' всегда больше наименьшей суммы для всех векторов v.

Итак, вот как вы можете выполнить цикл через элементы с приблизительно увеличивающаяся сумма: 

sort arr

for i = 1 to N
   for v = 5-element subsets of (1, ..., i)
     set = arr{v}
     if condition(set) is satisfied
       break_loop = true
       compute sum(set), keep set if it is the best so far
   break if break_loop
В принципе, это означает, что вам больше не нужно проверять 5-элементные комбинации (1, ..., n+1), Если вы найдете удовлетворяющее назначение в (1, ..., n), так как любое удовлетворяющее назначение с максимальным индексом n+1 будет иметь большую сумму, и вы можете остановиться после этого набора. Однако нет простого способа перебирать 5-комбинации (1, ..., n), гарантируя, что сумма всегда увеличивается, но, по крайней мере, вы можете прекратить проверку после того, как найдете удовлетворяющее множество в некотором n.
0

Это выглядит как идеальный кандидат для map-reduce (http://en.wikipedia.org/wiki/MapReduce ). Если вы знаете какой-либо способ разбиения их так, чтобы проходящие кандидаты одинаково присутствовали в каждом узле, то вы, вероятно, можете получить большую пропускную способность.

Полная сортировка на самом деле может не понадобиться, так как этап карты может позаботиться об этом. Каждый узел может затем проверить условие относительно k-кортежей и вывести результаты в файл, который может быть агрегирован / уменьшен позже.

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

0