全排列和全组合
1、全排列
题目
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
分析
1、把整个字符串视为第一个字符和后来的字符的组合
2、每次确定一个元素,和后面的元素依次兑换
https://zhuanlan.zhihu.com/p/34114529
代码
class Solution {
public:
vector<string> result;
vector<string> Permutation(string str) {
if(str.size()==0){
return result;
}
PermutationTest(str,0);
sort(result.begin(),result.end());
return result;
}
void PermutationTest(string str,int begin){
if(str.size()-1 == begin){
result.push_back(str);
return;
}
for(int i = begin;i<str.size();i++){
if(i!=begin && str[i] == str[begin]){
continue;
}
swap(str[begin],str[i]);
PermutationTest(str,begin+1);
swap(str[begin], str[i]);
}
}
};
2、全组合
如果不是求字符的所有排列,而是求字符的所有组合应该怎么办呢?还是输入三个字符 a、b、c,则它们的组合有a b c ab ac bc abc。当然我们还是可以借鉴全排列的思路,利用问题分解的思路,最终用递归解决。不过这里介绍一种比较巧妙的思路 ——基于位图。
假设原有元素 n 个,则最终组合结果是 个。我们可以用位操作方法:假设元素原本有:a,b,c 三个,则 1 表示取该元素,0 表示不取。故取a则是001,取ab则是011。所以一共三位,每个位上有两个选择 0 和 1。而000没有意义,所以是个结果。
这些结果的位图值都是 1,2…2^n-1。所以从值 1 到值 依次输出结果:
001,010,011,100,101,110,111 。对应输出组合结果为:a,b,ab,c,ac,bc,abc。
因此可以循环 1~2^n-1,然后输出对应代表的组合即可。有代码如下:
#include<stdio.h>
#include<string.h>
void Combination(char *str)
{
if(str == NULL)
return ;
int len = strlen(str);
int n = 1<<len;
for(int i=1;i<n;i++) //从 1 循环到 2^len -1
{
for(int j=0;j<len;j++)
{
int temp = i;
if(temp & (1<<j)) //对应位上为1,则输出对应的字符
{
printf("%c",*(str+j));
}
}
printf("\n");
}
}
void main()
{
char str[] = "abc";
Combination(str);
}
求2的n次方
可以用pow函数
或移位
解决。
power就是函数,返回值为2的n次方的结果 ,只适用于大于等于0
的int型数据.
https://blog.csdn.net/m0_38036750/article/details/91353071
递归方式
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
从图中可以看出,如果在前一次已经取出的数字,将不会在后面的数字组合中出现,从而有效避免重复。
package IMUHERO;
import java.util.LinkedList;
import java.util.List;
public class Solution77 {
LinkedList<List<Integer>>res=new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
if (n==0||k==0)return res;
LinkedList<Integer>list=new LinkedList<>();
generateCombine(n,k,1,list);
return res;
}
public void generateCombine(int n, int k, int start, LinkedList<Integer>list){
//与排序不同的是,递归参数中含有一个start,用来标记当前遍历到第几个数字,之前遍历完的将不在访问,此操作在下面的for循环中体现
if (list.size()==k){
res.addLast((LinkedList<Integer>)list.clone());
return;
}
//for (int i=start;i<=n;i++),下面进行剪枝
// 还有k - list.size()个空位, 所以, [i...n] 中至少要有 k - list.size() 个元素
// i最多为 n - (k - list.size()) + 1
for (int i=start;i<= n - (k - list.size()) + 1;i++){
list.addLast(i);
generateCombine(n,k,i+1,list);
list.removeLast();
}
return;
}
}
上一篇: 递归--谢宾斯基三角形、赛尔平斯基地毯