Cara membuat permutasi dalam c ++ menggunakan STL untuk jumlah tempat yang lebih rendah dari total panjang

15

Saya punya c++ vectordengan std::pair<unsigned long, unsigned long>objek. Saya mencoba untuk menghasilkan permutasi objek menggunakan vektor std::next_permutation(). Namun, saya ingin permutasi dari ukuran yang diberikan, Anda tahu, mirip dengan permutationsfungsi di python di mana ukuran permutasi yang diharapkan ditentukan.

Pada dasarnya c++setara dengan

import itertools

list = [1,2,3,4,5,6,7]
for permutation in itertools.permutations(list, 3):
    print(permutation)

Demo Python

(1, 2, 3)                                                                                                                                                                            
(1, 2, 4)                                                                                                                                                                            
(1, 2, 5)                                                                                                                                                                            
(1, 2, 6)                                                                                                                                                                            
(1, 2, 7)                                                                                                                                                                            
(1, 3, 2)
(1, 3, 4)
..
(7, 5, 4)                                                                                                                                                                            
(7, 5, 6)                                                                                                                                                                            
(7, 6, 1)                                                                                                                                                                            
(7, 6, 2)                                                                                                                                                                            
(7, 6, 3)                                                                                                                                                                            
(7, 6, 4)                                                                                                                                                                            
(7, 6, 5)
python c++ permutation d4rk4ng31
sumber
Terima kasih @ Jarod42 untuk menambahkan demo python itu :)
d4rk4ng31
Harus melakukannya di sisi saya, karena saya tidak tahu hasil python, tetapi cukup yakin saya tahu bagaimana melakukannya di C ++.
Jarod42
Sebagai catatan tambahan, bagaimana Anda ingin menangani input duplikat (1, 1)? permutasi python menyediakan duplikat [(1, 1), (1, 1)], sedangkan std::next_permutationmenghindari duplikat (hanya {1, 1}).
Jarod42
Uh .. tidak. Tanpa duplikat
d4rk4ng31

Jawaban:

6

Anda mungkin menggunakan 2 loop:

  • Ambil setiap n-tuple
  • beralih pada permutasi n-tuple itu
template <typename F, typename T>
void permutation(F f, std::vector<T> v, std::size_t n)
{
    std::vector<bool> bs(v.size() - n, false);
    bs.resize(v.size(), true);
    std::sort(v.begin(), v.end());

    do {
        std::vector<T> sub;
        for (std::size_t i = 0; i != bs.size(); ++i) {
            if (bs[i]) {
                sub.push_back(v[i]);
            }
        }
        do {
            f(sub);
        }
        while (std::next_permutation(sub.begin(), sub.end()));
    } while (std::next_permutation(bs.begin(), bs.end()));
}

Demo

Jarod42
sumber
Apa yang akan menjadi kompleksitas waktu dari kode ini? Apakah akan O (places_required * n) untuk kasus rata-rata dan O (n ^ 2) untuk kasus terburuk? Saya juga menebak O (n) untuk kasus terbaik, yaitu satu tempat
d4rk4ng31
2
@ d4rk4ng31: Kami memang menemukan setiap permutasi hanya sekali. kompleksitasnya std::next_permutation"tidak jelas" karena ia menghitung swap (Linear). Ekstraksi sub vektor dapat ditingkatkan, tetapi saya tidak berpikir itu mengubah kompleksitas. Selain itu jumlah permutasi tergantung dari ukuran vektor, sehingga 2 parameter tidak independen.
Jarod42
Bukankah seharusnya begitu std::vector<T>& v?
LF
@ LF: Itu disengaja. Saya menganggap bahwa saya tidak perlu mengubah nilai penelepon (saya mengurutkan vsaat ini). Saya mungkin melewati referensi const, dan membuat salinan diurutkan sebagai gantinya.
Jarod42
@ Jarod42 Oh maaf, saya salah membaca kode. Ya, melewati nilai adalah hal yang benar untuk dilakukan di sini.
LF
4

Jika efisiensi bukanlah perhatian utama, kami dapat mengulangi semua permutasi dan melompati permutasi yang berbeda pada akhiran memilih hanya masing-masing (N - k)!. Misalnya, untuk N = 4, k = 2, kami memiliki permutasi:

12 34 <
12 43
13 24 <
13 42
14 23 <
14 32
21 34 <
21 43
23 14 <
23 41
24 13 <
24 31
...

di mana saya memasukkan ruang untuk kejelasan dan menandai (N-k)! = 2! = 2permutasi masing-masing <.

std::size_t fact(std::size_t n) {
    std::size_t f = 1;
    while (n > 0)
        f *= n--;
    return f;
}

template<class It, class Fn>
void generate_permutations(It first, It last, std::size_t k, Fn fn) {
    assert(std::is_sorted(first, last));

    const std::size_t size = static_cast<std::size_t>(last - first);
    assert(k <= size);

    const std::size_t m = fact(size - k);
    std::size_t i = 0;
    do {
        if (i++ == 0)
            fn(first, first + k);
        i %= m;
    }
    while (std::next_permutation(first, last));
}

int main() {
    std::vector<int> vec{1, 2, 3, 4};
    generate_permutations(vec.begin(), vec.end(), 2, [](auto first, auto last) {
        for (; first != last; ++first)
            std::cout << *first;
        std::cout << ' ';
    });
}

Keluaran:

12 13 14 21 23 24 31 32 34 41 42 43
Evg
sumber
3

Berikut ini adalah algoritma yang efisien yang tidak menggunakan std::next_permutationsecara langsung, tetapi memanfaatkan kuda kerja dari fungsi itu. Yaitu, std::swapdan std::reverse. Sebagai nilai tambah, ini dalam urutan leksikografis .

#include <iostream>
#include <vector>
#include <algorithm>

void nextPartialPerm(std::vector<int> &z, int n1, int m1) {

    int p1 = m1 + 1;

    while (p1 <= n1 && z[m1] >= z[p1])
        ++p1;

    if (p1 <= n1) {
        std::swap(z[p1], z[m1]);
    } else {
        std::reverse(z.begin() + m1 + 1, z.end());
        p1 = m1;

        while (z[p1 + 1] <= z[p1])
            --p1;

        int p2 = n1;

        while (z[p2] <= z[p1])
            --p2;

        std::swap(z[p1], z[p2]);
        std::reverse(z.begin() + p1 + 1, z.end());
    }
}

Dan kami menyebutnya:

int main() {
    std::vector<int> z = {1, 2, 3, 4, 5, 6, 7};
    int m = 3;
    int n = z.size();

    const int nMinusK = n - m;
    int numPerms = 1;

    for (int i = n; i > nMinusK; --i)
        numPerms *= i;

    --numPerms;

    for (int i = 0; i < numPerms; ++i) {
        for (int j = 0; j < m; ++j)
            std::cout << z[j] << ' ';

        std::cout << std::endl;
        nextPartialPerm(z, n - 1, m - 1);
    }

    // Print last permutation
    for (int j = 0; j < m; ++j)
            std::cout << z[j] << ' ';

    std::cout << std::endl;

    return 0;
}

Berikut hasilnya:

1 2 3 
1 2 4 
1 2 5 
1 2 6 
1 2 7
.
.
.
7 5 6 
7 6 1 
7 6 2 
7 6 3 
7 6 4 
7 6 5

Ini adalah kode runnable dari ideone

Joseph Wood
sumber
2
Anda bahkan bisa meniru lebih banyak lagi dengan tanda tanganbool nextPartialPermutation(It begin, It mid, It end)
Jarod42
2
Demo .
Jarod42
@ Jarod42, itu solusi yang sangat bagus. Anda harus menambahkannya sebagai jawaban ...
Joseph Wood
Gagasan awal saya adalah meningkatkan jawaban Anda, tetapi ok, ditambahkan.
Jarod42
3

Mengubah jawaban Joseph Wood dengan antarmuka iterator, Anda mungkin memiliki metode yang mirip dengan std::next_permutation:

template <typename IT>
bool next_partial_permutation(IT beg, IT mid, IT end) {
    if (beg == mid) { return false; }
    if (mid == end) { return std::next_permutation(beg, end); }

    auto p1 = mid;

    while (p1 != end && !(*(mid - 1) < *p1))
        ++p1;

    if (p1 != end) {
        std::swap(*p1, *(mid - 1));
        return true;
    } else {
        std::reverse(mid, end);
        auto p3 = std::make_reverse_iterator(mid);

        while (p3 != std::make_reverse_iterator(beg) && !(*p3 < *(p3 - 1)))
            ++p3;

        if (p3 == std::make_reverse_iterator(beg)) {
            std::reverse(beg, end);
            return false;
        }

        auto p2 = end - 1;

        while (!(*p3 < *p2))
            --p2;

        std::swap(*p3, *p2);
        std::reverse(p3.base(), end);
        return true;
    }
}

Demo

Jarod42
sumber
1

Ini solusi saya setelah beberapa pemikiran

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> job_list;
    std::set<std::vector<int>> permutations;
    for (unsigned long i = 0; i < 7; i++) {
        int job;
        std::cin >> job;
        job_list.push_back(job);
    }
    std::sort(job_list.begin(), job_list.end());
    std::vector<int> original_permutation = job_list;
    do {
        std::next_permutation(job_list.begin(), job_list.end());
        permutations.insert(std::vector<int>(job_list.begin(), job_list.begin() + 3));
    } while (job_list != original_permutation);

    for (auto& permutation : permutations) {
        for (auto& pair : permutation) {
            std::cout << pair << " ";
        }
        std::endl(std::cout);
    }

    return 0;
}

Silakan komentar pikiran Anda

d4rk4ng31
sumber
2
Tidak setara dengan milikku, itu lebih setara dengan jawaban Evg, (tapi Evg melewatkan duplikat lebih efisien) permutesebenarnya hanya bisa set.insert(vec);menghilangkan faktor besar.
Jarod42
Apa kompleksitas waktu sekarang?
d4rk4ng31
1
Saya akan mengatakan O(nb_total_perm * log(nb_res))(nb_total_perm yang sebagian besar factorial(job_list.size())dan nb_resukuran hasil:) permutations.size(), Jadi masih terlalu besar. (tapi sekarang Anda menangani input duplikat yang bertentangan dengan Evg)
Jarod42