首页 > 代码库 > 分治法 全排列问题的一个Java实现
分治法 全排列问题的一个Java实现
public class Perm { public static void perm(Object[] a, int k, int m) { if (k == m) for (int i = 0; i < a.length; i++) System.out.print(a[i]);
System.out.println(); else { for (int i = k; i <= m; i++) {
swap(a, k, i);
perm(a, k + 1, m);
swap(a, k, i); } } }
public static void main(String[] args)
{
Integer[] a = new Integer[6];
for (int i = 0; i < a.length; i++)
a[i] = new Integer(i);
perm(a, 0, 5);
}
public static void swap(Object[] a, int i, int j)
{
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
算法思想:
对n个元素的数组进行全排列,
如果n = 1则无需排列;
如果n >= 2,则对首个元素的取可能的所有值,后面n-1个元素进行全排列(递归)。
时间复杂度:
T(n) = n (T(n-1) + b) = Θ(n*n!)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。