给定一个数字N 实现1~N的所有全排列
刚开始是想写个递归的，结果给写成迭代了。后来发现可以写的很简单。。。
class A(object):
tree = []
seq=""
def buildtree(self):
n1 = [1,‘f‘]
n2 = [2,‘f‘]
n3 = [3,‘f‘]
n4 = [4,‘f‘]
self.tree = [n1,n2,n3,n4]
def dfs( self):
t=self.tree
if( type(t) is int):
print t
else:
for e in t:
if e[1]==‘f‘:
self.seq = self.seq +str(e[0])
e[1]=‘t‘
self.dfs()
print self.seq
self.seq= self.seq[0:len( self.seq)-1]
e[1]=‘f‘
print(‘‘)
a=A()
a.buildtree()
a.dfs()
这里用python 实现 递归函数
class A(object):
tree = []
seq=""
def buildtree(self):
n1 = [1,[],‘f‘]
n2 = [2,[],‘f‘]
n3 = [3,[],‘f‘]
n4 = [4,[],‘f‘]
n1[1]=[n2,n3,n4]
n2[1]=[n1,n3,n4]
n3[1]=[n1,n2,n4]
n4[1]=[n1,n2,n3]
self.tree = [n1,n2,n3,n4]
def dfs( self,t):
if( type(t) is int):
print t
else:
for e in t:
if e[2]==‘f‘:
self.seq = self.seq +str(e[0])
e[2]=‘t‘
if type(e[1]) == list:
self.dfs(e[1])
print self.seq
self.seq= self.seq[0:len( self.seq)-1]
e[2]=‘f‘
print(‘‘)
a=A()
a.buildtree()
a.dfs(a.tree)
附上java的迭代算法 发现要实现迭代需要一个全局变量或者类中的公共成员 以及需要递归函数的格式，注意只是格式，而且就这个例子观测，函数时无参数的。上面的迭代的python实现也是
import java.util.ArrayList;
import java.util.List;
public class Dfs {
/**
* @param args
*/
static ArrayList<node> mapList = new ArrayList<node>();
static String seq="";
public class node{
String val;
boolean Looked;
node(String val){
this.val = val;
this.Looked = false;
}
}
public void buildMap(){
node n1 = new node("1");
node n2 = new node("2");
node n3 = new node("3");
node n4 = new node("4");
mapList.add(n1);
mapList.add(n2);
mapList.add(n3);
mapList.add(n4);
}
public void travel(){
for( node each:mapList)
if( each.Looked == false)
{ each.Looked = true;
seq+=each.val;
System.out.println(seq);
this.travel();
seq=seq.substring(0, seq.length()-1);
each.Looked = false;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Dfs dfs = new Dfs();
dfs.buildMap();
dfs.travel();
}
}
本文出自 “8691404” 博客，请务必保留此出处http://8701404.blog.51cto.com/8691404/1377093