快捷導(dǎo)航

python——全排列數(shù)的生成方式

更新時(shí)間：2020年02月26日 16:44:27 作者：weixin_43028509

今天小編就為大家分享一篇python——全排列數(shù)的生成方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

【問(wèn)題描述】輸入整數(shù)N( 1 <= N <= 10 )，生成從1~N所有整數(shù)的全排列。

【輸入形式】輸入整數(shù)N。

【輸出形式】輸出有N!行，每行都是從1~N所有整數(shù)的一個(gè)全排列，各整數(shù)之間以空格分隔。各行上的全排列不重復(fù)。輸出各行遵循"小數(shù)優(yōu)先"原則, 在各全排列中，較小的數(shù)盡量靠前輸出。如果將每行上的輸出看成一個(gè)數(shù)字，則所有輸出構(gòu)成升序數(shù)列。具體格式見(jiàn)輸出樣例。

【樣例輸入1】1

【樣例輸出1】1

【樣例說(shuō)明1】輸入整數(shù)N=1，其全排列只有一種。

【樣例輸入2】3

【樣例輸出2】

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

【樣例說(shuō)明2】輸入整數(shù)N=3，要求整數(shù)1、2、3的所有全排列, 共有N!=6行。且先輸出1開(kāi)頭的所有排列數(shù)，再輸出2開(kāi)頭的所有排列數(shù)，最后輸出3開(kāi)頭的所有排列數(shù)。在以1開(kāi)頭的所有全排列中同樣遵循此原則。

【樣例輸入3】10

【樣例輸出3】

1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 10 9

1 2 3 4 5 6 7 9 8 10

1 2 3 4 5 6 7 9 10 8

1 2 3 4 5 6 7 10 8 9

1 2 3 4 5 6 7 10 9 8

1 2 3 4 5 6 8 7 9 10

1 2 3 4 5 6 8 7 10 9

1 2 3 4 5 6 8 9 7 10

1 2 3 4 5 6 8 9 10 7

…

【樣例說(shuō)明3】輸入整數(shù)N=10，要求整數(shù)1、2、3、…、10的所有全排列。上例顯示了輸出的前10行。

【運(yùn)行時(shí)限】要求每次運(yùn)行時(shí)間限制在20秒之內(nèi)。超出該時(shí)間則認(rèn)為程序錯(cuò)誤。提示：當(dāng)N增大時(shí)，運(yùn)行時(shí)間將急劇增加。在編程時(shí)要注意盡量?jī)?yōu)化算法，提高運(yùn)行效率。

q = []
def perm(n ,begin , end):#使用遞歸進(jìn)行全排列
  global q#將q定義成全局變量
  if begin >= end:#判斷是否排序到最后一個(gè)數(shù)
    q += n
  else:
    i = begin
    for num in range(begin , end):
      n[num], n[i] = n[i], n[num]
      perm(n, begin + 1, end)
      n[num], n[i] = n[i], n[num]
n = int(input())#輸入整數(shù)n
a = []
for i in range(1, n+1):#獲取1~n的列表
  a.append(i)
perm(a , 0 , n)
b = []
temp = 1
for w in range(1 , n+1):#獲得輸出行數(shù)
  temp *= w
for j in range(0 , temp):#將perm中q所得的列表進(jìn)行拆分
  b.append(q[j*n:j*n+n])
ss = sorted(b)#排序
for r in ss:
  for c in r:
    print(c , end=' ')
  print()

補(bǔ)充拓展：解決Python數(shù)字全排列的問(wèn)題

利用itertools模塊

按住control點(diǎn)一下permulations方法，是一個(gè)枚舉方法

import itertools

array = [1,2,3,4]
pailie = list(itertools.permutations(array))#要list一下，不然它只是一個(gè)對(duì)象
for x in pailie:
  for y in x:
    print(y,end=' ')
  print()

如果不是全排列，是按字典序輸出不重復(fù)的組合方式可以用這個(gè)庫(kù)的combinations

from itertools import combinations
import sys
a,b = map(int,input().split())# a表示組合的序列是1到幾，b表示進(jìn)行組合的一個(gè)是幾個(gè)數(shù)
if b > a:
  print('-1')
  sys.exit()
mylist = list(range(1,a+1))
for x in combinations(mylist,b):# 參數(shù)第一個(gè)是可迭代的序列，第二個(gè)是一個(gè)組合幾個(gè)數(shù)
  for index in x:
    print(index,end=' ')
  print()

輸入5,3如圖