Thuật toán C++ cho N! orderings

Question

Tôi có một danh sách N mục và tôi tự hỏi làm thế nào tôi có thể lặp qua danh sách để có được mọi kết hợp. Không có gấp đôi, vì vậy tôi cần phải có tất cả N! trật tự. Bộ nhớ thêm là không có vấn đề, tôi đang cố gắng để nghĩ về thuật toán đơn giản nhất nhưng tôi đang gặp rắc rối.

Answer 1

Xem std::next_permutation    

Answer 2

C++ STL có next_permutation cho mục đích này.

Answer 3

Mở rộng trên câu trả lời của người khác, đây là một ví dụ về std :: next_permutation chuyển thể từ cplusplus.com

#include <iostream> 
#include <algorithm> 
using namespace std; 

void outputArray(int* array, int size) 
{ 
    for (int i = 0; i < size; ++i) { cout << array[i] << " "; } 
} 

int main() 
{ 
    int myints[] = { 1, 2, 3, 4, 5 }; 
    const int size = sizeof(myints); 

    cout << "The 5! possible permutations with 5 elements:\n"; 

    sort (myints, myints + size); 

    bool hasMorePermutations = true; 
    do 
    { 
    outputArray(myints, size); 
    hasMorePermutations = next_permutation(myints, myints + size); 
    } 
    while (hasMorePermutations); 

    return 0; 
} 

Answer 4

thuật toán đơn giản sử dụng Đệ quy:

giả

getPermutations(CurItemList , CurPermList) 

if CurItemList.isempty() 
    return CurPermList 
else 
    Permutations = {} 

    for i = 1 to CurItemList.size() 
     CurPermList.addLast(CurItemList.get(i)) 

     NextItemList = CurItemList.copy() 
     NextItemList.remove(i) 

     Permutations.add(getPermutations(NextItemList, CurPermList)) 

     CurPermList.removeLast() 


return Permutations 

// To make it look better 
Permutations(ItemList) 
    return getPermutations(ItemList, {}) 

tôi didnt kiểm tra nó, nhưng nên làm việc. Có lẽ nó không phải là cách thông minh nhất để làm điều đó, nhưng nó là một cách dễ dàng. Nếu có điều gì sai, vui lòng cho tôi biết!

Answer 5

Thử xây dựng tập hợp các kết hợp đệ quy với số lượng cố định các thành phần có thể có. Tập hợp tất cả các kết hợp có thể sẽ là liên kết của tập hợp các kết hợp của 1 phần tử, 2 phần tử, ... tối đa N phần tử.

Sau đó, bạn có thể tấn công từng kết hợp có kích thước cố định riêng lẻ.