全排列

2017-10-7 Plan C C语言

/* 递归 */

#include <stdio.h>
#include <string.h>

void select(int* arr, int* next, int total)
{
	int pos = next - arr;
	if(pos == total - 1)
	{
		for(int i = 0; i < total; i++)
		{
			printf("%d",arr[i]);
		}
		printf("\n");
	}
	else
	{
		for(int i = 0; i < total - pos; i++)
		{
			int temp = next[0];
			next[0] = next[i];
			next[i] = temp;
			
			select(arr, next+1, total);
		
			temp = next[0];
			next[0] = next[i];
			next[i] = temp;
		}
	}
}

void permutation(int* arr, int len)
{
	select(arr,arr,len);
}

int main()
{
	int arr[] = {1,2,3,4,5};
	permutation(arr,5);
}
/* 从后往前找到i满足*i<*(i+1) */
/* 从后往前找到j满足*i<*j */
/* 交换i,j的值 */
/* 将i+1及之后的数顺序颠倒 */

#include <stdio.h>
#include <string.h>

int permutation_next(int* arr, int len)
{
	int* i = arr + (len-2);
	for(; *i >= *(i+1) && i != arr; i--);

	if(*i > *(i+1))
	{
		return 0;
	}
	
	int* j = arr + (len-1);
	for(; *j <= *i && j != arr; j--);
	
	int temp = *i;
	*i = *j;
	*j = temp;
	
	int* p = i+1;
	int* q = arr + (len-1);
	for(;p < q; p++,q--)
	{
		temp = *p;
		*p = *q;
		*q = temp;
	}
	
	return 1;
}

void permutation(int* arr, int len)
{
	do
	{
		for(int i = 0; i < len; i++)
		{
			printf("%d",arr[i]);
		}
		printf("\n");
	}while(permutation_next(arr,len));
}

int main()
{
	int arr[] = {1,2,3};
	permutation(arr,3);
}


发表评论:

Powered by emlog
鄂ICP备16003833号