您的位置: 首页  >  文章  >  算法中的排列与组合

算法中的排列与组合

分类: 文章 • 2025-01-05 16:33:28

排列组合公式

不含重复元素的排列组合

算法中的排列与组合

含有重复元素的排列组合

如果产生的组合和排列可以包含有重复的元素，其实这类问题在苏荷数学上是多种集的排列和组合问题。

多重集的排列问题

  1. 设S是有k种不同类型对象的多重集合，每个元素都有无限的重复数。那么s的r排列数目是krk^r.
    需要注意的是，只要每种元素的数目大于r，对于r组合来说就是无限多的。
    怎么理解上面的定义呢，举个例子，冰淇淋有3种口味可以选择，我可以选择3种相同口味，也可以选择不同口味，每次选择即可相同也可不相同。再举个例子抛硬币3次，很显然，可能会出现3次都是正面，硬币出现正反面是可重复的。
    这很好理解，一次有k种选择，第二次有k∗k种选择，……，第r次有krk^r种选择。
    剑指offer中的面试题17.打印从1到最大的n位数，就是这类问题。可以假设一共有0-9十种对象，每种对象都有无数个(无数个和大于等于n个一样，因为排列的最长长度是n)，n位数就是十种对象的n排列，一共有10n10^n种。其实很好理解，第一位数字有10种选择，第二位也有10种选择，… 第n位也有10种选择。
  2. 设s是多重集合，有k种类型的对象，且每种类型的有限重复数是n1,n2,……,nk。s的大小是n=n1+n2+n3+……+nk。那么s的全排列数目等于：result=n!(n1!∗n2!∗……∗nk!)result=\frac{n!}{(n1!*n2!*……*nk!)}
    例子：词MISSISSIPPI中字母的排列数是？
    分析：词含有的字母总个数是11，M:1，I：4，S:4，P:2。所以result=11!/(1*4!*4!*2!).

多重集合的组合

设S是有k种类型对象的多重集合，每种元素均有无限的重复数。那么S的r组合的个数等于：C(r+k-1,r)==C(r+k-1,k-1).
需要注意的是，只要每种元素的数目大于r，对于r组合来说就是无限多的。
证明：S任何r组合一定呈现{x1a1,x2a2,……,xk*ak}的组合形式。x1+x2+……+xk=r.先将x系列数字分割成k部分，这样有了r+k-1个元素（要插入k-1个隔板，可以看做值为0的元素），用这些元素组成的一个r排列就是解。那么这样的排列个数是(r+k-1)!/(k-1)!/r!（除以同类型值的排列），即C(r+k-1,r)。

LeetCode：46. 全排列

题目描述:
给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
代码：

class Solution {
public:
    //深度优先遍历加回溯
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> vv;
        vector<bool> marked(nums.size(),false);
        vector<int> v;
        permulate(vv, v, nums, marked);
        return vv;
        
    }
    void permulate(vector<vector<int>> &vv, vector<int> &v, vector<int>& nums, vector<bool>& marked){
        if(v.size() == nums.size()){
            vector<int> rv(v.begin(),v.end());
            vv.push_back(rv);
            return;
        }
        for(int i = 0; i < nums.size(); i++){
            if(marked[i])
                continue;
            v.push_back(nums[i]);
            marked[i] = true; 
            permulate(vv, v, nums, marked);
            marked[i] = false; //回溯
            v.erase(v.end()-1);
        }
        
    }
};

组合

上面是求数组的全排列，我们同时思考一下数组的组合怎么求。思路来自剑指offer。
思路解析：
首先需要弄清楚排列和组合的区别，对于字符串"abc"，它的全排列包括：abc、acb、bac、bca、cab、cba。但它的所有组合为：a、b、c、ab、ac、bc、abc。也就是说一个长度为n的字符串，它的组合包括长度为1~n的所有字符子串(忽略顺序)。下面具体探讨一下字符串的组合问题的实现。
在求长度为n的字符串的组合时，我们要遍历从1到n所有的子串，当求长度为m(1≤m≤n)的组合时，可以把那个字符分成两部分：第一个字符和其余所有的字符。此时就分为两种情况了：
(1)组合包含第一个字符，则下一步在剩余字符里选取m-1个字符。
(2)组合不包含第一个字符，则下一步在剩余的n-1个字符中选取m个字符。
很明显，这个用递归实现比较清晰。总的来说，可以把求n个字符组成对的长度为m的组合问题分成两个子问题，即分别求n-1个字符中长度为m-1的组合；以及求n-1个字符中长度为m的组合。

class Solution {
public:

	vector<vector<int>> combination(vector<int>& nums) {
		vector<vector<int>> vv;
		vector<int> v;
		if (nums.size() == 0)
			return vv;
		for (int i = 1; i <= nums.size(); i++){
			combination(vv, v, nums, i, 0);
		}
		return vv;

	}
	void combination(vector<vector<int>> &vv, vector<int> &v, vector<int>& nums, int len, int start){
		if (len == 0){
			vector<int> rv(v.begin(), v.end());
			vv.push_back(rv);
			return;
		}
		if (start == nums.size())
			return;
		v.push_back(nums[start]);
		combination(vv, v, nums, len-1,start+1);
		v.pop_back();
		combination(vv, v, nums, len , start+1);
	}
};

剑指offer:面试题 38. 字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> a;
        if(str.empty())
            return a;
        Permutation(a,str,0);
        sort(a.begin(),a.end());//按照字典序输出
        return a;
     }
     void Permutation(vector<string> &array, string str, int begin)//遍历第begin位的所有可能性
     {
        //一次遍历的结束条件
        if(begin == str.size()-1)
        {
            array.push_back(str);
        }
        for(int i=begin;i<str.size();i++)
        {
            if(i!=begin && str[i] == str[begin])
            {
                continue;//有与begin位重复的字符串不进行交换，跳过
            }
            swap(str[i],str[begin]);
            //当i==begin时，也要遍历其后面的所有字符
            //当i!=begin时，先交换，使第begin位取到不同的可能字符，再遍历后面的字符
            Permutation(array,str,begin+1);
            swap(str[i],str[begin]);//为了防止重复的情况，还需要将begin处的元素重新换回来
        }
     }
};
int main()
{
    string a = "abc";
    Solution s;
    vector<string> b;
    b = s.Permutation(a);
    for(int i=0;i<b.size();i++)
    {
        cout<<b[i]<<endl;
    }
    return 0;
}

懒得敲了，代码来自:27、剑指offer–字符串的排列.
这种解法和上面的那道全排列的题是两种，解全排列的方法。

剑指offer中的面试题17.打印从1到最大的n位数

输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999。
注意不能直接打印输出，因为当n比较大的时候会溢出。
为了解决大数问题，可以使用字符串模拟加法。代码可以参考:打印从1到最大的n位数.
除此之外，还有一种解法就是多重集的全排列的解法。

void Print1ToMaxofNDigits(int n)
{
    if (n <= 0)
        return;

    char *number = new char[n + 1];
    number[n] = '\0';

    for (int i = 0; i < 10; ++i){
        number[0] = i + '0';
        Print1ToMaxofNDigitsRecursively(number,n,0);
    }

    delete[]number;
}

void Print1ToMaxofNDigitsRecursively(char* number, int length, int index)
{
    if (index == length - 1)
    {
        PrintNumber(number);
        return;
    }

    for (int i = 0; i < 10; ++i){
        number[index + 1] = i + '0';
        Print1ToMaxofNDigitsRecursively(number, length, index + 1);
    }
}

//打印数
void PrintNumber(char *number)
{
    bool isBeginning0 = true;
    int nLength = strlen(number);

    for (int i = 0; i < nLength; ++i){
        if (isBeginning0 && number[i] != '0')
            isBeginning0 = false;

        if (!isBeginning0)
            printf("%c", number[i]);
    }

    printf("\t");
}

懒得敲了，代码来自:打印从1到最大的n位数.

字符串的组合

参考文章:

  1. 排列组合详解
  2. 多重集合的排列与组合

相关推荐