Lo algoritmo puede calcular el conjunto potencia de un conjunto dado?

Question

Me gustaría generar eficientemente una lista única de combinaciones de números basados ??en una lista a partir de los números.

list = [1,2,3,4,5] ejemplo comienzo, pero el algoritmo debe trabajar 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 ellos, por ejemplo, en el ejemplo anterior que realmente no necesita la combinación [1,3,2] porque ya presente como [1,2,3]

Answer 1

Hay un nombre para lo que está pidiendo. Se llama el conjunto potencia .

Google para "algoritmo de ajuste de potencia" me llevó a este recursiva solución .

Rubí Algoritmo

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

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

conjunto potencia intuición

Si S = (a, b, c) a continuación, el powerset (S) es el conjunto de todos los subconjuntos powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b , c)}

El primer "truco" es tratar de Definir de forma recursiva.

¿Cuál sería un estado de parada?

S = () tiene lo que powerset (S)?

Como get a ella?

Reducir fijado por un elemento

considerar la adopción de un elemento hacia fuera - en el ejemplo anterior, sacar {c}

S = (a, b) a continuación, powerset (S) = {(), (a), (b), (a, b)}

Lo que falta?

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

hmmm

Aviso alguna similitud? Mira de nuevo ...

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

llevar a cabo cualquier elemento

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

powerset (S - {c}) = {(), (a), (b), (a, b)} unioned 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. es el conjunto vacío pasó? Hecho (Tenga en cuenta que el poder conjunto de {} {{es}})
2. Si no es así, tome un elemento cabo
   • método de llamada de forma recursiva en el resto del conjunto
   • devolver el conjunto formado por la Unión de
     1. el powerset del conjunto sin el elemento (de la llamada recursiva)
     2. este mismo conjunto (es decir, 2.1 ), pero con cada elemento en él unioned con el elemento inicialmente sacada

Answer 2

Simplemente cuente 0 a 2^n - 1 e imprimir los números de acuerdo a la representación binaria de su recuento. un medio 1 imprime ese número y un medio 0 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 3

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

Answer 4

Lo mismo que la respuesta de hobodave, pero iterativo y más rápido (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 5

A partir de un comentario de OP (copia editada):

El ejemplo se simplifica forma de lo que en realidad estoy haciendo. Los números son objetos que tienen una propiedad "Cantidad", quiero sumar las cantidades para cada combinación posible después eligió la combinación que utiliza la mayoría de los objetos en donde la suma de la N cantidades se encuentra dentro de algunos otros límites, por ejemplo, x < N < y.

Lo que tenemos es un problema de optimización. Lo que usted ha asumido que es la manera correcta de abordar este problema de optimización consiste en descomponerlo en un problema de enumeración (que es lo que le pide) y luego un problema de filtración (que presumiblemente se sabe cómo hacerlo).

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

Por lo tanto, encontrar la manera de plantear el problema de optimización como tal, escribir una nueva pregunta y editar éste a punto a la misma.

Answer 6

recursiva y soluciones iterativos para calcular potencia programada en el esquema. No se ha probado completamente aunque

(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

Más Allá es una solución recursiva, que es similar a los que habían puesto. Unas afirmaciones están proporcionando como tipo de pruebas unitarias. No me las arreglé para usar "set" tipo de Python para la representación de conjunto de conjuntos. Python, dijo que "los objetos del juego son unhashable" cuando se trata de la expresión 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)