Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como implementar um programa para gerar todos os subconjuntos de um determinado conjunto?

+1 voto
103 visitas
perguntada Abr 20, 2016 em Ciência da Computação por danielcajueiro (5,786 pontos)  
Compartilhe

1 Resposta

0 votos
respondida Abr 20, 2016 por danielcajueiro (5,786 pontos)  

Um exemplo bem simples usando a idéia que todos os subconjuntos podem ser divididos em dois grupos:

1) Aqueles que contém um determinado elemento

2) Aqueles que não contém um determinado elemento

from collections import deque
import copy

def no_none(x):
    return x!='0000'

def generate_subsets(mySet,myList=[]):
    numberElements=len(mySet)
    n=len(myList)
    if(n==numberElements):
        print filter(no_none,myList) #First attempt to funcional programming?
    else:
        x=myList[:]
        x.append('0000')
        generate_subsets(mySet,x)
        y=myList[:]
        y.append(mySet[n])
        generate_subsets(mySet,y)    

if __name__ == '__main__':

    n=3
    mySet=['a','b','c']
    generate_subsets(mySet)
...