Che algoritmo in grado di calcolare l'insieme potenza di un dato insieme?

Question

Vorrei generare efficientemente un elenco unico di combinazioni di numeri sulla base di un elenco iniziale di numeri.

esempio inizio list = [1,2,3,4,5] ma l'algoritmo dovrebbe funzionare per [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. Non voglio combinazioni duplicati, anche se ho potuto vivere con loro, ad esempio, nell'esempio di cui sopra non ho davvero bisogno la combinazione [1,3,2] perché già presente come [1,2,3]

Answer 1

C'è un nome per quello che stai chiedendo. Si chiama set motorizzazione .

Googling per "algoritmo insieme potenza" mi ha portato a questo ricorsiva soluzione .

Rubino Algoritmo

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

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

Power Set intuizione

Se S = (a, b, c), allora il powerset (S) è l'insieme di tutti i sottoinsiemi powerset (S) = {(), (a), (b), (c), (a, b), (a, c), (b, c), (a, b , c)}

Il primo "trucco" è quello di cercare di Definisci in modo ricorsivo.

Che cosa sarebbe uno stato di arresto?

S = () ha quello powerset (S)?

Come ad esso?

Ridurre impostato un elemento

Prendere in considerazione un elemento fuori - nell'esempio di cui sopra, estrarre {C}

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

Che cosa manca?

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

hmmm

Notate qualche similarità? Guarda ancora ...

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

prendere qualsiasi elemento fuori

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

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

dove e _i è un elemento di S (singleton)

Pseudo-algoritmo

1. è l'insieme vuoto passato? Fatto (Si noti che insieme potenza di {} è {{}})
2. Altrimenti, un elemento fuori
   • metodo chiamata ricorsivamente sul resto del set
   • restituire il set composto dell'Unione di
     1. la Powerset del set senza l'elemento (dalla chiamata ricorsiva)
     2. questo stesso set (cioè, 2.1 ), ma con ogni elemento al suo unioned con l'elemento inizialmente prelevata

Answer 2

Basta contare 0 a 2^n - 1 e stampare i numeri secondo la rappresentazione binaria di un passo. un mezzo 1 si stampa quel numero e un mezzo 0 non lo fai. Esempio:

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

Come per la risposta di hobodave, ma iterativo e più veloce (in Ruby). Funziona anche con entrambi Array e 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

Nel mio test, il metodo di IVlad non funziona così bene in Ruby.

Answer 5

Da un commento di OP (copia modificata):

  

L'esempio è semplificato forma di quello che sto facendo. I numeri sono oggetti che hanno una proprietà "Quantità", voglio sommare le quantità per ogni possibile combinazione poi ha scelto la combinazione che utilizza il maggior numero di oggetti in cui la somma delle quantità N è all'interno di alcuni altri confini, es x < N < y.

Quello che hai è un problema di ottimizzazione. Quello che avete assunto è che il modo giusto per affrontare questo problema di ottimizzazione è quello di scomporre in un problema di enumerazione (che è quello che ha chiesto) e poi un problema di filtrazione (che presumibilmente si sa come fare).

Quello che non hanno ancora capire è che questo tipo di soluzione funziona solo (a) per l'analisi teorica, o (b) per valori molto piccoli di n. L'enumerazione che stai chiedendo è esponenziale in n, il che significa che ci si finisce con qualcosa che avrebbe preso troppo tempo per l'esecuzione in pratica.

Quindi, capire come porre il problema di ottimizzazione in quanto tale, scrivere una nuova domanda, e modificare questo per punto ad esso.

Answer 6

ricorsivo e soluzioni iterative per calcolare insieme il potere in schema. Non completamente testato se

(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

Hereafter è una soluzione ricorsiva, che è simile a quelle già postato. Alcune affermazioni forniscono come tipo di test. Io non sono riuscito a usare "set" di tipo Python per rappresentare insieme di insiemi. Python ha detto che "gli oggetti della serie sono nel calcolo dell'hash" quando si tenta di espressione come "s.add (set ())".

Vedi anche soluzioni in molti linguaggi di programmazione a 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)