30/09/2018, 20:08

Cách chọn ra cấu hình phù hợp sau khi liệt kê

em có bài tập in ra cấu hình thứ k trong n hoán vị của 1 tập hợp. Vậy sau khi e liệt kê được toàn bộ các cấu hình thì làm sao để chọn ra cấu hình thứ k để in ra ạ. Mong mọi người giúp đỡ. Em cảm ơn

Gió viết 22:22 ngày 30/09/2018

Bài này không cần thiết phải liệt kê hết hoán vị của n phần tử.
Ta có nhận xét sau: nếu một dãy hoán vị đã dc sắp xếp theo thứ tự của a1,a2,a3,a4…,an thì mỗi số a[i] đứng đầu dãy đúng (n-1)! Lần. Từ nhận xét này ta tìm dc vị trí đầu tiên dựa theo k. Lặp lại các bước đối với các giá trị còn lại thì dc hoán vị cần tìm
Code tham khảo

from itertools import *
from math import *
n=8
a=list(range(n))
perm=list(permutations(a,n)) #hoán vị để đối chiếu thuật toán
k=124
print(perm[k])

res=[]
for i in range(n,0,-1):
 res.append(a[k//factorial(i-1)])
 k=k%factorial(i-1)
 #các dòng sau để xoá giá trị đã sử dụng
 for j in range(len(a)):
  if a[j]==res[-1]:
   del a[j]
   break

print(res)

Vikiki viết 22:12 ngày 30/09/2018

e cảm ơn anh ạ. nhưng e code trên C thì dùng mảng có hợp lý không ạ

Gió viết 22:17 ngày 30/09/2018

Code bằng mảng là ok rồi. Độ phức tạp cỡ O(n^3) nên cũng không cần tối nhiều

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Vikiki

0 chủ đề

0 bài viết

Tác giả nổi bật