Python - Số lớn nhất có thể tạo từ danh sách số cho trước

Tìm số lớn nhất có thể tạo bằng cách sắp xếp lại thứ tự các số trong danh sách.

Cách 1: Sinh tất cả hoán vị (dùng itertools.permutations), nối thành chuỗi, lấy max.

import itertools
numbers = [45, 35, 138, 43, 67]
result = []
for perm in itertools.permutations(str(n) for n in numbers):
    result.append(''.join(perm))
maximum = max(result, key=int)
print(int(maximum))  # 67454335138

Cách 2: Sắp xếp tùy chỉnh với functools.cmp_to_key. So sánh str(a)+str(b) vs str(b)+str(a).

from functools import cmp_to_key
numbers = [45, 35, 138, 43, 67]

def get_key(first, second):
    if str(first) + str(second) > str(second) + str(first):
        return -1
    return 1

result = sorted(numbers, key=cmp_to_key(get_key))
result = ''.join(str(x) for x in result)
print(int(result))  # 67454335138

Kết luận

Cách 2 hiệu quả hơn nhiều (O(n log n) thay vì O(n!)).