Permutations

+10

Bạn nhận được một danh sách nums gồm các số nguyên khác nhau. Hãy trả về mọi cách sắp xếp các giá trị đó, mỗi cách là một danh sách sử dụng mỗi giá trị đúng một lần, vì vậy n giá trị sẽ tạo ra n! cách sắp xếp. Liệt kê chúng theo thứ tự từ điển: so sánh hai cách sắp xếp ở từng vị trí và để vị trí khác nhau đầu tiên quyết định thứ tự. Với [1, 2, 3], thứ tự này đặt [1, 2, 3] lên đầu và [3, 2, 1] xuống cuối.

Hàm

permute(nums: integer-array) → integer-2d-array

numsinteger-array: các giá trị, tất cả đều khác nhau, theo thứ tự bất kỳ
Trả vềinteger-2d-array: mọi cách sắp xếp các giá trị, được liệt kê theo thứ tự từ điển

Ràng buộc

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Tất cả giá trị trong nums đều khác nhau.
nums có thể xuất hiện theo bất kỳ thứ tự nào.

Ví dụ

Đầu vào: nums = [3, 1, 2]
Đầu ra: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Giải thích: Các thứ tự bắt đầu bằng 1 đứng trước, và [1, 2, 3] đứng trước [1, 3, 2] vì ở vị trí thứ hai, 2 nhỏ hơn 3. Thứ tự đầu vào không quan trọng.

Đầu vào: nums = [2, -1]
Đầu ra: [[-1, 2], [2, -1]]
Giải thích: Hai giá trị có thể được viết theo hai thứ tự. [-1, 2] đứng trước vì -1 nhỏ hơn 2.

Câu hỏi mở rộng

Với một thứ tự đã cho, bạn có thể tạo thứ tự tiếp theo theo thứ tự từ điển ngay trên dữ liệu đó trong thời gian O(n) và dùng thêm O(1) bộ nhớ không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

n giá trị khác nhau có n! cách sắp xếp, 6 giá trị có 720 cách, và bạn phải liệt kê tất cả, nên khối lượng công việc ít nhất là n × n!. Quay lui qua các giá trị đã sắp xếp, luôn thử giá trị nhỏ nhất chưa dùng trước, sẽ tạo mỗi cách sắp xếp đúng một lần và xuất chúng theo thứ tự từ điển.

Điền vào từng chỗ trống, sau đó sắp xếp

Ý tưởng

Hãy tạo dần các thứ tự, mỗi lần thêm một giá trị, bắt đầu từ danh sách rỗng. Để thêm 3 vào [1, 2], chèn nó vào một trong ba khoảng trống: [3, 1, 2], [1, 3, 2] và [1, 2, 3]. Mỗi thứ tự gồm k+1 giá trị được tạo đúng một lần: xóa giá trị mới thêm nhất, bạn sẽ có thứ tự mà nó được tạo ra từ đó, còn vị trí của nó cho biết khoảng trống.

Các thứ tự không xuất hiện theo đúng thứ tự: với [1, 2, 3], thứ tự đầu tiên được tạo ra là [3, 2, 1]. Vì vậy, cuối cùng bạn phải sắp xếp, cần khoảng n! × log(n!) phép so sánh, mỗi phép so sánh tối đa n giá trị, tương đương khoảng 720 × 9.5 × 6 ≈ 41,000 lần đọc với sáu giá trị. Cách này cũng lưu cả một thế hệ thứ tự trong bộ nhớ.

Thuật toán

Bắt đầu bằng một danh sách chứa một thứ tự rỗng.
Với mỗi giá trị trong nums, tạo một danh sách mới: với mỗi thứ tự hiện có và mỗi vị trí chèn từ 0 đến độ dài của thứ tự đó, sao chép thứ tự và chèn giá trị vào vị trí đó.
Thay danh sách cũ bằng danh sách mới.
Sắp xếp các thứ tự theo từng vị trí rồi trả về chúng.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Quay lui với mảng đánh dấu phần tử đã dùng

Ý tưởng

Lấp đầy n vị trí từ trái sang phải: có n ứng viên cho vị trí đầu tiên, n-1 ứng viên cho vị trí thứ hai, cứ tiếp tục như vậy. Hãy hình dung cấu trúc này như một cây: mỗi cạnh đặt thêm một giá trị, còn mỗi lá ở độ sâu n là một thứ tự. Duyệt cây bằng một path dùng chung và một cờ used cho mỗi giá trị: với mỗi giá trị chưa dùng, chọn giá trị đó, khám phá sâu thêm một tầng, rồi bỏ chọn. Bỏ chọn sẽ khôi phục chính xác trạng thái ban đầu, để vòng lặp thử giá trị tiếp theo từ cùng một nút.

Thứ tự sẽ tự nhiên đúng. Vòng lặp thử giá trị chưa dùng nhỏ nhất trước và hoàn tất mọi thứ tự có cùng tiền tố trước khi đổi tiền tố đó, nên [1, 2, ...] đứng trước [1, 3, ...], rồi đến [2, ...]. Đó là lý do bạn sắp xếp nums trước. Cây có khoảng e × n! nút, mỗi nút chạy một vòng lặp gồm n lượt: thời gian O(n × n!).

Thuật toán

Sắp xếp các giá trị và tạo một mảng used gồm n cờ false.
Viết explore(). Nếu path chứa n giá trị, hãy thêm một bản sao vào kết quả rồi trả về.
Nếu không, với mỗi chỉ số i từ 0 đến n-1 có giá trị chưa được dùng: đánh dấu giá trị đó là đã dùng và thêm values[i] (chọn), gọi explore() (khám phá), sau đó xóa giá trị đó và đánh dấu là chưa dùng (bỏ chọn).
Gọi explore() một lần rồi trả về kết quả.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Lỗi thường gặp và trường hợp biên

Lưu path thay vì lưu bản sao của nó. Tất cả n! mục đều trỏ đến cùng một danh sách, danh sách này sẽ trống sau khi quá trình duyệt kết thúc.
Chỉ hoàn tác một nửa lựa chọn. Nếu bạn xóa giá trị nhưng vẫn để used[i] được bật, giá trị đó sẽ không xuất hiện ở nhánh sau và bạn sẽ trả về ít hơn n! cách sắp xếp.
Không sắp xếp nums trước. Khi đó, các cách sắp xếp sẽ theo thứ tự đầu vào, nên [3, 1, 2] sẽ được liệt kê đầu tiên.
Dùng phương pháp hoán đổi (hoán đổi nums[start] với từng vị trí phía sau, gọi đệ quy, rồi hoán đổi lại) mà không sắp xếp lần cuối. Với [1, 2, 3], phương pháp này liệt kê [3, 2, 1] trước [3, 1, 2].
Tìm trong path để kiểm tra xem một giá trị đã được dùng chưa. Mỗi lần kiểm tra tốn n thời gian và cách này sẽ gặp lỗi khi các giá trị bị lặp; một cờ cho mỗi chỉ số chỉ tốn O(1).

Câu hỏi thường gặp3

Có bao nhiêu hoán vị của một danh sách gồm n phần tử phân biệt?

n!, đọc là giai thừa của n: có n lựa chọn cho vị trí đầu tiên, n-1 cho vị trí thứ hai, giảm dần đến một lựa chọn cho vị trí cuối cùng, rồi nhân các số đó với nhau. Ba giá trị tạo ra 6 cách sắp xếp, sáu giá trị tạo ra 720 cách, còn mười giá trị đã tạo ra 3,628,800 cách, đó là lý do các bài toán hoán vị giữ n ở mức nhỏ.

Độ phức tạp thời gian của việc tạo tất cả các hoán vị là bao nhiêu?

O(n × n!). Có n! thứ tự và cần n bước để ghi ra từng thứ tự, vì vậy không có phương pháp nào tốt hơn khi phải trả về tất cả các thứ tự đó. Thuật toán quay lui đạt giới hạn này và, ngoài phần đầu ra, cần O(n) không gian cho đường đi, các cờ đánh dấu đã dùng và đệ quy.

Làm thế nào để tạo các hoán vị khi đầu vào có phần tử trùng lặp?

Sắp xếp các giá trị và tại mỗi vị trí, bỏ qua một giá trị nếu nó bằng giá trị đứng trước và bản sao trước đó chưa được dùng: i > 0, values[i] == values[i-1] và !used[i-1]. Điều đó buộc các giá trị bằng nhau phải được xếp theo thứ tự ban đầu, nhờ vậy mỗi cách sắp xếp khác nhau chỉ được tạo ra một lần.

def permute(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 1, 2]

Đầu ra mong đợi

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]