C++全排列和组合

淡淡的烟草味﹌ 2021-11-02 08:44 368阅读 0赞

全排列的写法：先确定第一个元素，后面的元素逐渐交换。

#include <iostream>
    using namespace std;
    
    void Perm(int start, int end, int a[]){
        //得到全排列的一种情况，输出结果
        if (start == end){
            for (int i = 0; i < end; i++)
                cout << a[i] << ' ';
            cout << endl;
            return;
        }
        for (int i = start; i < end; i++){
            swap(a[start], a[i]);      //交换
            Perm(start + 1, end, a);   //分解为子问题a[start+1,...,end-1]的全排列
            swap(a[i], a[start]);      //回溯
        }
    }
    int main() {
        int i, n, a[10];
        while (cin >> n, n) {
            for (i = 0; i < n; i++)
            {
                a[i] = i + 1;
            }
            Perm(0, n, a);
        }
        return 0;
    }

全排列模板写法：

#include<iostream>
    #include<array>
    #include<algorithm>
    using namespace  std;
    
    int main()
    {
        std::array<int, 3> A = {1,2,3};
        do {
            for (auto i : A)
                cout << i << " ";
            cout << std::endl;
        } while (next_permutation(A.begin(), A.end()));
    }

c++  组合：

#include <iostream>
    using namespace std;
    
    void dfs(int pos, int cnt, int n, int k, int a[],bool visited[]) {
        //已标记了k个数，输出结果
        if (cnt == k){
            for (int i = 0; i < n; i++)
                if (visited[i]) cout << a[i] << ' ';
            cout << endl;
            return;
        }
        //处理到最后一个数，直接返回
        if (pos == n) return;
        
        //如果a[pos]没有被选中
        if (!visited[pos]) {
            //选中a[pos]
            visited[pos] = true;
            //处理在子串a[pos+1, n-1]中取出k-1个数的子问题
            dfs(pos + 1, cnt + 1, n, k, a,visited);
            //回溯
            visited[pos] = false;   
        }
        //处理在子串a[pos+1, n-1]中取出k个数的问题
        dfs(pos + 1, cnt, n, k, a, visited);
    }
    int main() {
        int i, n, k;
        while (cin >> n >> k, n || k) 
        {
            int *a = new int[n];
            bool *visited = new bool[n];
            for (i = 0; i < n; i++)
            {
                a[i] = i + 1;
                visited[i] = false;
            }
            dfs(0, 0, n, k, a, visited);
            delete[] a;
            delete[] visited;
        }
      //  getchar();
        return 0;
    }

转载：[https://segmentfault.com/a/1190000002486075][https_segmentfault.com_a_1190000002486075]

[https://blog.csdn.net/hf19931101/article/details/79452799][https_blog.csdn.net_hf19931101_article_details_79452799]

[https_segmentfault.com_a_1190000002486075]: https://segmentfault.com/a/1190000002486075
[https_blog.csdn.net_hf19931101_article_details_79452799]: https://blog.csdn.net/hf19931101/article/details/79452799