Jak utworzyć permutację w c ++ przy użyciu STL dla liczby miejsc mniejszych niż całkowita długość

Mam c++ vectorz std::pair<unsigned long, unsigned long>przedmiotami. Próbuję wygenerować permutacje obiektów wektora za pomocą std::next_permutation(). Jednak chcę, aby permutacje miały określony rozmiar, wiesz, podobny do permutationsfunkcji w pythonie, w której określono rozmiar oczekiwanej zwróconej permutacji.

Zasadniczo c++odpowiednik

import itertools

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

Demo Pythona

(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) 

Możesz użyć 2 pętli:

• Weź każdą n-krotkę
• iteruj po permutacjach tego n-krotki

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()));
}

Próbny

Jeśli wydajność nie jest najważniejsza, możemy iterować po wszystkich permutacjach i pomijać te, które różnią się sufiksem, wybierając tylko każdą z (N - k)!nich. Na przykład dla N = 4, k = 2mamy permutacje:

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

gdzie wstawiłem spację dla jasności i oznaczyłem każdą i (N-k)! = 2! = 2ostatnią permutację za pomocą <.

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 << ' ';
    });
}

Wynik:

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

Oto skuteczny algorytm, który nie używa std::next_permutationbezpośrednio, ale wykorzystuje konie robocze tej funkcji. To znaczy std::swapi std::reverse. Na plus jest w porządku leksykograficznym .

#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());
    }
}

I nazywając to mamy:

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;
}

Oto wynik:

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

Oto kod, który można uruchomić z ideone

Włączając odpowiedź Josepha Wooda z interfejsem iteratora, możesz mieć metodę podobną do 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;
    }
}

Próbny

To jest moje rozwiązanie po namyśle

#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;
}

Skomentuj swoje przemyślenia