<commit_before>---
layout: post
title: 全排列的递归与非递归实现
description: "全排列是一个十分基础的概念，掌握起来也很简单"
tags: [算法]
image:
  background: witewall_3.png
comments: true
share: true
---

		全排列是一个十分基础的概念，是一串有可比权值的元素出现的所有排列形式，例如 '张全蛋'、'张蛋全'、'全张蛋'、'全蛋
	张'、'蛋全张'、'蛋张全'就是张全蛋的全排列，所以我们发现全排列用来取名字是很不错的，如果对每个汉字在名字中的权值做一
	张表，再来一张可能出现的不同字同时出现在名字中的关联权值表，那么全排列可以算出一张取名字的优先表，暂不表。

<!--more-->	

		那么全排列基本的一个规律我们可以很明显的发现，一个元素集合的全排列可以由该集合U内任意元素a加上剔除该元素后的集合
	u的全排列组成，而集合u也可以使用该方式去求全排，而最后不可细分的集合就是一个元素。这个描述很适合由递归来做，拿'张全
	蛋'来说，它的全排列由:
		'张'+'全蛋'的全排       '全'+'张蛋'的全排       '蛋'+'张全'的全排
		简而言之 由集合U中每个元素与U的第一个元素交换位置后，剩余的元素集合u递归去做该操作，直到u中只剩1个元素时(即递归
	到集合最后一个元素时)输出一个排列，最终得到集合U全排列。
	
<pre><code>
//求集合U的全排递归实现 
//all-s的值即为剩余元素集合u的大小
//s即为u集合的起点位置，起始位置为0
void allSorts(char U[],int s,int all){
	if(s == all){
		printf("%s\n",U);	
	}else{
		for(int i=s;i < all;i++){
			swaps(U,i,all-1);
			allSorts(U,s+1,all);
			swaps(U,i,all-1); //换回去等待下一个循环(i+1)与末尾换
		}
	}
}
void swaps(char s[],int i,int j){
	char t = s[i];
	s[i] = s[j];
	s[j] = t;
}
</code></pre>

		第二种方式是用非递归的方法去操作，对于'1234'来说全排列按照字典序'1234'的下一个排列为'1243'，最后一种排
	为'4321'，权值越大的元素在高位的排列应该越靠后，那么如果要靠生成的方法去打印出每一个排列，如果出现权值大的元素<commit_msg>add new posts<commit_after>---
layout: post
title: 全排列的递归与非递归实现
description: "全排列是一个十分基础的概念，掌握起来也很简单"
tags: [算法]
image:
  background: witewall_3.png
comments: true
share: true
---

	全排列是一个十分基础的概念，是一串有可比权值的元素出现的所有排列形式，例如 '张全蛋'、'张蛋全'、'全张蛋'、'全蛋
张'、'蛋全张'、'蛋张全'就是张全蛋的全排列，所以我们发现全排列用来取名字是很不错的，如果对每个汉字在名字中的权值做一
张表，再来一张可能出现的不同字同时出现在名字中的关联权值表，那么全排列可以算出一张取名字的优先表，暂不表。

<!--more-->	
	那么全排列基本的一个规律我们可以很明显的发现，一个元素集合的全排列可以由该集合U内任意元素a加上剔除该元素后的集合
u的全排列组成，而集合u也可以使用该方式去求全排，而最后不可细分的集合就是一个元素。这个描述很适合由递归来做，拿'张全
蛋'来说，它的全排列由:
	'张'+'全蛋'的全排       '全'+'张蛋'的全排       '蛋'+'张全'的全排
	简而言之 由集合U中每个元素与U的第一个元素交换位置后，剩余的元素集合u递归去做该操作，直到u中只剩1个元素时(即递归
到集合最后一个元素时)输出一个排列，最终得到集合U全排列。
	
<pre><code>
//求集合U的全排递归实现 
//all-s的值即为剩余元素集合u的大小
//s即为u集合的起点位置，起始位置为0
void allSorts(char U[],int s,int all){
	if(s == all){
		printf("%s\n",U);	
	}else{
		for(int i=s;i < all;i++){
			swaps(U,i,all-1);
			allSorts(U,s+1,all);
			swaps(U,i,all-1); //换回去等待下一个循环(i+1)与末尾换
		}
	}
}
void swaps(char s[],int i,int j){
	char t = s[i];
	s[i] = s[j];
	s[j] = t;
}
</code></pre>

		第二种方式是用非递归的方法去操作，对于'1234'来说全排列按照字典序'1234'的下一个排列为'1243'，最后一种排
	为'4321'，权值越大的元素在高位的排列应该越靠后，那么如果要靠生成的方法去打印出每一个排列，如果出现权值大的元素
{'fraction_non_alphanumeric': 0.17075306479859895, 'fraction_numerical': 0.020140105078809107, 'mean_word_length': 6.347266881028939, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2394190', 'n_tokens_mistral': 1841, 'n_tokens_neox': 1999, 'n_words': 131}