`

程序生成组合C(N,K)输出

阅读更多

本来是想在网上搜索下现成的,结果看到一堆想吐的,尼玛啊,什么递归了,什么回溯了。无语!难道就不能负责任点,搜索下相关算法,然后,好好的实现下?又不是有多难的算法!最可恶的是,这些人还zhuangbility,以为自己写的算法很好,贴出来炫耀,有啥可炫耀的?

数学简单道理

N! <<<< N^N

我把它看成N进制,全部生成一遍,去掉位数有重复的,必然是N!这样的排列算法都比哪些瞎写的好

C(N,K> <<< N^K,同样用N进制,一共K位,那样全生成一遍,去掉不合理的(如必须是升序,或者降序),自然是对的。就这个最浅显的算法,也比这些zhuangbility的人贴的算法强。

 

给个knuth排列组合书(第四卷)的算法实现(这还是其性能最差的一个)

 

//在N中选取K个数,[first,last)必须有序
template<typename rand_it,typename T>
void choose(rand_it first,rand_it last,int k,std::vector<std::vector<T> >&out)
{
    std::vector<int> assitVec ;
    assitVec.resize(k+1);
    
    //std::sort(vec.begin(),vec.end());
    
    //<1>初始化,//需要增加一个哨兵
    //std::copy(vec.begin(),vec.begin()+k,assitVec.begin());
    assitVec.resize(k+1);
    for(int j=0;j<k+1;j++){
        assitVec[j]=j;
    }
    
    int N=std::distance(first,last);
    int bit=0;
    int i=0;
    assitVec[k]=N;
LOOP:
    //<2>判断终止条件
    if(assitVec[i] == N){
        //结束
        return ;
    }
    //<3>输出辅助数组
    out.push_back(std::vector<T>(k));

    
    for(int j=0;j<k;j++)
    {
        rand_it it = first;
        std::advance(it,assitVec[j]);
        out.back()[j] = *it;
    }
    //<4>调整
    int flag=0;
    while(i<k){
    if(assitVec[i] +1 == assitVec[i+1])
    {
        //需要进一位,当前位恢复原始状态
        assitVec[i] = i;
        i++;
        flag=1;
    }
    else{
        assitVec[i]++;
        break;
       }
    }
    if(assitVec[i] == N){
        //结束
        return ;
    }
    for(bit=0;bit<i;bit++){
        assitVec[bit]=bit;
    }
    if(flag){
        i=0;
    }
    goto LOOP;
}

 上面的迭代器,虽然写的是random_it,但实际上支持output_it就可以了。

仅仅是 std::advance(it,assitVec[j]);这句稍微慢一点,当然实际上可以忽略。

 

使用如下举例:前提条件 K要小于集合长度

int main(int argc,char*argv[]){
    std::vector<int>vec(10);
    for(int i=0;i<10;i++){
        vec[i]='z'-i;
    }
    std::vector<std::vector<int> > out;    
   // std::sort(vec.begin(),vec.end());
    choose(vec.begin(),vec.end(),3,out);
    printf("%d\n",out.size());
    for(int i=0;i<out.size();i++){
        for(int j=0;j<out[i].size();j++){
            std::cout<<(char)out[i][j]<<",";
        }
        std::cout<<std::endl;
    }
    return 0;
}

 

 

分享到:
评论

相关推荐

    经典C语言源程序100例

    - 在上述程序中,虽然没有直接使用数组,但可以理解为循环中的数字组合可以看作是数组的一种应用,如`printf("%d,%d,%d\n",i,j,k);`。 3. **逻辑运算符** - `&&`表示逻辑与,只有两边的表达式都为真时,结果才为...

    C经典算法之排列组合

    ### C经典算法之排列组合 #### 知识点解析 **排列组合**是计算机科学与数学中的一个重要概念,广泛应用于密码学、数据处理、优化问题等领域。本篇内容主要介绍了如何利用C语言实现一个基本的排列算法。 #### 排列...

    排列组合生成算法

    - **深度优先搜索**:同样可以使用递归的深度优先搜索策略来生成组合,每次选择一个元素加入到结果中,然后在剩余元素中继续搜索,直到达到所需组合数量。 - **回溯法**:与排列类似,可以通过回溯法生成所有组合...

    c语言简单程序举例

    ### C语言简单程序知识点 #### 知识点一:杨辉三角形的生成与输出 在C语言中,可以通过循环结构来实现杨辉三角形的生成。本例中,杨辉三角形通过以下步骤实现: 1. **主函数** `main()` 负责整体流程的控制: - ...

    C语言实现生成贝塞尔曲线(代码).doc

    - `zuhe(int n, int k)`:计算组合数 \( C(n, k) \),即从 \( n \) 个不同元素中取出 \( k \) 个元素的组合数。 - `fang(float n, int k)`:计算 \( n \) 的 \( k \) 次幂。 - `benkn(int n, int k, float t)`:计算...

    谭浩强c语言程序设计

    ### 谭浩强《C语言程序设计》关键知识点概览 #### 1. C语言概述 - **1.1 C语言的发展过程** - C语言最初由丹尼斯·里奇于1972年在贝尔实验室开发。 - 它是为UNIX操作系统设计的,后来成为多种操作系统的标准编程...

    11选n组合.rar

    在压缩包"11选n组合.rar"中包含的"易语言11选n组合源码"很可能是一个用易语言编写的程序,用于生成和计算11选n的所有可能组合。 1. **组合的概念**: - 组合是数学中的一种基本概念,它与排列不同。组合不考虑元素...

    java m取n 重复 不重复 排列组合 for循环嵌套递归

    根据给定文件的信息,我们可以总结出以下关于Java中m取n排列组合的实现方式,包括重复与不重复的情况,以及如何使用for循环嵌套和递归来实现这些算法。 ### Java中m取n排列组合实现 #### 一、背景介绍 在计算机...

    100个C语言小程序(详细源码说明)

    此程序旨在生成所有不重复数字的三位数,并输出它们。对于学习C语言的初学者来说,这是一个很好的实践项目,因为它可以帮助理解嵌套循环、条件判断和基本的输出操作。 **关键知识点**: 1. **嵌套循环**:通过三个...

    C语言经典源程序100例

    #### 知识点一:生成无重复数字的三位数(程序1) **题目:** 给定四个数字1、2、3、4,需要找出所有可能组成的互不相同且没有重复数字的三位数,并计算总共有多少个这样的数。 **程序分析:** 通过三层嵌套循环分别...

    n个元素全排列 & 整数n的划分

    在给定的C程序中,`Perm`函数通过递归实现了全排列的生成。其基本思想是: 1. 当只有一个元素时,输出这个元素即为一种排列。 2. 对于每个位置k(从0到m-1),将该位置上的元素与位置k之后的所有元素交换,然后对...

    qtc++排列组合实现

    在编程领域,排列组合是算法设计中的一个重要概念,它涉及到如何有效地生成所有可能的序列或组合作为问题的解决方案。本篇文章将详细讲解如何在Qt C++环境中实现排列组合的算法。 Qt是一个跨平台的C++图形用户界面...

    C语言经典小程序

    **内容概述**: 此程序生成所有可能的不重复数字组合。 **关键知识点**: - **条件判断**: 使用 `if` 来检查是否满足条件。 - **嵌套循环**: 三个 `for` 循环嵌套,用于遍历所有可能的组合。 **代码分析**: ```c #...

    C实现任意阶矩阵求逆矩阵

    1. **初始化矩阵**: 创建一个n*n的二维数组,存储原始矩阵,以及一个2n*2n的二维数组,用于存储原始矩阵和单位矩阵的组合,即[| A | E ]。 2. **行变换**: 通过行替换操作(加减、缩放、交换行)将左半部分的A矩阵...

    100道C语言基础程序

    ### C语言基础知识解析 #### 知识点一:组合数学应用——生成所有可能的三位数 **背景介绍:** 在程序设计中,特别是在算法和数据结构的学习过程中,经常会遇到需要生成特定模式的数据集的情况。例如,给定一组...

    输出杨辉三角java入门程序

    在杨辉三角中,第n行有n个数字,第k个数字表示的是组合数C(n, k),即从n个不同元素中选择k个的方法数。 2. **Java程序设计基础**:此程序展示了基本的控制流程、变量声明和数据类型。在Java中,可以使用循环(如for...

Global site tag (gtag.js) - Google Analytics