나는이 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)
(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)
답변
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경우 순열이 있습니다.
12 34 <
12 43
13 24 <
13 42
14 23 <
14 32
21 34 <
21 43
23 14 <
23 41
24 13 <
24 31
...
여기서 명확성을 위해 공백을 삽입하고 각 (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;
}
출력은 다음과 같습니다.
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
이데온의 실행 가능한 코드는 다음과 같습니다.
답변
반복자 인터페이스를 사용하여 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;
}의견을 말 해주세요