《中学数学》排列组合问题之：错位重排（python实现）

问题引出:
编号为1-N的N个小球，装入编号为1-N的N个盒子，
要求每个盒子装一个小球，并且盒子和小球的编号不相同。
问有几种排法？
假设N个小球有D[N]种排法，
易得:
D[1]=0,  D[2]=1,  D[3]=2;
容易推导关系式：
D[n] = (n-1) * { D[n-1] + D[n-2] } ,其中n>=3;

代码展示:

方法1:公式递推法

def getN(N):assert type(N) == type(1) , "输入数据类型错误!!!"assert N > 0 , "输入数据取值范围错误!!!"if N == 1:return 0if N == 2:return 1if N > 2:return (N-1)*(getN(N-1)+getN(N-2))for i in range(1,20):print("D{0} = {1}".format(i,getN(i)))

控制台下输出:

Windows PowerShell
版权所有 (C) Microsoft Corporation。保留所有权利。尝试新的跨平台 PowerShell https://aka.ms/pscore6加载个人及系统配置文件用了 851 毫秒。
(base) PS C:\Users\chenxuqi\Desktop\News4cxq\实验> conda activate pytorch_1.7.1_cu102
(pytorch_1.7.1_cu102) PS C:\Users\chenxuqi\Desktop\News4cxq\实验>  & 'D:\Anaconda3\envs\pytorch_1.7.1_cu102\python.exe' 'c:\Users\chenxuqi\.vscode\extensions\ms-python.python-2021.6.944021595\pythonFiles\lib\python\debugpy\launcher' '51893' '--' 'c:\Users\chenxuqi\Desktop\News4cxq\实验\test.py'
D1 = 0
D2 = 1
D3 = 2
D4 = 9
D5 = 44
D6 = 265
D7 = 1854
D8 = 14833
D9 = 133496
D10 = 1334961
D11 = 14684570
D12 = 176214841
D13 = 2290792932
D14 = 32071101049
D15 = 481066515734
D16 = 7697064251745
D17 = 130850092279664
D18 = 2355301661033953
D19 = 44750731559645106
(pytorch_1.7.1_cu102) PS C:\Users\chenxuqi\Desktop\News4cxq\实验> 

方法2:深度优先搜索实现暴力枚举:

# 深度优先搜索实现错位重排问题
count = 0
def getN(N):assert type(N) == type(1) , "输入数据类型错误!!!"assert N > 0 , "输入数据取值范围错误!!!"global countcount = 0count_shuffle_num([None],list(range(1,N+1)),N)def count_shuffle_num(prior,resNums,chosNums):global countif chosNums < 1:returnelif chosNums == 1:prior = prior + resNumsif len(prior)-1 != prior[-1]:count += 1# print(prior)returnelse:for i in resNums:if i == len(prior):continueelse:resNums_ = resNums[:]resNums_.remove(i)count_shuffle_num(prior+[i],resNums_,chosNums-1)if __name__ == '__main__':for i in range(1,12):getN(i)print("D{0} = {1}".format(i,count))

控制台下输出:

Windows PowerShell
版权所有 (C) Microsoft Corporation。保留所有权利。尝试新的跨平台 PowerShell https://aka.ms/pscore6加载个人及系统配置文件用了 957 毫秒。
(base) PS C:\Users\chenxuqi\Desktop\News4cxq\实验> conda activate pytorch_1.7.1_cu102
(pytorch_1.7.1_cu102) PS C:\Users\chenxuqi\Desktop\News4cxq\实验>  & 'D:\Anaconda3\envs\pytorch_1.7.1_cu102\python.exe' 'c:\Users\chenxuqi\.vscode\extensions\ms-python.python-2021.6.944021595\pythonFiles\lib\python\debugpy\launcher' '52379' '--' 'c:\Users\chenxuqi\Desktop\News4cxq\实验\test.py'
D1 = 0
D2 = 1
D3 = 2
D4 = 9
D5 = 44
D6 = 265
D7 = 1854
D8 = 14833
D9 = 133496
D10 = 1334961
D11 = 14684570
(pytorch_1.7.1_cu102) PS C:\Users\chenxuqi\Desktop\News4cxq\实验> 

打印各种组合(按照序列递增顺序枚举):

# 深度优先搜索实现错位重排问题
count = 0
def getN(N):assert type(N) == type(1) , "输入数据类型错误!!!"assert N > 0 , "输入数据取值范围错误!!!"global countcount = 0count_shuffle_num([None],list(range(1,N+1)),N)def count_shuffle_num(prior,resNums,chosNums):global countif chosNums < 1:returnelif chosNums == 1:prior = prior + resNumsif len(prior)-1 != prior[-1]:count += 1# print(prior)print('              ',prior[1:],'\tcount =',count)returnelse:for i in resNums:if i == len(prior):continueelse:resNums_ = resNums[:]resNums_.remove(i)count_shuffle_num(prior+[i],resNums_,chosNums-1)if __name__ == '__main__':a = 5print('位置序号标记->',list(range(1,a+1)),'<-位置序号标记')getN(a)print('综上所述:\tD{0} = {1}'.format(a,count))

控制台下结果输出:

Windows PowerShell
版权所有 (C) Microsoft Corporation。保留所有权利。尝试新的跨平台 PowerShell https://aka.ms/pscore6加载个人及系统配置文件用了 971 毫秒。
(base) PS C:\Users\chenxuqi\Desktop\News4cxq\实验> conda activate pytorch_1.7.1_cu102
(pytorch_1.7.1_cu102) PS C:\Users\chenxuqi\Desktop\News4cxq\实验>  & 'D:\Anaconda3\envs\pytorch_1.7.1_cu102\python.exe' 'c:\Users\chenxuqi\.vscode\extensions\ms-python.python-2021.6.944021595\pythonFiles\lib\python\debugpy\launcher' '52632' '--' 'c:\Users\chenxuqi\Desktop\News4cxq\实验\test.py'
位置序号标记-> [1, 2, 3, 4, 5] <-位置序号标记[2, 1, 4, 5, 3]  count = 1    [2, 1, 5, 3, 4]  count = 2    [2, 3, 1, 5, 4]  count = 3    [2, 3, 4, 5, 1]  count = 4    [2, 3, 5, 1, 4]  count = 5    [2, 4, 1, 5, 3]  count = 6    [2, 4, 5, 1, 3]  count = 7    [2, 4, 5, 3, 1]  count = 8    [2, 5, 1, 3, 4]  count = 9    [2, 5, 4, 1, 3]  count = 10   [2, 5, 4, 3, 1]  count = 11[3, 1, 2, 5, 4]  count = 12[3, 1, 4, 5, 2]  count = 13[3, 1, 5, 2, 4]  count = 14[3, 4, 1, 5, 2]  count = 15[3, 4, 2, 5, 1]  count = 16[3, 4, 5, 1, 2]  count = 17[3, 4, 5, 2, 1]  count = 18[3, 5, 1, 2, 4]  count = 19[3, 5, 2, 1, 4]  count = 20[3, 5, 4, 1, 2]  count = 21[3, 5, 4, 2, 1]  count = 22[4, 1, 2, 5, 3]  count = 23[4, 1, 5, 2, 3]  count = 24[4, 1, 5, 3, 2]  count = 25[4, 3, 1, 5, 2]  count = 26[4, 3, 2, 5, 1]  count = 27[4, 3, 5, 1, 2]  count = 28[4, 3, 5, 2, 1]  count = 29[4, 5, 1, 2, 3]  count = 30[4, 5, 1, 3, 2]  count = 31[4, 5, 2, 1, 3]  count = 32[4, 5, 2, 3, 1]  count = 33[5, 1, 2, 3, 4]  count = 34[5, 1, 4, 2, 3]  count = 35[5, 1, 4, 3, 2]  count = 36[5, 3, 1, 2, 4]  count = 37[5, 3, 2, 1, 4]  count = 38[5, 3, 4, 1, 2]  count = 39[5, 3, 4, 2, 1]  count = 40[5, 4, 1, 2, 3]  count = 41[5, 4, 1, 3, 2]  count = 42[5, 4, 2, 1, 3]  count = 43[5, 4, 2, 3, 1]  count = 44
综上所述:       D5 = 44
(pytorch_1.7.1_cu102) PS C:\Users\chenxuqi\Desktop\News4cxq\实验> 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！