[递归] 排列组合 - 从一个字符串中任意选取N个元素构成的所有排列组合 - C语言

青旅半醒 2022-04-18 05:59 196阅读 0赞

> 排列组合

【题目】求从字符串中"ABCD"中任取3个元素构成的所有排列组合

1.   A l e n ( s t r ) n = C l e n ( s t r ) n ∗ A n n A\_\{len(str)\}^n = C\_\{len(str)\}^n \*A\_\{n\}^n Alen(str)n=Clen(str)n∗Ann
2.  先从ABCD中选3个元素，然后对这三个元素进行全排列

【如何求排列】https://blog.csdn.net/summer\_dew/article/details/83097993  
【如何求组合】https://geodoer.blog.csdn.net/article/details/83315100

【结果】  
![在这里插入图片描述][20181109131150504.png]

【代码】

#include<stdio.h>
    
    
    int combination_permutation(char tmp[], int n);
    int combination(char *tmp,int m, int index);
    int permutation(char str[],int sbegin, int send);
    void swap(char *c1, char *c2);
    
    int main() { 
    	char tmp[50];
    	int n;
    	int cnt;
    
    	scanf("%s", tmp);
    	scanf("%d", &n);
    	// tmp中选n个进行全排列
    	cnt = combination_permutation(tmp, n);
    	printf("\n种数：%d\n", cnt);
    	return 0;
    }
    
    int combination_permutation(char tmp[], int n) { 
    	return combination(tmp, n, 0);
    }
    
    char arr[50];
    // 在tmp数组中选m个，第m个放在index的位置
    int combination(char *tmp,int m, int index) { 
    	int case1, case2;
    
    	if (m==0) {  //选完了
    		// 把arr进行全排列
    		arr[index] = '\0';
    		//printf("%s\n", arr);
    		return permutation(arr, 0, index-1);
    	}
    	
    	if (*tmp!='\0') { 
    		//选*tmp
    		arr[index] = *tmp;
    		case1 = combination(tmp+1, m-1, index+1);
    		//不选*tmp
    		case2 = combination(tmp+1, m, index);
    		return case1 + case2;
    	}
    	return 0;
    }
    // 将str中[sbegin, send]中进行全排列
    int permutation(char str[], int sbegin, int send) { 
    	int i;
    	int cnt=0;
        if(sbegin == send) { //当 sbegin = send时输出 
            for( i = 0; i<=send; i++)   //输出一个排列 
    			printf("%c", str[i]);
            printf("\n");
    		return 1;
        }  
        else {   
            for( i = sbegin; i <= send; i++) { //循环实现交换和sbegin + 1之后的全排列 
                swap(&str[i], &str[sbegin]);   //把第i个和第sbegin进行交换
                cnt += permutation(str, sbegin + 1, send);  
                swap(&str[i], &str[sbegin]);   //【注1】交换回来 
            }
        }
    	return cnt;
    }
    void swap(char *c1, char *c2) { 
    	char tmp;
    	tmp = *c1;
    	*c1 = *c2;
    	*c2 = tmp;
    }

【如果只选3个，可以用以下暴力的方法】

/* * @Test:口袋中有红、黄、蓝、白、黑5种颜色的球若干个。每次从口袋中先后取3个球，问取到3种不同颜色的球的可能取法，输出每种排列的情况 */
    #include<stdio.h>
    int main() { 
    	enum Color { red,yellow,blue,white,black};
    	enum Color i,j,k,pri;
    	int n,loop;
    	
    	n=0;
    	for (i=red; i<=black; i++) { 
    		for (j=red; j<=black; j++) { 
    			if (i!=j) { 
    				for (k=red; k<=black; k++) { 
    					if ( (i!=k) && (j!=k) ) { 
    						n++;
    						printf("%-4d",n);
    						for(loop=1; loop<=3; loop++) { 
    							switch (loop) { 
    								case 1:pri=i;break;
    								case 2:pri=j;break;
    								case 3:pri=k;break;
    								default:break;
    							}
    							switch(pri) { 
    								case red : printf("%-10s","red"); break;
    								case yellow : printf("%-10s","yellow"); break;
    								case blue : printf("%-10s","blue"); break;
    								case white : printf("%-10s","white"); break;
    								case black : printf("%-10s","black"); break;
    								default:break;
    							}
    						}
    						printf("\n");
    					}
    				}
    			}
    		}
    	}
    
    	printf("\ntotal:%5d\n",n);
    	return 0;
    }

[20181109131150504.png]: /images/20220418/922ceeaf16614c9aaba59d173058200d.png