本文我将首先用递归和非递归算法实现对整数数组的全排列，然后通过提炼接口，将这种算法运用到实现对其它数据类型的全排列，对long数组，列表，字符串等。
下面代码是用来实现对整数数组的排列的算法，具体原理见这里
。
public static List<int[]> perm(int[] a) {
return perm(a, 0, a.length);
}
public static List<int[]> perm(int[] a, int fromIndex, int toIndex) {
List<int[]> result = new ArrayList<int[]>();
perm(a, fromIndex, toIndex, result);
return result;
}
private static void perm(int[] a, int fromIndex, int toIndex, List<int[]> result) {
if (toIndex - fromIndex <= 1) {
result.add(a.clone());
} else {
for (int i = fromIndex; i < toIndex; i++) {
swap(a, fromIndex, i);
perm(a, fromIndex+1, toIndex, result);
swap(a, fromIndex, i);
}
}
}
private static void swap(int[] a, int i, int j) {
int temp = a[i]; a[i] = a[j]; a[j] = temp;
}
这里将所有的结果放在一个List中，这样对小的数据很好，但是对大的数据可能会OutOfMemory，在我的机器上当数据的大小>=10时就会OutOfMemory。我需要将它转换成非递归算法，并返回Iterator，这样保存在内存中的数据极少，而不会OutOfMemory。将该程序转换成非递归算法时，需要先画出递归树，具体该怎么做，这里就不详述了，见代码：
public static Iterator<int[]> permIterator(int[] a, int fromIndex, int toIndex) {
return new IntArrayPermIterator(a, fromIndex, toIndex);
}
public static Iterator<int[]> permIterator(int[] a) {
return new IntArrayPermIterator(a, 0, a.length);
}
public static Iterable<int[]> permIterable(int[] a, int fromIndex, int toIndex) {
return new IntArrayPermIterator(a, fromIndex, toIndex);
}
public static Iterable<int[]> permIterable(int[] a) {
return new IntArrayPermIterator(a, 0, a.length);
}
// 将递归翻译成非递归
private static class IntArrayPermIterator implements Iterator<int[]>, Iterable<int[]> {
private int[] array;
private int toIndex;
private LinkedList<StackFrame> frames = new LinkedList<StackFrame>();
public IntArrayPermIterator(int[] a, int fromIndex, int toIndex) {
this.array = a;
this.toIndex = toIndex;
frames.add(new StackFrame(fromIndex));
}
public boolean hasNext() {
return frames.size() > 0;
}
public int[] next() {
StackFrame frame = frames.getLast();
swap(array, frame.fromIndex, frame.currentIndex);
for (int i = frame.fromIndex + 1; i < toIndex; i++) {
frames.addLast(new StackFrame(i));
}
int[] result = array.clone();
frame = frames.removeLast();
while (!frames.isEmpty()) {
frame = frames.getLast();
swap(array, frame.fromIndex, frame.currentIndex);
if (frame.currentIndex != toIndex - 1) {
frame.currentIndex++; break;
}
frames.removeLast();
}
return result;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Iterator<int[]> iterator() {
return this;
}
}
private static class StackFrame {
int fromIndex;
int currentIndex;
public StackFrame(int fromIndex) {
this.fromIndex = fromIndex;
this.currentIndex = fromIndex;
}
public String toString() {
return String.format("[%d, %d]", fromIndex, currentIndex);
}
}
IntArrayPermIterator实现Iterator和Iterable接口，实现Iterable接口是为了能够在利用JDK5中增强for循环：
for (int[] a: permIterable(new int[]{1, 2, 3})) {
System.out.println(Arrays.toString(a));
}
这样做的问题是，如果要实现对long数组，char数组，List数据，字符串的排列，我几乎需要将它们重写一遍。我想重用这些算法，该怎么办呢？每当这时我都会想到提取接口。让我们观察递归版本的perm(int[] a, int fromIndex, int toIndex, List<int[]> result)方法(非递归版本类似)，它用到对数组a的进行操作的方法只有swap方法和a.clone()方法，因此可以将它提取出一个接口叫做Permable，为了不指定toIndex，我添加了一个新方法size()。另外为了不和Object中clone()方法冲突，我使用了copy这个名字。接口如下：
public interface Permable<T> {
void swap(int i, int j);
T copy();
int size();
}
该接口使用了类型参数T，表示返回的数据类型。使用这个接口，递归版本的排列算法为：
public static <T> List<T> perm(Permable<T> data) {
return perm(data, 0, data.size());
}
public static <T> List<T> perm(Permable<T> data, int fromIndex, int toIndex) {
List<T> result = new ArrayList<T>();
perm(data, fromIndex, toIndex, result);
return result;
}
private static <T> void perm(Permable<T> data, int fromIndex, int toIndex, List<T> result) {
if (toIndex - fromIndex <= 1) {
result.add(data.copy());
} else {
for (int i = fromIndex; i < toIndex; i++) {
data.swap(fromIndex, i);
perm(data, fromIndex+1, toIndex, result);
data.swap(fromIndex, i);
}
}
}
要对long数组，字符串，List等进行排序，只需要提供它们自己的Permable接口实现：
public static class LongArrayPermable implements Permable<long[]> {
private long[] data;
public LongArrayPermable(long[] data) {
this.data = data;
}
public void swap(int i, int j) {
long temp = data[i]; data[i] = data[j]; data[j] = temp;
}
public long[] copy() {
return data.clone();
}
public int size() {
return data.length;
}
}
public static class CharArrayPermable implements Permable<char[]> {
private char[] data;
public CharArrayPermable(char[] data) {
this.data = data;
}
public void swap(int i, int j) {
char temp = data[i]; data[i] = data[j]; data[j] = temp;
}
public char[] copy() {
return data.clone();
}
public int size() {
return data.length;
}
}
public static class StringPermable implements Permable<String> {
private char[] data;
public StringPermable(String str) {
this.data = str.toCharArray();
}
public StringPermable(char[] data) {
this.data = data;
}
public String copy() {
return new String(data);
}
public int size() {
return data.length;
}
public void swap(int i, int j) {
char temp = data[i]; data[i] = data[j]; data[j] = temp;
}
}
public static class ObjectArrayPermable implements Permable<Object[]> {
private Object[] data;
public ObjectArrayPermable(Object[] data) {
this.data = data;
}
public void swap(int i, int j) {
Object temp = data[i]; data[i] = data[j]; data[j] = temp;
}
public Object[] copy() {
return data.clone();
}
public int size() {
return data.length;
}
}
public static class ListPermable<E> implements Permable<List<E>> {
private List<E> data;
private Class<?> implementation;
public ListPermable(List<E> data, Class<?> listImplementation) {
this.data = data;
this.implementation = listImplementation;
}
public ListPermable(List<E> data) {
this(data, data.getClass());
}
@SuppressWarnings("unchecked")
public List<E> copy() {
if (ArrayList.class == implementation) {
return new ArrayList<E>(data);
} else {
try {
List<E> list = (List<E>) implementation.newInstance();
list.addAll(data);
return list;
} catch (InstantiationException e) {
throw new IllegalStateException(e);
} catch (IllegalAccessException e) {
throw new IllegalStateException(e);
}
}
}
public int size() {
return data.size();
}
public void swap(int i, int j) {
E temp = data.get(i); data.set(i, data.get(j)); data.set(j, temp);
}
}
现在要得到字符串，long数组的排列，可以：
for (long[] a : perm(new LongArrayPermable(new long[]{1, 2, 3}))) {
System.out.println(Arrays.toString(a));
}
for (String a : perm(new StringPermable("abc"))) {
System.out.println(a);
}
它该接口用在非递归版本的排列算法上也很简单，只需要做几处简单的替换就可以了，这里就不列举了，见附件。
参考文章：
全排列算法原理和实现： http://www.blogjava.net/nokiaguy/archive/2008/05/11/199838.html
如何用栈实现递归与非递归的转换： http://www.chinaunix.net/jh/23/331522.html
，这篇文章给我启发，将递归算法转换成非递归算法时需要行画出递归树。
分享到：
相关推荐
递归算法通常与堆栈操作紧密相关，需要理解递归概念、递归实现与堆栈的关系。 7. 分治法是一种常见的算法设计方法，它将问题分解为相互独立的子问题，然后分别求解这些子问题。分治法是许多算法如快速排序、归并...
数据结构与算法是计算机科学的基础，对于理解和设计高效的软件至关重要。在Java编程语言中，学习数据结构和算法有助于提升程序的性能和可维护性。"数据结构与算法java版"这个资源虽然清晰度不高，但内容较为全面，...
数据结构与算法是计算机科学的基础，对于理解和解决复杂问题至关重要。在Java环境下，这些概念的实现使得程序设计更加高效和优化。以下将详细介绍标题和描述中提到的关键知识点： 1. **栈与队列**： - 栈（Stack）...
《算法基础与在线实践》是一本深入浅出的教材，旨在帮助读者理解并掌握算法的基础知识，同时结合实际编程环境，提升算法的在线实践能力。该书内容全面，清晰度高，目录结构分明，便于读者查找和学习。作为一本与Java...
Java数据结构与算法是计算机科学中的基础且至关重要的部分，它们是解决问题和设计高效程序的核心。本书《Java数据结构与算法（第二版）》显然深入探讨了这些主题，旨在帮助读者提升编程技能和理解复杂问题的解决策略...
#### Java与面向对象程序设计：构建算法的基础 在《数据结构与算法（JAVA语言版）》这一资源中，Java作为首选编程语言，其强大的面向对象特性为学习数据结构与算法提供了坚实的基础。Java的特性如封装、继承、多态...
2. **基于归纳的递归：** 通过归纳原理来设计递归算法，即先假设问题的一部分已经被解决，然后基于这部分解决方案来构建整个问题的解决方案。 3. **递推关系求解：** - **求解递推关系的常用方法：** 包括特征方程...
本章节将深入探讨递归的概念、实现原理以及与堆栈的关系，通过基于归纳的递归来理解递归的本质，学习递推关系的求解方法，包括线性齐次递推式、非齐次递推关系的解，以及Master Method的运用。此外，我们还将了解...