C\C++\C#实现求全排列
郁闷 没人来给我加分！假设{1,2,3}表示1,2,3三个数的全排列，那么有下面的结果：
{1,2,3}=1{2,3}，2{1,3}，3{1,2} 也就是说求1,2,3有全排列由三个部分组成了分别为1{2,3}，2{1,3}，3{1,2}，大括号前面的称为前缀。一直递归下去就可求出结果。所以假设perm(int list[],int begin,int end)表示输出前缀为"list"后缀为"list的全排列"。
令int list={1,2,3}，所以：
perm({1,2,3},0,2)=perm({1,2,3},1,2}，perm({2,1,3},1,2}，perm({3,2,1},1,3}；
理解了这个式子之后就可以写代码了：C源码 #include <stdio.h>
typedef int ElemType;
void swap(ElemType *a,ElemType *b){
//交换2个数
ElemType temp=*a;
*a=*b;
*b=temp;
}//swap
void perm(ElemType list[],int begin,int end){
int i=0;
if(begin==end){
for(i=0;i<=begin;i++)
printf("%d ",list);
printf("\n");
}
else
for(i=begin;i<=end;i++){
swap(&list,&list);
perm(list,begin+1,end);
swap(&list,&list);
}
}//perm
void main(){
ElemType list[]={1,2,3};
perm(list,0,2);
}
C++代码 #include <iostream>
template <class _Ty>
void perm(_Ty list[],int begin,int end){
//输出前缀为"list"后缀为"list的全排列"---这名话很重要；
//前缀是固定的，求后缀的时候要用递归求
if(begin==end){
//如果相等，则表明前缀为list，后缀就没有，所以直接输出前缀
for(int i=0;i<=begin;i++)
std::cout<<list;
std::cout<<std::endl;//输出一个之后，换行
}
else{
//如果不相等，就要循环(end-begin)次，每次前缀都不同
for(int i=begin;i<=end;i++){
std::swap(list,list);//交换之后就可以得到前缀了
perm(list,begin+1,end);//递归输出
std::swap(list,list);//换回来
}
}
}
void main(){
int list[]={1,2,3};
perm(list,0,2);
}
C#源码 using System;
using System.Collections.Generic;
namespace CSharpDemo
{
class Program
{
public
static
void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = a;
}
public
static
void Perm<T>(T[] list, int begin, int end)
{
if (begin == end)
{
for (int i =
0; i <= begin; i++)
Console.Write(list);
Console.WriteLine();
}
else
for (int i = begin; i <= end; i++)
{
Swap<T>(ref list, ref list);
Perm<T>(list, begin+1, end);
Swap<T>(ref list, ref list);
}
}
static
void Main(string[] args)
{
int[] list ={ 1, 2, 3 };
Perm<int>(list, 0, 2);
}
}
}
来学习~ 准备用matlab编~
页:
[1]
