欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

全排列和全组合

程序员文章站 2024-02-21 18:51:22
...

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;
    }
}

https://blog.csdn.net/qq_37768971/article/details/90553015

相关标签: 牛客练习