大家好，我是Python進(jìn)階者。這篇文章的題目真的是很難取，索性先取這個(gè)了，裝個(gè)13好了。
前言
前幾天在才哥交流群里，有個(gè)叫【Rick Xiang】的粉絲在Python交流群里問了一道關(guān)于排列組合的問題，初步一看覺得很簡(jiǎn)單，實(shí)際上確實(shí)是有難度的。
題目是：一個(gè)列表中有隨機(jī)15個(gè)數(shù)，沒有重復(fù)值。從列表里面任意選5個(gè)數(shù)，如何選出來包含a, a+1的所有組合。a可以是15個(gè)數(shù)中的任意一個(gè)。
一、思路
這個(gè)問題看似簡(jiǎn)單，思路正如上圖的【張老師】說的那樣，分兩步走，理論上來說，確實(shí)是可以實(shí)現(xiàn)。正常我們計(jì)算排列組合公式，用下圖中的組合公式計(jì)算是沒問題的。
但是這道題目的實(shí)現(xiàn)，涉及到用Python程序進(jìn)行實(shí)現(xiàn)，當(dāng)然計(jì)算一個(gè)數(shù)值，對(duì)于Python和我們來說并不難，難的是需要回歸排列組合原本的狀態(tài)，然后用程序進(jìn)行實(shí)現(xiàn)。本文借用了群成員【有點(diǎn)意思】所說的蒙特卡洛算法和代碼進(jìn)行實(shí)現(xiàn)，下面一起來看看吧！
這里引用【張老師】提及的第二種方案，先隨機(jī)取14個(gè)數(shù)，然后從14個(gè)隨機(jī)數(shù)中隨機(jī)取一個(gè)，然后自增1，作為第15個(gè)隨機(jī)數(shù)，之后再?gòu)倪@15個(gè)隨機(jī)數(shù)中進(jìn)行隨機(jī)取5個(gè)隨機(jī)數(shù)，再進(jìn)行if判斷，看看連續(xù)值是否同時(shí)存在同一個(gè)列表中，之后把滿足條件的列表append到一個(gè)空列表中去，最后再去用set集合去重，得到最后的結(jié)果。
二、解決方法
1）偽代碼
這里先給出【有點(diǎn)意思】大佬的偽代碼，這樣看上去大家也更加好理解一些，如下圖所示。其實(shí)下面這個(gè)代碼也不算是偽代碼，現(xiàn)在Python也支持中文變量，下面這個(gè)代碼也是完全可以跑起來的，只不過看上去要比下文中的純英文代碼要更加好理解一些。
下面給出具體的實(shí)現(xiàn)過程，這里給出5份代碼，歡迎大家積極嘗試。
2）代碼一
# coding: utf-8import random
def quchong(list_data): list2 = [] for i in list_data: if i not in list2: list2.append(i) return list2
# 從隨機(jī)的15個(gè)數(shù)值中隨機(jī)取出5個(gè)數(shù)，放到一個(gè)數(shù)組# 生成不重復(fù)的14個(gè)隨機(jī)數(shù)random_14 = [random.randint(0, 100) for i in range(14)] # 這個(gè)寫法容易出現(xiàn)隨機(jī)值重復(fù)random_14 = random.sample(range(100), 14)print(random_14)random_1 = random.choice(random_14)random_2 = random_1 + 1random_14.append(random_2)random_15 = random_14print(random_1, random_2)
final_list = []for i in range(100): select = [random.choice(random_15) for j in range(5)] quchong_select = set(select) if random_1 in quchong_select and random_2 in quchong_select: final_list.append(quchong_select)fina_result = quchong(final_list)print(len(fina_result))
乍一看，這個(gè)方法確實(shí)可以實(shí)現(xiàn)，但是這里會(huì)有一個(gè)小bug，那就是random.randint()函數(shù)生成的隨機(jī)中會(huì)有重復(fù)值，而題目要求是生成不重復(fù)的隨機(jī)值。那么這個(gè)問題，將在代碼二中得到解決。
3）代碼二
使用random.sample()函數(shù)，這個(gè)函數(shù)可以隨機(jī)產(chǎn)生隨機(jī)值，而且不會(huì)重復(fù)，還是很奈斯的。另外，使用了numpy.random.choice()函數(shù)，可以直接選擇隨機(jī)的5個(gè)數(shù)，效率比代碼一更高一些。
# -*- coding: utf-8 -*-import numpy as npimport random
def quchong(list_data): list2 = [] for i in list_data: if i not in list2: list2.append(i) return list2
# 從隨機(jī)的15個(gè)數(shù)值中隨機(jī)取出5個(gè)數(shù)，放到一個(gè)數(shù)組# 生成不重復(fù)的14個(gè)隨機(jī)數(shù)random_14 = random.sample(range(100), 14)print(random_14)random_1 = random.choice(random_14)random_2 = random_1 + 1random_14.append(random_2)random_15 = random_14print(random_1, random_2)
final_list = []for i in range(100): sub_random_data = np.random.choice(random_15, 5) quchong_select = set(sub_random_data) if random_1 in quchong_select and random_2 in quchong_select: final_list.append(quchong_select)fina_result = quchong(final_list)print(len(fina_result))
4）代碼三
代碼三主要是在代碼一和代碼二的基礎(chǔ)上加了一些函數(shù)，使得讀起來更加的有邏輯性和層次感。
# -*- coding: utf-8 -*-# 模塊化import randomimport numpy as np
# 從隨機(jī)的15個(gè)數(shù)值中隨機(jī)取出5個(gè)數(shù)，放到一個(gè)數(shù)組，生成不重復(fù)的14個(gè)隨機(jī)數(shù)def get_random15(): random_14 = random.sample(range(1000), 14) print(random_14) random_1 = random.choice(random_14) random_2 = random_1 + 1 random_14.append(random_2) random_15 = random_14 print(random_1, random_2) get_final_result(random_1, random_2, random_15)
def get_final_result(random_1, random_2, random_15): final_list = [] for i in range(1000): sub_random_data = np.random.choice(random_15, 5) quchong_select = set(sub_random_data) if random_1 in quchong_select and random_2 in quchong_select: final_list.append(quchong_select) fina_result = quchong(final_list) print(len(fina_result))
def quchong(list_data): list2 = [] for i in list_data: if i not in list2: list2.append(i) return list2
if __name__ == '__main__': get_random15()
5）代碼四
細(xì)心的朋友可能已經(jīng)發(fā)現(xiàn)了一個(gè)問題，在隨機(jī)從np.random.choice(random_15, 5)取值的時(shí)候，也會(huì)取出重復(fù)的值，這樣也是不符合要求的，這里給出了一個(gè)方案，從15個(gè)隨機(jī)數(shù)中取出一個(gè)之后，然后remove掉這個(gè)取出的數(shù)，重新去剩下的列表中去取，這樣就完美的避開了這個(gè)問題。
# 模塊化import randomimport numpy as np
# 取出隨機(jī)的15個(gè)數(shù)值def get_random15(): for i in range(2): random_15 = random.sample(range(20), 15) # print(random_15) get_random5(random_15)
# 遍歷隨機(jī)的15個(gè)數(shù)值，取相鄰的兩個(gè)隨機(jī)數(shù)，并調(diào)用函數(shù)進(jìn)行處理def get_random5(random_15): random_5 = [] # 遍歷5次，從random_15中取5個(gè)不同的元素 for i in range(5): random_data = np.random.choice(random_15) random_5.append(random_data) random_15.remove(random_data) # print(random_5) for num in random_5: random_1 = num random_2 = random_1 + 1 get_final_result(random_1, random_2, random_5)
# 判斷相鄰的兩數(shù)值是否同時(shí)存在隨機(jī)的15個(gè)數(shù)值的列表中，如果滿足要求，就存到一個(gè)列表中，并調(diào)用去重函數(shù)def get_final_result(random_1, random_2, random_5): final_list = [] if random_1 in random_5 and random_2 in random_5: print(random_5) final_list.append(random_1) result = quchong(final_list) print(result)
# 針對(duì)得到的所有列表，進(jìn)行去重處理def quchong(list_data): list = [] for i in list_data: if i not in list: list.append(i) return list
if __name__ == '__main__': get_random15()
代碼寫到這里，已經(jīng)比之前的方案要好很多了，比之前的三個(gè)代碼都要嚴(yán)謹(jǐn)一些，但是仍然存在不足。雖然解決了隨機(jī)生成重復(fù)性的問題，也解決了隨機(jī)從random_15中取出重復(fù)數(shù)的問題，但是弊端還是存在的。這個(gè)代碼遍歷挺多的，復(fù)雜度倒是正常，但是輸出的格式不太好看，沒有達(dá)到預(yù)期。這里我只是遍歷了2次，而且隨機(jī)數(shù)我只是開放到0-20，如果循環(huán)次數(shù)增多，數(shù)值越多的話，計(jì)算起來速度可就不好說了。
6）代碼五
經(jīng)過【有點(diǎn)意思】大佬和我的共同努力，現(xiàn)在祭出終極版本，這個(gè)版本是迄今為止，針對(duì)該問題寫出的最嚴(yán)謹(jǐn)?shù)囊粋€(gè)版本了，代碼如下。
# -*- coding: utf-8 -*-# 模塊化import randomimport numpy as npimport time
# 取出隨機(jī)的15個(gè)數(shù)值def get_random15(): for i in range(100000): random_15 = random.sample(range(2000), 15) # print("隨機(jī)15數(shù)=",random_15,len(random_15)) get_random5(random_15)
# 遍歷隨機(jī)的15個(gè)數(shù)值，取相鄰的兩個(gè)隨機(jī)數(shù)，并調(diào)用函數(shù)進(jìn)行處理def get_random5(random_15): random_5 = [] # 遍歷5次，從random_15中取5個(gè)不同的元素 for i in range(5): random_data = np.random.choice(random_15) random_5.append(random_data) random_15.remove(random_data) # print("random_5=",random_5) # print("random_15=",random_15) for num in random_5: random_1 = num random_2 = random_1 + 1 # print(random_1,random_2) get_final_result(random_1, random_2, random_5)
# 判斷相鄰的兩數(shù)值是否同時(shí)存在隨機(jī)的15個(gè)數(shù)值的列表中，如果滿足要求，就存到一個(gè)列表中，并調(diào)用去重函數(shù)def get_final_result(random_1, random_2, random_5): final_list = [] if random_1 in random_5 and random_2 in random_5: # print(random_5) final_list.append(random_5) result = quchong(final_list) if result: if len(result[0]) == 5: # print(random_1,random_2) # print("result=",result) final_result.append(result)
# 針對(duì)得到的所有列表，進(jìn)行去重處理def quchong(list_data): list = [] for i in list_data: if i not in list: list.append(i) return list
if __name__ == '__main__': start_time = time.time() global final_result final_result = [] get_random15()
final_result = quchong(final_result) print("共%d個(gè)符合題意的列表" % len(final_result)) print("分別是：%s" % final_result)
end_time = time.time() used_time = end_time - start_time print() print("本次程序用時(shí)：{}".format(time.strftime('%H(小時(shí)):%M（分鐘）:%S（秒）', time.gmtime(used_time))))
這個(gè)代碼運(yùn)行之后，可以看到符合題意列表的具體個(gè)數(shù)，還有具體的列表數(shù)值，還有耗時(shí)時(shí)間。
經(jīng)過測(cè)試，在10萬次循環(huán)以內(nèi)，符合要求的數(shù)據(jù)大概有1000左右，運(yùn)行時(shí)間也只是秒級(jí)的。如果繼續(xù)擴(kuò)大循環(huán)力度，程序的復(fù)雜度會(huì)更加大，更加貼近理論的排列組合值，因?yàn)楹臅r(shí)太長(zhǎng)，這里不再做測(cè)試，感興趣的話，自己可以改下參數(shù)進(jìn)行調(diào)試。
三、總結(jié)
我是Python進(jìn)階者。本文基于粉絲針對(duì)排列組合問題的提問，給出了一個(gè)利用Python基礎(chǔ)+蒙特卡洛算法的解決方案，基本上可以達(dá)到了粉絲的要求。
不過話說回來，這個(gè)方案還是存在一定的弊端的，隨著循環(huán)次數(shù)越多，隨機(jī)數(shù)越大，排列組合數(shù)就會(huì)越多，運(yùn)行的時(shí)間也就會(huì)越長(zhǎng)，當(dāng)然得到的數(shù)據(jù)也就更加的精準(zhǔn)了。
最后感謝【Rick Xiang】提問，感謝【張老師】提供的思路，感謝【有點(diǎn)意思】大佬一直和我探討交流學(xué)習(xí)，這一過程，雖然耗時(shí)，但是也是學(xué)到了很多知識(shí)，也感謝我寄幾花時(shí)間和經(jīng)歷整理這篇接近4000字的文章。
針對(duì)這個(gè)問題，小編這里整理了1個(gè)思路，當(dāng)然實(shí)現(xiàn)方法肯定遠(yuǎn)遠(yuǎn)不只是這1種，如果你有其他的方法，可以隨時(shí)分享給我噢！
------------------- End -------------------
