Какой алгоритм может рассчитать набор мощности данного набора?
Я хотел бы эффективно генерировать уникальный список комбинаций чисел на основе начального списка чисел.
пример начала list = [1,2,3,4,5] но алгоритм должен работать для [1,2,3...n]
result =
[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]
Заметка. Я не хочу повторяющихся комбинаций, хотя я мог бы жить с ними, например, в приведенном выше примере мне не нужна комбинация [1,3,2], потому что она уже представлена как [1,2,3]
7 ответов
Есть имя для того, что вы спрашиваете. Это называется набором мощности.
Поиск в "алгоритме набора мощности" привел меня к этому рекурсивному решению.
Рубиновый алгоритм
def powerset!(set)
return [set] if set.empty?
p = set.pop
subset = powerset!(set)
subset | subset.map { |x| x | [p] }
end
Power Set Intuition
Если S = (a, b, c), тогда powerset(S) - это набор всех подмножествpowerset(S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}
Первый "трюк" - попытаться определить рекурсивно.
Что бы остановить состояние?
S = () имеет какой powerset(S)?
Как добраться до этого?
Уменьшить набор на один элемент
Рассмотрите возможность удаления элемента - в приведенном выше примере выведите {c}
S = (a, b), затем powerset(S) = {(), (a), (b), (a, b)}
Чего не хватает?
powerset(S) = {(c), (a, c), (b, c), (a, b, c)}
хммм
Заметили сходство? Посмотри снова...
powerset(S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}
вынуть любой элемент
powerset(S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)} является
powerset(S - {c}) = {(), (a), (b), (a, b)}, объединенный с
{c} U powerset(S - {c}) = {(c), (a, c), (b, c), (a, b, c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
где ei является элементом S (синглтон)
Псевдо-алгоритм
- Набор передан пустым? Готово (обратите внимание, что набор мощности {} равен {{}})
- Если нет, выньте элемент
- рекурсивно вызывать метод на оставшейся части множества
- вернуть набор, состоящий из Союза
- powerset набора без элемента (от рекурсивного вызова)
- это то же самое множество (то есть, 2.1), но с каждым элементом в нем, объединенным с элементом, первоначально удаленным
Просто посчитай 0 в 2^n - 1 и распечатайте числа в соответствии с двоичным представлением вашего счета. 1 означает, что вы печатаете это число и 0 значит ты не Пример:
set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
00011 => print {1, 2}
00100 => print {3}
00101 => print {1, 3}
00110 => print {2, 3}
00111 => print {1, 2, 3}
...
11111 => print {1, 2, 3, 4, 5}
def power(a)
(0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end
Из комментария OP (копия отредактирована):
Пример - это упрощенная форма того, что я на самом деле делаю. Числа являются объектами, которые имеют свойство "Кол-во", я хочу суммировать количества для каждой возможной комбинации, затем выбрать комбинацию, которая использует большинство объектов, где сумма сумм
Nнаходится в некоторых других границах, напримерx < N < y,
У вас есть проблема оптимизации. Вы предположили, что правильный способ решения этой проблемы оптимизации состоит в том, чтобы разложить ее на проблему перечисления (о чем вы просили), а затем на проблему фильтрации (которую, вероятно, вы знаете, как это сделать).
Чего вы еще не понимаете, так это того, что решение такого типа работает либо (а) для теоретического анализа, либо (б) для очень малых значений n, Перечисление, которое вы запрашиваете, является экспоненциальным в nЭто означает, что вы получите что-то такое, что на практике займет слишком много времени.
Поэтому выясните, как поставить проблему оптимизации как таковую, напишите новый вопрос и отредактируйте его, чтобы указать на него.
Мой коллега придумал элегантный способ сделать это в рубине. Он использует концепцию IVlad для набора индексов.
class Array
def select_by_index(&block)
# selects array element by index property
n = []
each_with_index do |e, i|
if block.call(i)
n << e
end
end
n
end
end
def pow(a)
# power set of a
max = (1 << a.length)
(0...max).map { |i| a.select_by_index { |k| (1 << k) & i != 0 }}
end
Рекурсивные и итерационные решения для расчета мощности, заданной в схеме. Хотя не полностью протестировано
(define (power_set set)
(cond
((empty? set) (list '()))
(else
(let ((part_res (power_set (cdr set))))
(append (map (lambda (s) (cons (car set) s)) part_res) part_res)))))
(define (power_set_iter set)
(let loop ((res '(())) (s set))
(if (empty? s)
res
(loop (append (map (lambda (i) (cons (car s) i)) res) res) (cdr s)))))
Здесь и далее рекурсивное решение, аналогичное уже опубликованным. Несколько утверждений приводятся как вид модульных тестов. Мне не удалось использовать "набор" типа Python для представления набора множеств. Python говорит, что "set-объекты не подлежат уничтожению" при попытке выражения типа "s.add(set())".
См. Также решения на многих языках программирования по адресу http://rosettacode.org/wiki/Power_set
def generatePowerSet(s, niceSorting = True):
"""Generate power set of a given set.
The given set, as well as, return set of sets, are implemented
as lists.
"niceSorting" optionnaly sorts the powerset by increasing subset size.
"""
import copy
def setCmp(a,b):
"""Compare two sets (implemented as lists) for nice sorting"""
if len(a) < len(b):
return -1
elif len(a) > len(b):
return 1
else:
if len(a) == 0:
return 0
else:
if a < b:
return -1
elif a > b:
return 1
else:
return 0
# Initialize the power set "ps" of set "s" as an empty set
ps = list()
if len(s) == 0:
ps.append(list())
else:
# Generate "psx": the power set of "sx",
# which is "s" without a chosen element "x"
sx = copy.copy(s)
x = sx.pop()
psx = generatePowerSet(sx, False)
# Include "psx" to "ps"
ps.extend(psx)
# Include to "ps" any set, which contains "x"
# Such included sets are obtained by adding "x" to any subset of "sx"
for y in psx:
yx = copy.copy(y)
yx.append(x)
ps.append(yx)
if niceSorting:
ps.sort(cmp=setCmp)
return ps
assert generatePowerSet([]) == [[]]
assert generatePowerSet(['a']) == [[], ['a']]
assert generatePowerSet(['a', 'b']) == [[], ['a'], ['b'], ['a', 'b']]
assert generatePowerSet(['a', 'b','c']) == [[],
['a'], ['b'], ['c'],
['a', 'b'], ['a', 'c'], ['b', 'c'],
['a', 'b', 'c'] ]
assert generatePowerSet(['a', 'b','c'], False) == [ [],
['a'],
['b'],
['a', 'b'],
['c'],
['a', 'c'],
['b', 'c'],
['a', 'b', 'c'] ]
print generatePowerSet(range(4), True)
То же, что и ответ hobodave, но итеративно и быстрее (в Ruby). Это также работает с обоими Array а также Set,
def Powerset(set)
ret = set.class[set.class[]]
set.each do |s|
deepcopy = ret.map { |x| set.class.new(x) }
deepcopy.map { |r| r << s }
ret = ret + deepcopy
end
return ret
end
В моих тестах метод IVlad не работал так хорошо в Ruby.