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

15

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)
python c++ permutation d4rk4ng31
źródło
Dzięki @ Jarod42 za dodanie tej wersji demona python :)
d4rk4ng31
Musiałem to zrobić po mojej stronie, ponieważ nie znam wyniku w Pythonie, ale byłem całkiem pewien, że wiem, jak to zrobić w C ++.
Jarod42
Na marginesie, jak chcesz obsługiwać zduplikowane dane (1, 1)? permutacje Pythona zapewniają duplikaty [(1, 1), (1, 1)], ale std::next_permutationunikaj duplikatów (tylko {1, 1}).
Jarod42
O nie. Bez duplikatów
d4rk4ng31

Odpowiedzi:

6

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

Jarod42
źródło
Jaka będzie złożoność czasowa tego kodu? Czy będzie to O (miejsca_wymagane * n) dla przeciętnego przypadku i O (n ^ 2) dla najgorszego przypadku? Zgaduję również O (n) dla najlepszego przypadku, tj. Jedno miejsce
d4rk4ng31
2
@ d4rk4ng31: Rzeczywiście, każdą permutację napotykamy tylko raz. złożoność std::next_permutationjest „niejasna”, ponieważ liczy się zamiana (liniowa). Ekstrakcję wektora podrzędnego można poprawić, ale nie sądzę, aby zmieniała złożoność. Ponadto liczba permutacji zależy od wielkości wektora, więc parametr 2 nie jest niezależny.
Jarod42
Czy nie powinno tak być std::vector<T>& v?
LF,
@LF: To celowo. Uważam, że nie muszę zmieniać wartości dzwoniącego (sortuję vobecnie). Mógłbym przejść przez const referen i zamiast tego utworzyć posortowaną kopię w treści.
Jarod42
@ Jarod42 Och, przepraszam, całkowicie źle odczytałem kod. Tak, przekazywanie wartości jest właściwe.
LF,
4

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
Evg
źródło
3

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

Joseph Wood
źródło
2
Możesz nawet naśladować jeszcze więcej dzięki podpisowibool nextPartialPermutation(It begin, It mid, It end)
Jarod42
2
Demo .
Jarod42
@ Jarod42, to naprawdę fajne rozwiązanie. Powinieneś dodać to jako odpowiedź ...
Joseph Wood,
Mój początkowy pomysł polegał na poprawieniu odpowiedzi, ale dobrze, dodał.
Jarod42
3

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

Jarod42
źródło
1

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

d4rk4ng31
źródło
2
Nie jest równoważny z moim, jest bardziej równoważny z odpowiedzią Evga (ale Evg bardziej skutecznie pomija duplikaty). permutemoże w rzeczywistości tylko set.insert(vec);usunąć duży czynnik.
Jarod42
Jaka jest teraz złożoność czasu?
d4rk4ng31
1
Powiedziałbym O(nb_total_perm * log(nb_res))( nb_total_permktóra jest głównie factorial(job_list.size())i nb_reswielkość wyniku permutations.size():), więc wciąż za duża. (ale teraz radzisz sobie z duplikatami danych sprzecznymi z Evgiem)
Jarod42