logo标签列表

如何使用STL在C++中创建一个长度小于总长度的排列

pythonc++permutation
19

我有一个包含std::pair<unsigned long, unsigned long>对象的。我尝试使用std::next_permutation()生成向量对象的排列组合。然而，我希望这些排列组合的大小是固定的，就像python中的permutations函数一样，可以指定期望返回的排列组合的大小。

基本上，这就是的等价物。

import itertools

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

Python演示

(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, 1)？Python 的排列函数提供了重复的 [(1, 1), (1, 1)]，而 std::next_permutation 则避免了重复（只有 {1, 1}）。 - Jarod42
5个回答
6
你可以使用两个循环：
  • 遍历每一个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()));
}

演示

这段代码的时间复杂度会是多少？平均情况下会是O(places_required*n)，最坏情况下会是O(n^2)吗？我猜最好情况下会是O(n)，即只有一个地方。 - kesarling He-Him
2
@d4rk4ng31：我们确实只遇到每个排列一次。std::next_permutation的复杂度是“不确定”的，因为它计算了交换（线性）。子向量的提取可以改进，但我认为它不会改变复杂度。此外，排列的数量取决于向量大小，因此这两个参数不是独立的。 - Jarod42
那不应该是 std::vector<T>& v 吗？ - L. F.
@L.F.：这是有意的。我认为我不必改变调用者的值（我目前正在对v进行排序）。我可以通过const引用传递，并在函数体内创建一个已排序的副本。 - Jarod42
@Jarod42 对不起，我完全误读了代码。是的，在这里传递值是正确的做法。 - L. F.
4
如果效率不是主要考虑因素，我们可以遍历所有排列，并跳过那些在后缀上有差异的排列，只选择每个 (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次排列。

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
3

这里有一个高效的算法，它不直接使用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

这里是来自ideone的可运行代码：

2
你甚至可以使用签名 bool nextPartialPermutation(It begin, It mid, It end) 来模拟更多的操作。 - Jarod42
@Jarod42，这是一个非常好的解决方案。你应该将其添加为答案... - Joseph Wood
我的初衷是为了改进你的回答，但好吧，已经添加了。 - Jarod42
3

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

演示

0
这是我经过一番思考后得出的解决方案。
#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;
}

请在下方留下您的想法。
2
与我的解答不太相同，更接近于Evg的解答（但Evg跳过重复元素的效率更高）。实际上，permute只需要set.insert(vec);，这将大大减少时间复杂度。 - Jarod42
1
我会说 O(nb_total_perm * log(nb_res)) (nb_total_perm 大多是 factorial(job_list.size())，而 nb_res 是结果的大小：permutations.size())，所以仍然太大了。（但现在你处理重复输入与 Evg 相反） - Jarod42
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接