全排列

发表于 2024/03/27 11:04:25 [计算机基础] 浏览次数：233

#include <stdio.h>
/**
 * 交换
 * @param arr    [description]
 * @param index1 [description]
 * @param index2 [description]
 */
void swap(int arr[], int index1, int index2){
		int temp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = temp;
}
void showArr(int arr[], int len){
	for(int i = 0; i < len; i++){
		printf("%d ", arr[i]);
	}
	printf("\n");
}
/**
 * 全排列 
 *思路:第一个数和后面的数（包括自己）交换，每个交换结果又用第二个数和后面的数交换，交换结果又用第三个数和后面的数交换....最后一个数和最后一个数交换。
 * @param arr   [数组]
 * @param index [交换数位置]
 * @param num   [最后一个数的位置]
 */
void perm(int arr[], int index, int endIndex){
	if(index == endIndex){ //一次递归结束
		showArr(arr, endIndex+1);
	}else{
		for(int i = index; i <= endIndex; i++){
			swap(arr, index, i); //交换数(index)和后面的数（包括自己）交换
			perm(arr, index+1, endIndex); //递归 index+1
			swap(arr, i, index); //交换完了，要换回来 以便 下一次循环
		}
	}
}

int main(){
	int arr[4] = {1, 2, 3, 4};
	perm(arr, 0, 3);
	return 0;
}