以下為小弟我自己刻出來的排列組合中的組合C(n,k)之程式碼,我知道有些更好的寫法,但抱著自己刻刻看的心態做到了這一步
主要邏輯:因組合=沒有順序之排列,因此取由小到大之組合當排列,但因下方程式碼沒寫好,會導致重複同樣組合輸出多次,而小弟我打算用建表的方式確認輸出是否在表中,若否則放入並輸出,是的話就跳過,但無論如何都只會碰到表的第一格,感覺上遞迴呼叫會不段刷新表(dic)以及計數(count2),想請問各位大大該怎麼辦ˊㄇˋ
dic=[None]*50
count2=0
def cnk(n,k): # 主函數
p = [] # p
y=1
return permNext(n,k,p,y) # 呼叫 permNext 遞迴下去排出所有可能
def permNext(n,k,p,y):
count=0
global count2
global dic
i = len(p)
if i == k:
if not p in dic: #確認是否在字典裡 否則放入並印出 是則do nothing
dic[count2]=p
print(dic[count2])
count2=count2+1
return
for x in range(y,n+1): #因為組合沒有順序性 因此想法為只找由小到大 則為全部組合
permNext(n,k,p,y+1)
if x not in p:
for j in range(len(p)):
if x > p[j]:
count=count+1
if count == len(p):
p.append(x)
permNext(n,k,p,y+1)
p.pop()
cnk(6,3)
上面之輸出為[4, 5, 6]
若是選擇輸出dic則為[[4, 5, 6], None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
已邀請的邦友 {{ invite_list.length }}/5
遞迴第一課：不使用全域變數
遞迴第二課: 都用迴圈了,這遞迴不純啊.
遞迴就是不要用迴圈,才能發揮其優點.
遞迴第二課: 都用迴圈了,這遞迴不純啊.
敢情是「類遞迴」
了解,因為最近在嘗試學習遞迴,腦袋一直打結轉不過來,還是某部分還是下意識用迴圈去寫了,想請問為什麼遞迴沒辦法使用全域變數呢?
為什麼要用全域變數??
應該說,比較好奇的是為什麼不能,是不需要嗎?還是哪裡會出錯呢?如果單純是以我此次寫的程式的話我是希望將取好的set藉由count2=count2+1 的方式放入array[count2]當中,但寫出來卻會報錯說在定義之前就使用到了count2這個變數,上網查了一下之後才加上了global
我的想法是,讓count2跟dic[]都可以被所有的函式所看到,修改,比對這樣,所以才想說用全域變數的方式
首先按照你想做的事情，若要過濾重複的為什麼不用tuple+set
再來，你這樣寫根本繞遠路.....
不是說雖然知道有更好的寫法什麼的，而是你剛開始的思維就是錯的，你沒有必要去進行比對有沒有重複的東西，直接進行二元處理不香嗎？是1的就選取，0的話就不選取不就好了
def cnk(n,k):
result = []
temp1 =list(range(1,n+1))
for i in range(1, 2**n):
temp2 = list(bin(i)[2:].zfill(n))
if temp2.count('1')!=3:
continue
result.append([str(i) for i, j in zip(temp1, temp2) if int(j)])
return result
print(cnk(6,3))
確實二元處理邏輯上也比較好理解,只是想說用遞迴去寫寫看,抱著繞遠路也沒關係的心態想說把它寫出來,但結果不甚理想ˊㄇˋ
owen4096
用tuple儲存你要進行排列的數字
set可以過濾掉重複的東西，就可以找到全部的組合
配合len就可以得到有幾組組合
原來是這樣,下次會試試看這種方式,感謝您
看影片追技術