首页 > 编程语言 >算法练习:排列组合之子集合

算法练习:排列组合之子集合

时间:2022-12-07 18:40:05浏览次数:44  
标签:mDstArrayTemp int 子集合 back gResultSet 算法 IntArray mSrcArray 排列组合


问题描述

输入一个含有不同数字的序列,输出其所有子集合(含空集)。要求:1)集合里元素有序排列;2)输出结果不含有重复集合

 

举例

输入序列{3,1,2}

输出:{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

 

问题分析

可以使用排列组合问题求解的第一种方法:分期摊还。初始化时,结果集合里含有一个空集。当扫描数列时,保留原有集合,同时将当前元素插入现有的所在集合中,从而形成新的集合。详见后面代码的GetSubSetsAmortized函数。

也可以使用第二种方法:for循环中使用递归。注意:1)保留任意的中间结果,而不是遍历完成数列才保存结果。2)利用完了数列的数之和,需要回退,即回溯法,恢复至使用前的状态。详见后面代码的GetSubSetsRecursive函数。

 

扩展问题

如果序列中含有重复元素,又要保证输出结果不含重复集合,如何处理?为了避免输出重复组合,只取第一个相同的元素加入组合中。详见后面代码的GetSubSetsRecursiveEx函数。

 

代码部分

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

using namespace std;

typedef vector<int> IntArray;
typedef vector<vector<int>> ResultSet;


ResultSet gResultSet;//结果集


//采用分期摊还的方法
void GetSubSetsAmortized( const IntArray& mSrcArray )
{
//加入空集
gResultSet.push_back( IntArray() );

for( int i = 0; i < mSrcArray.size(); ++i )
{
int nCount = gResultSet.size();
for( int j = 0; j < nCount; ++j )
{
IntArray mSubSet = gResultSet[j];
mSubSet.push_back( mSrcArray[i] );
gResultSet.push_back( mSubSet );
}
}
}

//采用for循环内递归调用
void GetSubSetsRecursive( const IntArray& mSrcArray, IntArray& mDstArrayTemp, int iStart )
{
if ( iStart > mSrcArray.size() ) return;

gResultSet.push_back( mDstArrayTemp );//保留任意的中间结果

for( int i = iStart; i < mSrcArray.size(); ++i )
{
//加入元素
mDstArrayTemp.push_back( mSrcArray[i] );

GetSubSetsRecursive( mSrcArray, mDstArrayTemp, i + 1 );

//移除元素
mDstArrayTemp.pop_back();
}
}


//采用for循环内递归调用
void GetSubSetsRecursiveEx( const IntArray& mSrcArray, IntArray& mDstArrayTemp, int iStart )
{
if ( iStart > mSrcArray.size() ) return;

gResultSet.push_back( mDstArrayTemp );//保留任意的中间结果

for( int i = iStart; i < mSrcArray.size(); ++i )
{
//避免结果集重复,只取第一个相同值加入
if ( i != iStart && mSrcArray[i] == mSrcArray[i-1] ) continue;

//加入元素
mDstArrayTemp.push_back( mSrcArray[i] );

GetSubSetsRecursiveEx( mSrcArray, mDstArrayTemp, i + 1 );

//移除元素
mDstArrayTemp.pop_back();
}
}

//打印结果集
void OutSubSets()
{
for( ResultSet::iterator it = gResultSet.begin();
it != gResultSet.end(); ++it )
{
if ( it->empty() )
{
cout << "空集" << endl;
continue;
}
for( IntArray::iterator itTemp = it->begin();
itTemp != it->end(); ++itTemp )
{
cout << *itTemp << " ";
}
cout << endl;
}
cout << "--------------------------------------------" << endl;
}

int main()
{
IntArray mSrcArray;
int nTemp;
while( true )
{
mSrcArray.clear();
while( cin >> nTemp )
{
if ( nTemp == 0 ) break;
mSrcArray.push_back( nTemp );
}

//排序
sort( mSrcArray.begin(), mSrcArray.end() );


gResultSet.clear();
//GetSubSetsAmortized( mSrcArray );

IntArray mDstArrayTemp;
GetSubSetsRecursiveEx( mSrcArray, mDstArrayTemp, 0 );

//打印结果集
OutSubSets();
}
return 0;
}



系列文章说明:
1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟,那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷,程序员面试揭秘》一书而写的一些心得体会,文章大多数观点均来自此书,特此说明!
3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.

作者:山丘儿


标签:mDstArrayTemp,int,子集合,back,gResultSet,算法,IntArray,mSrcArray,排列组合
From: https://blog.51cto.com/u_15905375/5919883

相关文章

  • 算法练习:排列组合之全排列
    问题描述输入一个不含相同数字的序列,输出所有可能的排列。 问题分析与之前的“求解子集合”类似,使用递归方法:典型的在for循环内调用递归函数。不同的是,必须等到所有的数字......
  • 算法练习:排列组合之组合和
    问题描述给出一组不同的正整数序列和一个目标值,求出所有可能的组合,使得组合里所有元素和为目标值。要求:1)每个组合里的元素按照升序排列。2)输出组合里不含有重复的组合。3)输......
  • 算法练习:TopK_1
    问题描述求一维数组中最小的K个数。 方法一:排序先把数组从小到大排序,取前K个数。时间复杂度为O(nlogn)。如果数组过大,机器内存无法同时容纳整个数组,则需要使用外部排序。以......
  • mybatis-plus雪花算法生成Id使用详解
    文章目录​​前言​​​​一、mybatis-plus官网​​​​二、雪花算法实战​​​​1.建表​​​​2.新建测试工程​​​​3.单元测试​​​​三、实现分析​​​​四、为什么......
  • mybatis-plus雪花算法增强:idworker
    文章目录​​前言​​​​一、官网​​​​二、默认实现的弊端​​​​三、mybatis-plus中datacenterId和workerId的默认生成规则​​​​四、idworker介绍​​​​五、idwo......
  • 算法练习:两指针之三数之和为0
    问题描述给出一个整型数组,找出所有三个元素的组合,其组合之和等于0。要求在结果集里不含有重复的组合。举例:输入{-2, 1, -1, 2, 1}输出{-2, 1, 1 } 问题分析最容易想到的是......
  • 算法练习:两数之和
    题目:给定一个整型数组,是否能找出两个数使其和为指定的某个值?注:整型数组中不存在相同的数。一、解题方法1、暴力解法(时间复杂度O(n^2) )这是最容易想到的一种方法,即使用两......
  • 操作系统:银行家算法(避免死锁)
    算法介绍:程序实现:/*****************************************************程序:银行家算法实现作者:小单时间:2013年11月5日***************************......
  • KMP算法详解-字符串匹配
    1.什么是KMP是由这三位学者发明的:Knuth,Morris和Pratt,所以取了三位学者名字的首字母。所以叫做KMP2.KMP的用处KMP主要用于字符串匹配。KMP的主要思想是当出现字符串不匹......
  • 算法练习:两指针之有序数组去重
    问题描述给出一个有序数组,就地移除重复元素,保持每个元素只出现一次,并返回新数组的长度。 问题分析这个比较简单,直接使用两个指针,一个在前,一个在后,扫描一遍数组即可。时间复......