Hỏi thuật toán: Sinh chỉnh hợp không lập chập k của n

Cho em hỏi là nếu sử dụng phương pháp sinh thì để sinh được chỉnh hợp không lập chập k của n. Cần phải thiết kế thuật toán như thế nào ạ ?

Em đang học C++ nếu ai có code demo bằng ngôn ngữ này thì tốt ạ. Không thi ngôn ngữ khác em vẫn đọc được. Ngoài ra nếu không có thời gian thì có thể cho em xin cái thuật toán thôi ạ.

Giờ cũng không có code, search google thì bạn tự search. Mình làm bằng cách sử dụng cây n- phân
Giả sử có 4 số 1, 2, 3, 4 thì các cây con sẽ như sau:

                                                   null
                     1                            2                            3                          4
             2       3       4            1       3       4            1       2       4          1       2       3
           3   4   2   4   2   3    (mấy cây sau tương tự)
           4   3   4   2   3   2
4 Likes

Nhưng mà mình muốn dùng thử phương pháp sinh ấy. Với lại cho mình xin keyword search.

void PermGenerator(int n, int k)
{
    std::vector<int> d{n};
    std::iota(d.begin(), d.end(), 1);
    std::cout << "These are the Possible Permutations: " << std::endl;
    do
    {
        for (int i = 0; i < k; i++)
            std::cout << d[i] << " ";
        std::cout << std::endl;
        std::reverse(d.begin()+k, d.end());
    } while (std::next_permutation(d.begin(), d.end()));
}

Source: StackOverflow

4 Likes

Làm bài nhị phân trước rồi sẽ giải được bài này :smiley:

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?