印刷n再帰を使用してkの組み合わせアルゴリズムを選択

Question

これは古典的なインタビューの質問でなければなりませんが、私はそれを理解することに問題があります。

以下はPythonで実装したものです。実行すると、ab, ac, adしか印刷されません。それは'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]) 

上記の行を渡したときの正解はab,ac,ad,bc,bd,cdです。

used param（http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/）を使用せずにここから正しい実装を知っていますが、 私の質問は私の実装ですか？

あなたはそれに少し気をつけていただけますか？

デバッグするたびに、私は毎回「used」を印刷しました。 used paramは "ad"を印刷した後に（True、True、True、True）になり、それより深くは進まない。 usedを使用するとしたら、usedを修正するにはどうすればいいですか？あなたがをバックトラックときは、解除used[i]に忘れてしまった

Answer 1

は：

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

あなたの現在の実装では、あなたが値としてiを選ぶ瞬間からTrueへused[i]を設定します。しかし、後で別の支店を選ぶ場合は、正しく簿記を行い、used[i]の設定を解除する必要があります。

今すぐ"ab"と"ba"が生成されることに注意してください。したがって、は対称性を持つ組み合わせを生成します。必要がない場合は、追加パラメータを使用することができます。それはあなたがが以前よりも低い屈折率を使用していないことを確認します選んだ1：

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

それにもかかわらず、この多かれ少なかれ敗北「使用」のアレイを使用する目的。

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, "")

この後、プリント：あなたは、単にprevを使用することができます

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

Answer 2

少し遅れてパーティーに、しかし、私はあなたが再帰をもっと活用するべきだと思います。余分な引数を渡す必要はありません。

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 

このアプローチはsize - 1の組み合わせを生成し、size番目の文字とそれらを組み合わせた：

は、ここで簡単な方法です。サイズ3の組み合わせについて

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

：サイズ-2の組み合わせについて

ところで