How to create a permutation in c++ using STL for number of places lower than the total length

Question

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

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 '20 at 17:53

score 6 · Accepted Answer · answered Apr 23 '20 at 17:03

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

answered Apr 23 '20 at 17:03

Jarod42

203,559
14
181
302

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 – kesarling He-Him Apr 23 '20 at 17:10
2

@d4rk4ng31: We indeed encounter each permutation only once. complexity of [`std::next_permutation`](https://en.cppreference.com/w/cpp/algorithm/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 '20 at 17:23
Shouldn't that be `std::vector& v`? – L. F. Apr 25 '20 at 03: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 '20 at 06:12
@Jarod42 Oh sorry, I completely misread the code. Yeah, passing by value is the right thing to do here. – L. F. Apr 25 '20 at 07:28

Evg · Answer 2 · 2020-04-23T17:26:19.217

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:

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

score 3 · Answer 3 · answered Apr 23 '20 at 18:08

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:

Here is runnable code from ideone

You could even mimic even more with signature `bool nextPartialPermutation(It begin, It mid, It end)` — Jarod42, Apr 23 '20 at 18:31
@Jarod42, that is a really nice solution. You should add it as an answer... — Joseph Wood, Apr 23 '20 at 19:58

score 3 · Answer 4 · answered Apr 24 '20 at 06:04

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

kesarling He-Him · Answer 5 · 2020-04-23T18:33:15.397

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

edited Apr 23 '20 at 18:33

answered Apr 23 '20 at 18:15

kesarling He-Him

1,944
3
14
39

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 '20 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 '20 at 19:27

How to create a permutation in c++ using STL for number of places lower than the total length

5 Answers5

Linked