총 길이보다 작은 장소 수에 대해 STL을 사용하여 C ++에서 순열을 만드는 방법

나는이 c++ vector와 std::pair<unsigned long, unsigned long>객체. 를 사용하여 벡터 객체의 순열을 생성하려고합니다 std::next_permutation(). 그러나 permutations기대되는 반환 순열의 크기가 지정된 파이썬 의 함수 와 유사하게 순열의 크기를 지정 하고 싶습니다 .

기본적으로, c++동등한

import itertools

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

파이썬 데모

답변

2 개의 루프를 사용할 수 있습니다.

각 n 튜플을 가져 가라.
해당 n- 튜플의 순열을 반복

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

데모

답변

효율성이 주요 관심사가 아닌 경우 모든 순열을 반복하고 접미사마다 다른 순열마다 다른 순열을 건너 뛸 수 있습니다 (N - k)!. 예를 들어의 N = 4, k = 2경우 순열이 있습니다.

여기서 명확성을 위해 공백을 삽입하고 각 (N-k)! = 2! = 2-nd 순열을 로 표시 했습니다 <.

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

산출:

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

답변

다음은 std::next_permutation직접 사용하지 않지만 해당 기능의 작동 말을 사용 하는 효율적인 알고리즘입니다 . 즉, std::swap하고 std::reverse. 또한, 사전 식 순서 입니다.

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

그리고 그것을 호출하면 다음과 같습니다.

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

출력은 다음과 같습니다.

이데온의 실행 가능한 코드는 다음과 같습니다.

답변

반복자 인터페이스를 사용하여 Joseph Wood 답변을 돌리면 다음과 비슷한 방법이 있습니다 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;
    }
}

데모

답변

이것은 몇 가지 생각 후 내 솔루션입니다

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

의견을 말 해주세요

IT HOW

무엇이는 물어보세요

총 길이보다 작은 장소 수에 대해 STL을 사용하여 C ++에서 순열을 만드는 방법

답변

답변

답변

답변

답변

답변