7
votes

Générez tous les sous-ensembles "uniques" d'un ensemble (pas un powerset)

Disons que nous avons un ensemble S qui contient quelques sous-ensembles: xxx

disons également que s contient six éléments uniques: a, b , c, d, e et f .

Comment trouver tous les sous-ensembles possibles de s contenant chacun des éléments uniques de S exactement une fois?

Le résultat de la fonction / méthode doit être quelque chose comme ça:


  [[[A, B, C], [D, E, F]];  
  [[[A, B, C], [D, F], [E]];  
  [[[A, B], [C], [D, E, F]];  
  [[[A, B], [C], [D, F], [E]].  
  Y a-t-il une meilleure pratique ou une façon standard d'atteindre cela?  
 Je serais reconnaissant pour un pseudo-code, un exemple de rubis ou d'erlang.


                        
                        
                            
                                                                    ruby
                                                                    set
                                                                    erlang
                                                                    subset
                                                                    powerset
                                                            
                        
                                                    
                            
                            
                                0 commentaires



                                    
                    5 Réponses :
                    
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Pourquoi ne pas utiliser l'algorithme gourmand? 

 1) Set Set s descendre à l'aide de la longueur des sous-ensembles 

2) Laissez I: = 0 

3) Ajouter S [i] à la solution 

4) Trouver S [J] où J> i tel qu'il contient des éléments qui ne sont pas en solution actuelle 

5) Si vous ne trouvez pas l'élément décrit dans 4, puis
  5.A) Solution claire 

  5.b) Augmenter i 

  5.C) Si je> | S | Puis casser, pas de solution trouvée; (
  5.d) goto 3 

  Modifier  

Hmm, lisez votre message et venez en conclusion que vous avez besoin d'un  Meilleure première recherche . Votre question n'est pas réellement un problème de partition car ce dont vous avez besoin est également appelé  Problème de modification de la tâche  Mais dans cette dernière situation, la toute première solution est prise comme la meilleure - vous souhaitez réellement trouver toutes les solutions et c'est la raison pour laquelle vous devriez vous devoir la meilleure approche de stratégie de recherche.                                 


                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Cela semble être une exercice classique "BackTrack". 


 # 1: Commandez vos séries parmi ESCETHER, la bande-backtrack ne donnera pas deux solutions deux fois. 
 # 2: actuel_set = [], set_list = [] 
 # 3: boucle traversant tout le jeu d'ordre inférieur à celui du dernier dans la liste SET_LIST (ou si la définition est vide). Appelez-le Set_at_hand 
 # 4: si SET_AT_ADHAND n'a aucune intersection avec actuelle_set 
 # 4 / true / 1: Union it to Current_Set, ajoutez également à Set_List. 
 # 4 / true / 2: courant_set complet? True: Ajouter Set_List dans la liste des solutions correctes. FAUX: RECURSE À # 3 
 # 4 / true / 3: retirez SET_AT_HORD de Current_set et Set_List 
 # 5: fin de boucle 
 # 6: retour 
                                

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    3
 votes
                                
                            
                            
                                
                                     On dirait que ce que vous cherchez sont les  Partitions  d'un ensemble / matrice. < p> Une façon de le faire est récursivement:  

 Un tableau 1 élément [x] a exactement une partition 
 Si X est un tableau de la forme X = [tête] + queue, puis les partitions de X sont générées en prenant chaque partition de la queue et en ajoutant la tête à chaque possible. Par exemple, si nous produisions les partitions de [3,2,1] à partir de la partition [[2,1]] de [2,1], nous pouvons ajouter 3 à [2,1] ou comme élément distinct , qui nous donne 2 partitions [[3,2,1] ou [[[2,1], [3]] du 5 que [1,2,3] a 
  Une implémentation de rubis ressemble un peu à   xxx                                  

                                                                    
                                    
                                    
                                        3 commentaires
                                        
                                                                                            
                                                    Fonctionne très bien! Mais j'ai trouvé que cela se bloque pour quelque chose d'égal ou supérieur à 10 articles. Une idée pourquoi? Les partitions en cours d'exécution ([1,2,3,4,5,6,7,8,9,10]) accrochent de rubis                                                
                                                
                                                                                            
                                                    Les collections impliquées deviennent grandes assez rapidement - il y a 115975 partitions d'un tableau de 10 articles, il n'a toujours pas pris quelques secondes sur ma machine. Si vous exécutez ceci en IRB, il tentera d'afficher le résultat - pas une bonne idée!                                                
                                                
                                                                                            
                                                    Il se bloque réellement dans les rails et en courant sous RSPEC de RUBYMINE. Je suis sur Mac Running Lion. Mon problème est en fait plus spécialisé que cela, donc je l'ai posté ici:  Stackoverflow.com/Questtions/9732944/...                                                 
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     générer tous les sous-ensembles  xxx                                  

                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Jetez un oeil ici:  https://github.com/sagivo/algorithms /blob/master/powerset.rb  

Ceci est un algorithme simple que j'ai construit pour trouver un powerset d'un tableau.                                 

                                                                    
                                    
                                    
                                        0 commentaires


            
                
		    
                    Articles qui pourrait vous intéresser :
                                            
                            Problème lors de l'installation de ruby-2.7.1                        
                        
                                            
                            commande pry introuvable après l'installation de gem                        
                        
                                            
                            nokogiri ne s'installe pas dans ruby 2.7.1 centos 7.2                        
                        
                                            
                            Comment masquer le titre du formulaire qui apparaît à l'intérieur d'une balise de légende lors de la génération de cases à cocher pour une association à l'aide de simple-form?