Какой алгоритм может рассчитать набор питания данного набора?

Question

Я хотел бы эффективно генерировать уникальный список комбинаций чисел на основе исходного списка чисел.

Пример запуска 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

Answer 1

Есть имя для того, что вы спрашиваете. Это называется Комплект питания.

Googling для «алгоритма электропитания» привел меня к этому Рекурсивное решение.

Алгоритм Рубина

def powerset!(set)
   return [set] if set.empty?

   p = set.pop
   subset = powerset!(set)  
   subset | subset.map { |x| x | [p] }
end

Установка мощности интуиция

Если s = (a, b, c) то пауза(Ы) это набор всех подмножествпауза(S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}

Первый «трюк» - попытаться определять рекурсивно.

Что было бы состояние остановки?

S = () имеет то, что пауза(Ы)?

Как получать к этому?

Уменьшить набор одним элементом

Рассмотрим принять элемент - в приведенном выше примере выньте {C}

S = (a, b) тогда пауза(S) = {(), (a), (b), (a, b)}

Чего не хватает?

пауза(S) = {(c), (a, c), (b, c), (a, b, c)}

Хм

Обратите внимание на любые сходства? Посмотри снова...

пауза(S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)}

взять любой элемент

пауза(S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)} является

пауза(S - {C}) = {(), (a), (b), (a, b)} объединить с

{C} U пауза(S - {C}) = {(c), (a, c), (b, c), (a, b, c)}

пауза(Ы) = пауза(S - {е_я}) U ({e_я} U. пауза(S - {е_я}))

где Э._я это элемент S (синглтон)

Псевдоалгоритм

1. Прошло ли набор пустой? Сделано (обратите внимание, что набор питания {} {{}})
2. Если нет, возьми элемент
   • рекурсивно называют метод на оставшуюся часть набора
   • вернуть набор, состоящий из союза
     1. PowerSet набора без элемента (от рекурсивного вызова)
     2. этот же набор (т.е. 2.1) но с каждым элементом в нем объединенный с элементом изначально вывезен

Answer 2

Просто считаю 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}

Answer 3

def power(a)
 (0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end

Answer 4

То же самое, что и ответ 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

В моем тестах метод Ивлада не работает так хорошо в Ruby.

Answer 5

С комментариев от OP (копирование отредактировано):

Пример упрощена форма того, что я на самом деле делаю. Числа - это объекты, которые имеют свойство «qty», я хочу суммировать величины для каждой возможной комбинации, затем выбрали комбинацию, использующую большинство объектов, где сумма величин. N находится в пределах некоторых других границ, например x < N < y.

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

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

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

Answer 6

Рекурсивные и итеративные решения для расчета электропитания на схеме. Не полностью проверен, хотя

(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)))))

Answer 7

Далее - рекурсивное решение, которое похоже на уже опубликованные. Несколько утверждений обеспечивают как вид единиц. Мне не удалось использовать «Установить» тип Python для представления набора наборов. Python сказал, что «установленные объекты неходятся» при попытке выражения, такими как «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)