19

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) 
1
  • 1
    As a side note, how do you want to handle duplicate inputs as (1, 1)? python permutations provides duplicated [(1, 1), (1, 1)], whereas std::next_permutation avoid duplicates (only {1, 1}).
    – Jarod42
    Apr 23, 2020 at 17:53

5 Answers 5

6

You might use 2 loops:

  • Take each n-tuple
  • iterate over permutations of that n-tuple
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()));
}

Demo

5
  • What will be the time complexity of this code? Will it be O(places_required*n) for average case and O(n^2) for worst case? I am also guessing O(n) for best case, i.e. one place Apr 23, 2020 at 17:10
  • 2
    @d4rk4ng31: We indeed encounter each permutation only once. complexity of std::next_permutation is "unclear" as it counts swap (Linear). Extraction of the sub vector can be improved, but I don't think it change complexity. In addition number of permutation depends of vector size, so the 2 parameter are not independent.
    – Jarod42
    Apr 23, 2020 at 17:23
  • Shouldn't that be std::vector<T>& v?
    – L. F.
    Apr 25, 2020 at 3:24
  • @L.F.: It is on purpose. I consider that I don't have to change value of caller (I sort v currently). I might pass by const reference, and create a sorted copy in body instead.
    – Jarod42
    Apr 25, 2020 at 6:12
  • @Jarod42 Oh sorry, I completely misread the code. Yeah, passing by value is the right thing to do here.
    – L. F.
    Apr 25, 2020 at 7:28
4

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
0
3

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

3
  • 2
    You could even mimic even more with signature bool nextPartialPermutation(It begin, It mid, It end)
    – Jarod42
    Apr 23, 2020 at 18:31
  • @Jarod42, that is a really nice solution. You should add it as an answer... Apr 23, 2020 at 19:58
  • My initial idea was to improve your answer, but ok, added.
    – Jarod42
    Apr 24, 2020 at 6:06
3

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

0

This is my solution after some thought

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

Please comment your thoughts

2
  • 2
    Not equivalent to mine, it is more equivalent to Evg's answer, (but Evg skips duplicates more efficiently). permute could in fact only be set.insert(vec); removing a big factor.
    – Jarod42
    Apr 23, 2020 at 18:27
  • 1
    I would say O(nb_total_perm * log(nb_res)) (nb_total_perm which is mostly factorial(job_list.size()) and nb_res size of result:permutations.size()), So still too big. (but now you handle duplicates input contrary to Evg)
    – Jarod42
    Apr 23, 2020 at 19:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.