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

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

Просто посчитайте от 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 2

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

Поиск в Google по «алгоритму набора мощности» привел меня к этому рекурсивному решению .

Алгоритм Ruby

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, в)}

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

Каким будет состояние остановки?

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 , б, в)}

вынуть любой элемент

powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a , б, в)} is

powerset (S - {c}) = {(), (a), (b), (a, b)} объединены с

{c} U powerset (S - {c}) = {(c), (a, c), (b, c), (a, b, c)}

powerset (S) = powerset (S - {e _i }) U ({e _i } U powerset (S - {e _i }))

, где e _i - элемент S (синглтон)

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

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

Answer 3

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

Answer 4

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

Answer 5

Рекурсивные и итерационные решения для расчета мощности, заданной в схеме. Хотя не полностью протестировано

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

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

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

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

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

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

Answer 7

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