全排列问题：(非字典序)
public class Main
{
public static void main(String arsg[])
{
perm(new int[]{1,2,3,4,5},0,4)
}
public static void perm(int[] arr,int start,int end)
{
if(start == end)
{
for(int i = 0;i<arr.length;i++)
{
System.out.print(arr[i]+" ");
}
System.out.println();
}
else
{
for(int i = start;i<=end;i++)
{
swap(arr,start,i);
perm(arr,start+1,end);
swap(arr,start,i);
}
}
public static vodi swap(int[] arr,int i,int j)
{
int temp;
temp = arr[i];
arr[i] = arr[i];
arr[j] = temp;
}
}
字典序：洛谷1706全排列问题
import java.util.Scanner;
public class 全排列 {
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0;i<arr.length;i++)
{
arr[i] = i+1;
}
perm(arr,0,n-1);
}
public static void perm(int[] arr,int start,int end)
{
if(start == arr.length-1)
{
for(int i = 0;i<=end;i++)
{
System.out.print(arr[i]+" ");
}
System.out.println();
}
else
{
for(int i = start;i<=end;i++)
{
swap(arr,start,i);
perm(arr,start+1,end);
swapback(arr,start,i);//回溯
}
}
}
public static void swap(int[] arr,int i,int j)
{
int temp = arr[j];
for(int a = j;a>i;a--)
{
arr[a] = arr[a-1];
}
arr[i] = temp;
}
public static void swapback(int[] arr,int i,int j)
{
int temp = arr[i];
for(int a = i;a<j;a++)
{
arr[a] = arr[a+1];
}
arr[j] = temp;
}
}
从n个数字里面任意取r个数字排序：（洛谷P1157）
public class P1157 {
static int n,r,ay[];
static boolean arr[];
public static void main(String args[])
{ Scanner sc = new Scanner(System.in);
n = sc.nextInt(); //输入n个总的需要排列的元素
r = sc.nextInt();//输入r个排列个数
arr = new boolean[n+1];//标记数字是否使用过
ay = new int[r+1];//存放输出数组
perm(1);
}
static void perm(int x)
{
if(x > r)//递归出口，满r个数字输出
{
for(int i = 1;i<=r;i++)//从第一位开始存放
{
System.out.printf("%3d",ay[i]);//输出为3个字符
}
System.out.println();
}
else
{
for(int i = 1;i<=n;i++)//从第一位开始存放
{
if(arr[i])//boolean型的数据初始值为false
{
continue;
}
if(x>1&&ay[x-1]>i)//去重
{
continue;
}
arr[i] = true;
ay[x] = i;
perm(x+1);
arr[i] = false;
}
}
}
}
网友评论