Generic placeholder image
闲敲代码、落灯花
What's past is prologue

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

保持热情,持续学习,每日精进

算法--生成可重集排列

算法--生成可重集排列

本文与作者在csdn上的博文【算法--生成可重集排列】保持同步


首先,把各个元素改成用户输入,输入数组为p,然后把if(a[k]==j)改为if(a[k]==p[j])a[cur]=j改成a[cur]=p[j],然后先把p数组中元素用模板函数sort()按从小到大排个序,接下来要更改原程序中控制元素不重复出现的部分:

for(int k=0;k<cur;k++){          
                if(a[k]==p[j]){
                    ok++;break;
                }
            }


把它改为控制重复次数的代码:

    int c1=0,c2=0;
            for(int x=0;x<cur;x++)if(p[j]==a[x])c1++;
            for(int y=0;y<n;y++)if(p[j]==p[y])c2++;


判断是否接收该元素也由条件

if(c1<c2)


决定。

下面是完整代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include <cstdlib>
using namespace std;

void permutation(int *a,int *p,int n,int cur){
    if(cur==n){
        for(int i=0;i<n;i++)printf("%d ",a[i]);printf("\n");
    }
    else {
        for(int j=0;j<n;j++)if(!j||p[j]!=p[j-1]){
            int c1=0,c2=0;
            for(int x=0;x<cur;x++)if(p[j]==a[x])c1++;
            for(int y=0;y<n;y++)if(p[j]==p[y])c2++;
            if(c1<c2){
                a[cur]=p[j];
                permutation(a,p,n,cur+1);
            }           
        }
    }
}
int main(){
    int n;
    scanf("%d",&n);
    int *a=new int[n];
    int *p=new int[n]; 
    for(int i=0;i<n;i++)scanf("%d",&p[i]);
    permutation(a,p,n,0); 
    delete(a);
    delete(p);
}



猜你喜欢
算法--生成1~n的排列
阅读 222

在暴力求解法中,我们常常要用上枚举一些简单内容以便方便获得解,若要输出整数n的前n个整数的全排列,则按字典序输出为: (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)。 从中我们似乎发现了一些规律:先输出以1开头的排列,再输出以2开头的排列,然后是3;...

生成子集——二进制法
阅读 208

用二进制位的0和1表示集合中是否存在该元素要生成0~n的子集,先生成0~n的二进制序列,这些序列的0、1位正好可以对应一个子集中全集在该位置上的元素是否存在,将其作为子集中存在的元素的标记,输出对应元素。#include #include

乘法运算过程模拟法首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。 在这个过程...

用大数乘法计算阶乘
阅读 244

在比较小的范围内阶乘可以递归实现,而求更大的数的阶乘一般用到long long长整形数,不过,即使这样,在耗时和再大些的阶乘上力有不逮,所以,在输入比较大的情况下,用大数乘法计算阶乘是最好的选择。 计算过程分2步: 1、输入字符串s,将它的值保存到整型n中; 2、从1~i~n-1循环将i转化...

生成子集——位向量法
阅读 183

生成0~n序列的子集对于0~n的每一个值在集合中都有存在和不存在两种状态,所以递归每个值的存在状态即可生成子集#include #include #include #include

太残忍,半个月不做题,就对题目毫无感觉了,明明思路正确清晰,但敲的代码满满的bug,连输入字符串前要开辟空间都能无视。。。还在输入后就清空了却在后面一个劲的对它操作。。。略怀悲伤地把代码改好了。#include #include #incl...

子集生成算法——增量构造法
阅读 363

思路是一次选出一个元素放入集合中生成0~n的子集,每次选出最小的值放入集合中,通过从0递增得到下一个位置的值。#include #include #include #include

常用的大数相乘算法有模拟加减法和分治法,第一种符合我们的运算习惯,第二种用数学方法提高了效率,(具体描述与实现可参考http://www.cnblogs.com/heyonggang/p/3599857.html)而两种各有优势的方法的程序实现都比较复杂,并且不易于初学者理解,于是我琢磨出了一个将...