排列与组合(permutation combination)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/****************************************************************
 * C++  计算排列数和组合数
 * date:20222-5-3
 * version: 1.0
 * author: Alex Li
 ****************************************************************/ 

#include <iostream>
using namespace std;
int fact(int n) {
   if (n == 0 || n == 1)
   return 1;
   else
   return n * fact(n - 1);
}
int main() {
   int n, m, comb, per;
   cout<<"Enter N : ";
   cin>>n;
   cout<<"\nEnter M : ";
   cin>>m;
   comb = fact(n) / (fact(m) * fact(n-m));
   cout << "\nCombination : " << comb;
   per = fact(n) / fact(n-m);
   cout << "\nPermutation : " << per;
   return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/**************************************************************** 
 * Description: print all permutations of a given string 字符串全排列
 * Author: Alex Li
 * Date: 2023-01-20 16:45:45
 * LastEditTime: 2023-07-08 12:16:04
****************************************************************/

#include <iostream> 
using namespace std; 

//字符串全排列
void permute(string a, int l, int r){ 
	// Base case 
	if (l== r) 
		cout<<a<<' '; 
	else{ 
		// Permutations made 
		for (int i = l; i <= r; i++) { //是字母l，不是数字1
			// Swapping done  遍历每个元素到[l,r]的第一个位置
			swap(a[l], a[i]);   
			// Recursion called 递归，缩小范围
			permute(a, l+1, r);
			swap(a[i],a[l]); //回溯，保证字符串顺序正确
		} 
	} 
} 

// Driver Code 
int main() { 
	string str;
    cout<<"please input a string: ";
    cin>>str; 
	int n = str.size(); 
	permute(str, 0, n-1); 
	return 0; 
} 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/**************************************************************** 
 * Description: permutation of string and m 从字符串中选取m个元素的排列
 * Author: Alex Li
 * Date: 2023-07-07 14:15:34
 * LastEditTime: 2023-07-08 12:15:02
****************************************************************/

#include <iostream> 
using namespace std; 
int m;

//字符串全排列
void permute(string a, int l, int r){ 
	if(m==0)return;
	// Base case 
	if (l==m){
        for (int i = 0; i <m; i++)cout<<a[i];
		cout<<' '; 
	}
	else{ 
		// Permutations made 
		for (int i = l; i <= r; i++) { //是字母l，不是数字1
			// Swapping done  遍历每个元素到[l,r]的第一个位置
			swap(a[l], a[i]);   
			// Recursion called 递归，缩小范围
			permute(a, l+1, r);
		} 
	} 
} 

// Driver Code 
int main() { 
	string str;
		
    cout<<"please input a string: ";
    cin>>str; 
	cout<<"please input the length of substring: ";
	cin>>m;
	int n = str.size(); 
	permute(str, 0, n-1); 
	return 0; 
} 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

/**************************************************************** 
 * Description: C++ program to print all combination of size r in an array of size n
 * Author: Alex Li
 * Date: 2023-07-07 14:15:34
 * LastEditTime: 2023-07-10 21:01:39
****************************************************************/
#include <iostream> 
using namespace std; 
//a是原字符串，d是用于存放输出组合元素的字符串，start 和end是标识a数组，index和r是标识d数组。
void Combination(string a, string  d,int start, int end, int index, int r){
	 
	 if(index==r){
		for (int  j = 0; j<r; j++)cout<<d[j];
		cout<<" ";
		return ;		
	 }

	 for (int i =start; i <=end; i++){ 
		d[index]=a[i];
		Combination(a,d,i+1,end,index+1,r);
	 }
}

int main(){
string str;
	int r;	
    cout<<"please input a string: ";
	cin>>str;
    cout<<"please input the length of substring: ";
	cin>>r;
	string data;  //临时存储组合数
	int n=str.size();
	Combination(str,data,0,n-1,0,r);
}