C++ 排列组合

在算法和实际编程中，排列和组合是非常常见的问题。C++ STL提供了一些实用的函数来帮助我们处理这类问题，而不必手动实现复杂的排列组合算法。本文将详细介绍C++中的排列组合相关功能，并通过实例讲解其应用。

排列与组合基础知识

在开始之前，让我们简单回顾一下排列和组合的数学概念：

排列：从n个不同元素中取出m个元素的所有可能排列方式，顺序很重要。数学上表示为 $P(n,m) = \frac{n!}{(n-m)!}$
组合：从n个不同元素中取出m个元素的所有可能组合方式，顺序不重要。数学上表示为 $C(n,m) = \frac{n!}{m!(n-m)!}$

STL中的排列函数

C++ STL中提供了两个主要函数用于生成排列：

std::next_permutation - 生成下一个排列
std::prev_permutation - 生成上一个排列

这两个函数定义在<algorithm>头文件中。

next_permutation

next_permutation函数将给定序列重新排列成字典序中的下一个更大的排列。

函数原型

cpp
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

返回值

如果能生成下一个排列，函数返回true
如果当前排列已经是最后一个排列（字典序最大），函数返回false并将序列重置为字典序最小的排列

实例代码

cpp
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3};
    
    do {
        // 输出当前排列
        for (int num : nums) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(nums.begin(), nums.end()));
    
    return 0;
}

输出：

备注

next_permutation会按照字典序（即按照元素从小到大的顺序）生成排列。为了生成所有可能的排列，需要先确保序列已按升序排序。

prev_permutation

prev_permutation函数与next_permutation相反，它将给定序列重新排列成字典序中的上一个更小的排列。

函数原型

cpp
template <class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template <class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

实例代码

cpp
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> nums = {3, 2, 1};  // 开始于字典序最大的排列
    
    do {
        // 输出当前排列
        for (int num : nums) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } while (std::prev_permutation(nums.begin(), nums.end()));
    
    return 0;
}

输出：

生成组合

虽然STL没有直接提供组合生成函数，但我们可以使用next_permutation配合一些技巧来实现组合的生成。

使用二进制掩码生成组合

一种常见方法是使用二进制掩码：

cpp
#include <iostream>
#include <vector>
#include <algorithm>

void printCombinations(const std::vector<int>& elements, int r) {
    int n = elements.size();
    std::vector<bool> mask(n, false);
    
    // 设置前r个位置为true
    for (int i = 0; i < r; i++) {
        mask[i] = true;
    }
    
    do {
        // 输出当前组合
        for (int i = 0; i < n; i++) {
            if (mask[i]) {
                std::cout << elements[i] << " ";
            }
        }
        std::cout << std::endl;
    } while (std::prev_permutation(mask.begin(), mask.end()));
    // 使用prev_permutation因为我们需要从11100...排列开始
}

int main() {
    std::vector<int> elements = {1, 2, 3, 4, 5};
    int r = 3;  // 要选取的元素个数
    
    std::cout << "从 {1, 2, 3, 4, 5} 中选择3个元素的所有组合：" << std::endl;
    printCombinations(elements, r);
    
    return 0;
}

输出：

排列组合的实际应用场景

1. 全排列问题

当我们需要生成所有可能的排列顺序时，next_permutation非常有用。例如，解决旅行商问题（TSP）的暴力方法：

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

// 计算给定城市顺序的总路程
int calculateDistance(const std::vector<std::vector<int>>& distances, const std::vector<int>& path) {
    int totalDistance = 0;
    for (int i = 0; i < path.size() - 1; i++) {
        totalDistance += distances[path[i]][path[i + 1]];
    }
    // 从最后一个城市返回起点
    totalDistance += distances[path.back()][path[0]];
    return totalDistance;
}

// 暴力解决TSP
int solveTSP(const std::vector<std::vector<int>>& distances) {
    int n = distances.size();
    std::vector<int> cities(n);
    for (int i = 0; i < n; i++) {
        cities[i] = i;
    }
    
    int minDistance = INT_MAX;
    
    // 尝试所有可能的路径
    do {
        int currentDistance = calculateDistance(distances, cities);
        minDistance = std::min(minDistance, currentDistance);
    } while (std::next_permutation(cities.begin(), cities.end()));
    
    return minDistance;
}

int main() {
    // 城市之间的距离矩阵
    std::vector<std::vector<int>> distances = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    
    int shortestPath = solveTSP(distances);
    std::cout << "最短路径长度: " << shortestPath << std::endl;
    
    return 0;
}

警告

全排列算法的时间复杂度为O(n!)，对于大规模问题（如n>10）会变得非常慢。

2. 子集生成

使用组合生成算法可以帮助我们生成所有可能的子集：

cpp
#include <iostream>
#include <vector>
#include <algorithm>

void generateSubsets(const std::vector<int>& set) {
    int n = set.size();
    
    // 生成从空集到全集的所有子集
    for (int r = 0; r <= n; r++) {
        std::vector<bool> mask(n, false);
        
        // 设置前r个位置为true
        for (int i = 0; i < r; i++) {
            mask[i] = true;
        }
        
        do {
            std::cout << "{ ";
            for (int i = 0; i < n; i++) {
                if (mask[i]) {
                    std::cout << set[i] << " ";
                }
            }
            std::cout << "}" << std::endl;
        } while (std::prev_permutation(mask.begin(), mask.end()));
    }
}

int main() {
    std::vector<int> set = {1, 2, 3};
    std::cout << "集合 {1, 2, 3} 的所有子集：" << std::endl;
    generateSubsets(set);
    
    return 0;
}

自定义排序的排列

next_permutation和prev_permutation都接受自定义比较函数，这使得我们可以按照自己的规则生成排列：

cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

struct Person {
    std::string name;
    int age;
};

int main() {
    std::vector<Person> people = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 20}
    };
    
    // 按年龄降序排序
    std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age > b.age;
    });
    
    // 生成所有可能的排列（按年龄降序的字典序）
    do {
        for (const auto& person : people) {
            std::cout << person.name << " (" << person.age << ") ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(people.begin(), people.end(), [](const Person& a, const Person& b) {
        return a.age > b.age;
    }));
    
    return 0;
}

优化和注意事项

内存使用：排列组合算法在处理大量数据时会消耗大量内存，需要注意内存限制。
时间复杂度：
- 全排列：O(n!)
- 组合：O(C(n,k))
递归替代方案：对于特定问题，有时递归实现的回溯算法可能比使用STL函数更高效。

提示

在处理大规模排列组合问题时，考虑使用迭代生成而不是一次性生成所有可能性，以节省内存和提高效率。

总结

C++ STL中的排列组合函数为我们提供了强大而便捷的工具，能够高效地生成各种排列和组合。主要记住：

std::next_permutation用于生成字典序中的下一个排列
std::prev_permutation用于生成字典序中的上一个排列
虽然没有直接的组合生成函数，但可以通过二进制掩码结合排列函数实现

这些函数在解决实际问题时非常有用，从简单的全排列到复杂的组合优化问题都能发挥重要作用。

练习题

实现一个函数，打印字符串的所有可能排列（不包括重复的）。
使用next_permutation解决"下一个排列"问题：给定一个整数数组，找出字典序中的下一个排列。
实现一个函数，生成从1到n的所有可能的k个数的组合。
编写一个程序，列出n个人中选取k个人的所有可能委员会组合。

扩展资源

C++ Reference: next_permutation
C++ Reference: prev_permutation
《算法导论》中关于排列组合的章节
《Effective STL》by Scott Meyers

掌握了这些技术，你将能够有效地解决许多涉及排列组合的编程问题！

排列与组合基础知识​

STL中的排列函数​

next_permutation​

函数原型​

返回值​

实例代码​

prev_permutation​

函数原型​

实例代码​

生成组合​

使用二进制掩码生成组合​

排列组合的实际应用场景​

1. 全排列问题​

2. 子集生成​

自定义排序的排列​

优化和注意事项​

总结​

练习题​

扩展资源​

排列与组合基础知识

STL中的排列函数

next_permutation

函数原型

返回值

实例代码

prev_permutation

函数原型

实例代码

生成组合

使用二进制掩码生成组合

排列组合的实际应用场景

1. 全排列问题

2. 子集生成

自定义排序的排列

优化和注意事项

总结

练习题

扩展资源