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

Ответ 1

Есть имя для того, что вы просите. Он назывался power set.

Googling для "алгоритма установки мощности" привел меня к этому рекурсивному решению.

Алгоритм Ruby

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 =() имеет какую силу (S)?

Как получить к нему?

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

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

S = (a, b), то poweret (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 poweret (S - {c}) = {(c), (a, c), (b, c), (a, b, c)}

poweret (S) = poweret (S - {e _i}) U ({e _i} U-набор (S - {e _{iсуб > }))}

где e _i - элемент из S (singleton)

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

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

Ответ 2

Просто посчитайте 0 до 2^n - 1 и напечатайте цифры в соответствии с двоичным представлением вашего счета. a 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}

Ответ 3

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

Ответ 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

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

Ответ 5

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

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

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

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

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

Ответ 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)))))

Ответ 7

В дальнейшем это рекурсивное решение, похожее на уже опубликованные. Несколько утверждений предоставляют как единичные тесты. Мне не удалось использовать "set" тип 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)