Maison  >  Article  >  développement back-end  >  Exemple d'implémentation Python de recherche de tous les sous-ensembles d'un ensemble

Exemple d'implémentation Python de recherche de tous les sous-ensembles d'un ensemble

不言
不言original
2018-05-05 10:19:054170parcourir

Cet article présente principalement l'exemple d'implémentation de Python pour trouver tous les sous-ensembles d'un ensemble. Il a une certaine valeur de référence. Maintenant, je le partage avec vous. Les amis dans le besoin peuvent s'y référer

<.>Méthode 1 : Implémentation de la régression

def PowerSetsRecursive(items):
  """Use recursive call to return all subsets of items, include empty set"""
  
  if len(items) == 0:
    #if the lsit is empty, return the empty list
    return [[]]
  
  subsets = []
  first_elt = items[0] #first element
  rest_list = items[1:]
  
  #Strategy:Get all subsets of rest_list; for each of those subsets, a full subset list
  #will contain both the original subset as well as a version of the sebset that contains the first_elt
  
  for partial_sebset in PowerSetsRecursive(rest_list):
    subsets.append(partial_sebset)
    next_subset = partial_sebset[:] +[first_elt]
    subsets.append(next_subset)
  return subsets

def PowerSetsRecursive2(items):
  # the power set of the empty set has one element, the empty set
  result = [[]]
  for x in items:
    result.extend([subset + [x] for subset in result])
  return result

Méthode 2 : Méthode binaire

def PowerSetsBinary(items): 
  #generate all combination of N items 
  N = len(items) 
  #enumerate the 2**N possible combinations 
  for i in range(2**N): 
    combo = [] 
    for j in range(N): 
      #test jth bit of integer i 
      if(i >> j ) % 2 == 1: 
        combo.append(items[j]) 
    yield combo

Recommandations associées :


Méthode Python pour déterminer si un ensemble est un sous-ensemble d'un autre ensemble

Méthode Python pour implémenter un traitement simple de chaîne de texte

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn