Java代码:
import java.util.*;
public class Main{
static int n;
static int[] a;//一种排列情况
static boolean[] b;//判断数字i是否已被使用
static void dfs(int step){//step表示当前到了第几位
if(step==n+1){//前n位已经放好,输出这种排列情况
for(int i=1;i<=n;i++)
System.out.print(a[i]);
System.out.println();
return;
}
for(int i=1;i<=n;i++){
if(!b[i]){//若数字i还未被使用
a[step]=i;//在当前位上放i
b[i]=true;//防止重用
dfs(step+1);//放下一位数字
b[i]=false;//回溯法,进行另一种尝试
}
}
}
public static void main(String[] args){
Scanner in=new Scanner(System.in);
n=in.nextInt();
a=new int[n+1];
b=new boolean[n+1];
dfs(1);//从第一位开始放
}
}
上述代码改用Python:
n=int(input())
a=[]
b=[False]*(n+1)
def dfs(i):
if i==n+1: # 1~n已经搜索完毕
print(a)
for num in range(1,n+1):
if not b[num]:
a.append(num)
b[num]=True
dfs(i+1)
a.pop()
b[num]=False
dfs(1)
直接调用Python itertools库里的permutations函数:
import itertools as it
n=int(input())
perms=it.permutations(list(i for i in range(1,n+1)))
for perm in perms:
print(perm)
版权声明:本文为beilunc7原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。