Imprimer n choisir k algorithme de combinaison utilisant la récursivité

Question

Cela doit être une question d'entrevue classique, cependant, j'ai un problème pour la comprendre.

Ci-dessous est mon implémentation en Python et si vous l'exécutez, il est seulement l'impression ab, ac, ad. Il ne va pas au niveau 'b' (bc, bd).

def Print_nCk (the_list, k, str_builder, used): 
    if len(str_builder) == k: 
     print str_builder 
     return 
    else: 
     for i in xrange(len(the_list)): 
      if used[i] !=True: 
       str_builder+=the_list[i] 
       used[i] = True 
       Print_nCk(the_list, k, str_builder, used) 
       str_builder = str_builder[:-1] 


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False]) 

La bonne réponse est ab,ac,ad,bc,bd,cd lorsque la ligne ci-dessus est transmise.

Je connais la bonne implémentation d'ici sans utiliser used param (http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/) mais ma question est ce qui ne va pas est ma mise en œuvre?

Pouvez-vous nous éclairer?

Pour déboguer, j'ai imprimé "utilisé" à chaque fois. Le used param devient (True, True, True, True) après avoir imprimé "ad" alors il ne va pas plus loin que cela. Quelle est la façon intelligente de réparer le used, si j'insiste pour utiliser used?

Answer 1

Vous avez oublié de unset used[i] lorsque vous faites marche arrière:

def Print_nCk (the_list, k, str_builder, used): 
    if len(str_builder) == k: 
     print str_builder 
     return 
    else: 
     for i in xrange(len(the_list)): 
      if used[i] != True: 
       str_builder += the_list[i] 
       used[i] = True 
       Print_nCk(the_list, k, str_builder, used) 
       str_builder = str_builder[:-1] 
       used[i] = False 


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

Dans votre implémentation actuelle, vous définissez used[i] à True à partir du moment où vous prenez la i en tant que valeur. Si toutefois, plus tard, vous décidez de choisir une autre succursale, vous devriez faire la comptabilité correctement et ainsi mettre à used[i].

Notez que maintenant "ab" et "ba" seront générés. Vous générer ainsi des combinaisons avec la symétrie. Si vous ne le souhaitez pas, vous pouvez utiliser un paramètre supplémentaire . Cela fait en sorte que vous ne utiliser un index inférieur au préalable choisi un:

def Print_nCk (the_list, k, str_builder, used, prev = 0): 
    if len(str_builder) == k: 
     print str_builder 
     return 
    else: 
     for i in xrange(prev,len(the_list)): 
      if used[i] != True: 
       str_builder += the_list[i] 
       used[i] = True 
       Print_nCk(the_list, k, str_builder, used, i+1) 
       str_builder = str_builder[:-1] 
       used[i] = False 


Print_nCk(['a','b','c','d'], 2, "",[False,False,False,False])

Néanmoins, cette plus ou moins défaites dans le but d'utiliser un tableau « utilisé ». Vous pouvez simplement utiliser les prev:

def Print_nCk (the_list, k, str_builder, prev = 0): 
    if len(str_builder) == k: 
     print str_builder 
     return 
    else: 
     for i in xrange(prev,len(the_list)): 
      str_builder += the_list[i] 
      Print_nCk(the_list, k, str_builder, i+1) 
      str_builder = str_builder[:-1] 


Print_nCk(['a','b','c','d'], 2, "")

Ce puis imprime:

>>> Print_nCk(['a','b','c','d'], 2, "") 
ab 
ac 
ad 
bc 
bd 
cd 

Answer 2

peu tard à la fête, mais je pense que vous devriez profiter davantage de récursivité. Il n'y a pas besoin de passer des arguments superflus.

est ici une approche plus simple:

def Print_nCk(the_list, size): 
    combs = [] 
    if size == 1: # the base case 
     return the_list 

    for i, c in enumerate(the_list[:-size + 1]): 
     for sub_comb in Print_nCk(the_list[i + 1:], size - 1): # generate and return all sub-combos of size - 1 
      combs.append(c + sub_comb) # for each sub-combo, add the sizeth (or n - sizeth) character 

    return combs 

Cette approche génère des combinaisons de size - 1 et les combine avec le caractère size e.

pour la taille-2 combinaisons:

>>> Print_nCk(['a','b','c','d'], 2) 
['ab', 'ac', 'ad', 'bc', 'bd', 'cd'] 

Pour les combinaisons de taille-3:

>>> Print_nCk(['a','b','c','d'], 3) 
['abc', 'abd', 'acd', 'bcd']