algorithm - teoria - subconjunto

¿Qué algoritmo puede calcular el conjunto de potencias de un conjunto dado?

Question

Me gustaría generar de manera eficiente una lista única de combinaciones de números basada en una lista inicial de números.

ejemplo de list = [1,2,3,4,5] inicio list = [1,2,3,4,5] pero el algoritmo debería funcionar para [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]

Nota. No quiero combinaciones duplicadas, aunque podría vivir con ellas, por ejemplo, en el ejemplo anterior realmente no necesito la combinación [1,3,2] porque ya está presente como [1,2,3]

Answer 1

De un comentario de OP (copia editada):

El ejemplo es una forma simplificada de lo que realmente estoy haciendo. Los números son objetos que tienen una propiedad "Cantidad", quiero sumar las cantidades para cada combinación posible y luego elegir la combinación que utiliza la mayoría de los objetos donde la suma de las cantidades N está dentro de algunos otros límites, por ejemplo , x < N < y .

Lo que tienes es un problema de optimización. Lo que ha asumido es que la forma correcta de abordar este problema de optimización es descomponerlo en un problema de enumeración (que es lo que pidió) y luego un problema de filtración (que probablemente sepa cómo hacerlo).

Lo que aún no se da cuenta es que este tipo de solución solo funciona (a) para el análisis teórico, o (b) para valores muy pequeños de n . La enumeración que estás solicitando es exponencial en n , lo que significa que terminarás con algo que llevaría demasiado tiempo en la práctica.

Por lo tanto, descubra cómo plantear su problema de optimización como tal, escriba una nueva pregunta y edite este para señalarlo.

Answer 2

Hay un nombre para lo que estás preguntando. Se llama el conjunto de poder .

Buscar en Google para "algoritmo de conjunto de potencia" me llevó a esta solución recursiva .

Algoritmo de rubí

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

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

Intuición del conjunto de poder

Si S = (a, b, c) entonces el conjunto de potencias (S) es el conjunto de todos los subconjuntos de conjunto de potencias (S) = {(), (a), (b), (c), (a, b), ( a, c), (b, c), (a, b, c)}

El primer "truco" es tratar de definir recursivamente.

¿Qué sería un estado de parada?

S = () tiene que powerset (S)?

¿Cómo llegar a ella?

Reducir conjunto por un elemento

Considere sacar un elemento - en el ejemplo anterior, saque {c}

S = (a, b) luego powerset (S) = {(), (a), (b), (a, b)}

¿Lo que falta?

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

hmmm

¿Se nota alguna similitud? Mirar de nuevo...

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

sacar cualquier elemento

powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b, c)} es

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

{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 }))

donde e _i es un elemento de S (un singleton)

Pseudo algoritmo

1. ¿Se pasó el set vacío? Hecho (Tenga en cuenta que el conjunto de potencias de {} es {{}})
2. Si no, saca un elemento
   • Recursivamente llamar al método en el resto del conjunto
   • Devolver el conjunto compuesto por la unión de
     1. el conjunto de potencias del conjunto sin el elemento (de la llamada recursiva)
     2. este mismo conjunto (es decir, 2.1 ) pero con cada elemento en él unido junto con el elemento inicialmente eliminado

Answer 3

Igual que la respuesta de hobodave, pero iterativa y más rápida (en Ruby). También funciona con Array y 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

En mis pruebas, el método de IVlad no funciona tan bien en Ruby.

Answer 4

Solo cuente de 0 a 2^n - 1 e imprima los números de acuerdo con la representación binaria de su cuenta. un 1 significa que imprime ese número y un 0 significa que no lo hace. Ejemplo:

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 5

Soluciones recursivas e iterativas para calcular el conjunto de potencia en el esquema. Aunque no completamente probado

(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

En lo sucesivo es una solución recursiva, que es similar a las ya publicadas. Algunas afirmaciones están proporcionando como tipo de pruebas unitarias. No logré usar el tipo "conjunto" de Python para representar conjuntos de conjuntos. Python dijo que "los objetos establecidos son inestables" al intentar expresiones como "s.add (set ())".

Vea también soluciones en muchos lenguajes de programación en 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 7

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