Menu
I have a c++ vector with std::pair<unsigned long, unsigned long> objects. I am trying to generate permutations of the objects of the vector using std::next_permutation(). However, I want the permutations to be of a given size, you know, similar to the permutations function in python where the size of the expected returned permutation is specified.
Basically, the c++ equivalent of
import itertools
list = [1,2,3,4,5,6,7]
for permutation in itertools.permutations(list, 3):
print(permutation)
Python Demo
(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)
523
You take first element of an array (k=0) and exchange it with any element (i) of the array. Then you recursively apply permutation on array starting with second element. This way you get all permutations starting with i-th element.
Algorithm using C++ STL We can generate all permutations of an array by making use of the STL function next_permutation. A call of next_permutation returns the next lexicographically smallest permutation. If the sequence is lexicographically largest, the function returns false.
std::next_permutation It is used to rearrange the elements in the range [first, last) into the next lexicographically greater permutation. A permutation is each one of the N! possible arrangements the elements can take (where N is the number of elements in the range).
Turning Joseph Wood answer with iterator interface, you might have a method similar to 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
173
If efficiency is not the primary concern, we can iterate over all permutations and skip those that differ on a suffix selecting only each (N - k)!-th one. For example, for N = 4, k = 2, we have permutations:
12 34 <
12 43
13 24 <
13 42
14 23 <
14 32
21 34 <
21 43
23 14 <
23 41
24 13 <
24 31
...
where I inserted a space for clarity and marked each (N-k)! = 2! = 2-nd permutation with <.
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 << ' ';
});
}
Output:
12 13 14 21 23 24 31 32 34 41 42 43
Here is a an efficient algorithm that doesn't use std::next_permutation directly, but makes use of the work horses of that function. That is, std::swap and std::reverse. As a plus, it's in lexicographical order.
#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());
}
}
And calling it we have:
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;
}
Here is the output:
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
Here is runnable code from ideone
41
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
