美文网首页
生成排列、组合数

生成排列、组合数

作者: ae9e2d371f0c | 来源:发表于2017-04-08 01:52 被阅读138次

排列组合数

组合数

生成组合数
举例:
比如有一个数组int arr[3] = {1,4,8},生成组合数就是要生成{1},{4},{8},{1,4},{1,8},{4,8},{1,4,8}
思路:
要生成{1,4,8}这个数组的组合数,需要依赖{1,4}的组合数。如果记{1,4}的生成的组合数集合为A,那么生成{1,4,8}的组合数的方式为拷贝一份A序列集合得到B序列集合,对B序列集合中所有的序列,都加上一个8,那么{1,4,8}的序列结合就可以用A+B+{8}的方式表示。{1,4}也是类似的过程。由{1}加上{1,4}以及{4}构成。
实现:

class Solution {
public:
    //arr 数组指针
    //len 数组长度
    //返回二维数组
    vector<vector<int> > getAllCombination(int arr[], int len) {
        vector<vector<int> > combinations;
        vector<int> a;
        a.push_back(arr[0]);
        combinations.push_back(a);
        for (int i = 1; i < len; i++) {
            unsigned long l = combinations.size();
            for (unsigned long j = 0; j < l; j++) {
                vector<int> temp = combinations[j];
                temp.push_back(arr[i]);
                combinations.push_back(temp);
            }
            vector<int> b;
            b.push_back(arr[i]);
            combinations.push_back(b);
        }
        return combinations;
    }
};
int main() {
    int arr[] = {1, 4, 8};
    Solution s = Solution();
    vector<vector<int> > c = s.getAllCombination(arr,3);
    for(int i = 0;i<c.size();i++){
        for(int j = 0;j<c[i].size();j++){
            cout << c[i][j] << "\t";
        }
        cout <<endl;
    }
}

排列数

生成组合数
举例:
生成排列数的过程,同样是上面的列子{1,4,8}对应的组合数序列就是{1},{4},{8},{1,4},{4,1},{1,8},{8,1},{4,8},{8,4},{1,4,8},{1,8,4},{4,1,8},{4,8,1},{8,1,4},{8,4,1}一共是15种。
思路:
生成排列数序列与组合数序列最大的不同就是排列数序列是有序的,而组合数序列是无序的,那么排列数序列的生成就需要组合数序列、以及对这些组合数序列进行全排序。全排序就是对于{1,4}要生成{1,4}{4,1}.组合数上面讲过了,下面讲下如何根据给定集合生成全排序。
生成全排序:
考虑已经有序列abc,那么生成全排序如下:
step1:对序列abc,通过将a与b、c交换得到baccba.或者交换b和c得到acb
step2:对bac又可以交换a与c得到bca;对cba交换b与a可以得到cab
这样我们就可以得到abc的全排序。这样一个过程就是不断交换元素,但是需要控制好交换的开始坐标以及结束条件。
全序列实现:

class Solution{
public:
    vector<vector<int> >p;
    void permutation(int *arr,int start,int len){
        if(start == len-1){
            //根据当前序列构造序列
            vector<int> temp;
            for(int i = 0;i<len;i++){
                temp.push_back(arr[i]);
            }
            p.push_back(temp);
        }
        for(int i = start;i<len;i++){
            swap(arr[start],arr[i]);
            permutation(arr,start+1,len);
            swap(arr[i],arr[start]);
        }
    }
};

int main(){
    int arr[] = {1,4,8};
    Solution s = Solution();
    s.permutation(arr,0,3);//s.p保存着全序列
    for(int i = 0;i<s.p.size();i++){
        for(int j = 0;j<s.p[i].size();j++){
            cout << s.p[i][j] << "\t";
        }
        cout << endl;
    }
}

排列数生成:
最后我们来生成排列数序列。就两步,首选生成组合数序列,其次对于每个组合数序列,利用上面的全序列的生成过程生成每个组合序列的全序列,把所有的全序列合在一起,就可以得到我们的排列数序列。

实现:

#include <iostream>
#include <vector>

using namespace std;
class Solution{
public:
    //构造组合数
    vector<vector<int> > getAllCombination(int arr[],int len){
        vector<vector<int> >ret;
        vector<int>a;
        a.push_back(arr[0]);
        ret.push_back(a);
        for(int i = 1;i<len;i++){
            unsigned long l = ret.size();
            for(int j = 0;j<l;j++){
                vector<int> temp = ret[j];
                temp.push_back(arr[i]);
                ret.push_back(temp);
            }
            vector<int>b;
            b.push_back(arr[i]);
            ret.push_back(b);
        }
        return ret;
    }
    vector<vector<int> >p;
    //生成全序列
    void getPermutation(int arr[], int start, int len){
        if(start == len-1){
            //显示、保存全序列
            vector<int> temp;
            for(int i = 0;i<len;i++){
                temp.push_back(arr[i]);
            }
            p.push_back(temp);
        }
        for(int i = start;i<len;i++){
            swap(arr[start],arr[i]);
            getPermutation(arr,start+1,len);
            swap(arr[start],arr[i]);
        }
    }

    vector<vector<int> > getAllPermutation(int arr[], int len){
        vector<vector<int> > ret;
        vector<vector<int> > combinations = getAllCombination(arr,len);
        for(int i = 0;i<combinations.size();i++){
            int tempArr[combinations[i].size()];
            for(int j= 0;j<combinations[i].size();j++){
                tempArr[j] = combinations[i][j];
            }
            p.clear();
            getPermutation(tempArr,0,combinations[i].size());
            //ret.insert(ret.end(),p.begin(),p.end());
            for(int j = 0;j<p.size();j++){
                ret.push_back(p[j]);
            }
        }
        return ret;
    }
};

int main(){
    int arr[] = {1,4,8};

    Solution s = Solution();
    vector<vector<int> > r = s.getAllPermutation(arr,3);
    for(int i = 0;i<r.size();i++){
        for(int j= 0;j<r[i].size();j++){
            cout << r[i][j] <<  "\t";
        }
        cout << endl;
    }

    return 0;
}

参考

http://wuchong.me/blog/2014/07/28/permutation-and-combination-realize/

相关文章

  • 生成排列、组合数

    排列组合数 组合数 生成组合数举例:比如有一个数组int arr[3] = {1,4,8},生成组合数就是要生成{...

  • Oracle 集合处理sql

    /根据一组坐标+半径+生成的坐标精度生成一组圆形集合数据/SELECT SDO_UTIL.CIRCLE_POLYG...

  • 时间长了就生疏的排列组合

    排列数:组合数:全排列:排列是先组合再排列: 最基本的排列组合公式,不能忘在脑后,应该熟稔于心。 排列和组合的区...

  • 《算法竞赛入门经典》第七章学习笔记

    枚举排列 生成1~n的排列 生成可重集的排列 利用STL生成排列 子集生成 增量构造法 位向量法 二进制法

  • TensorFlow(3) 线性回归

    生成数据 拟合数据 绘制模型

  • 【计算机数学】组合数知识

    组合数排列: 那么在计算机中怎么求组合数排列呢: 可以通过递归求, 类似杨辉三角的方式算法方面我们一般用性能好的非...

  • JS数据类型—对象

    概述 生成方法 什么是对象?简单说,对象就是一组“键值对”(key-value)的集合,是一种无序的复合数据集合。...

  • 按照字典序生成全排列

    说到排列,肯定先想到生成排列,这一节讲如何按照字典序法生成数字的全排列或者某一排列的下一排列。 原理如上,给个题目...

  • 组合数学-排列公式优化

    一般的排列组合计数公式 分两种情况: 1.从N个不同的物品中取出K个物品,考虑其次序,有P[N][K]中情况,P[...

  • 生成组合对象之从底至上生成排列

    从底至上生成排列 对于生成{1,...,n}的所有n!个排列,使用减一技术可以这样思考 将该问题的规模减一就是生成...

网友评论

      本文标题:生成排列、组合数

      本文链接:https://www.haomeiwen.com/subject/baokattx.html