全排列递归思路(java)

全排列，full permutation, 经常用于博彩行业。当然我也是一时心血来潮，突然想看看具体如何实现。

这里，我选择递归，因为递归的用法真是多种多样，而且这里正好也反应了一个事实，递归对应着数据结构中的树。

 

根据二叉树的递归遍历，我们认识到了递归的强大，而她的故事也远远不止于此。这里要说的是，二叉树的递归遍历，前中后都简洁的难以置信，但是都有一个共同特点，那就是一个函数里包含两次自身调用。

 

所以，如果一个递归函数中包含了两次自身调用，那么这类问题就是归纳成二分问题。也就是to be or not to be , is the problem。如果一个使用相同手段并且并且每一个点上可分为两种情况的问题，基本都可以转化为递归问题。当然，如果是有三个孩子的树，那么我们可能需要在一个递归函数中调用自身三次。

 

这里的递归，和我们计算阶乘的又有不一样，因为她没有返回，是发散的。也就是从一个节点，发散到N个节点，我们要的结果是叶子节点。

 

计算全排列，我们可以单独拿出每一个元素作为根节点来构成一棵树，所有的可能排列情况就都隐藏在森林中了。现在来看每一颗树，假如4个元素 ， A， B， C， D，以A为根是第一颗，表示以A开头的排列。

那么，第二个位置可以选着 B，C， D，如果我们选择了B，那么B下还有 C， D可以选择， 如果我们选了C，那么最后只剩下D，这样，就列出第一种。如图所示：

 

我们可以看到，这里的孩子个数是递减的，直到最后一个元素，就不用选择了，同时也得到一种可能。

要枚举出所有的，那么就遍历这样一颗树。好了，先上代码。

/**
	 * recursive method, used for the tree traversal.
	 * 
	 * @param inStr
	 *            the elements need to be choose
	 * @param pos
	 *            the position of the elements we choose
	 * @param parentData
	 *            the elements have been chosen
	 */
	public void permutation(String inStr, int pos, StringBuffer parentData) {
		if (inStr.length() == 0) {
			return;
		}
		if (inStr.length() == 1) {
			System.out.println("{" + inStr + "}");
			return;
		}
		// here we need a new buffer to avoid to pollute the other nodes.
		StringBuffer buffer = new StringBuffer();
		// copy from the parent node
		buffer.append(parentData.toString());

		// choose the element
		buffer.append(inStr.charAt(pos));

		// get the remnant elements.
		String subStr = kickChar(inStr, pos);

		// got one of the result
		if (subStr.length() == 1) {
			buffer.append(subStr);
			System.out.println(buffer.toString());
			return;
		}

		// here we use loop to choose other children.
		for (int i = 0; i < subStr.length(); i++) {
			permutation(subStr, i, buffer);
		}

	}

	// a simple method to delete the element we choose
	private String kickChar(String src, int pos) {
		StringBuffer srcBuf = new StringBuffer();
		srcBuf.append(src);
		srcBuf.deleteCharAt(pos);
		return srcBuf.toString();
	}

 

真的很简洁。测试一下。

 

public static void main(String args[]) {
		Permutation p = new Permutation();
		StringBuffer buffer = new StringBuffer();
		String input = "ABCD";
		for (int i = 0; i < input.length(); i++) {
			p.permutation(input, i, buffer);
		}
	}

 

注意，这个方法实际上还不能单独使用，必须使用循环把每一个元素都考虑进去。

或许你还有更简洁的方法。当然，从性能上看，递归不是很好。但是我觉得可以考虑从树上去分析。

好了，有空贴上c版本的。

 C版本：

 http://airu.iteye.com/admin/blogs/1936366

评论

3 楼 airu 2013-08-27  

说道二叉树，只是大家比较熟悉，通过二叉树，推断出递归调用与树的关系。如果在一个函数内调用自身N 次，那就是N 叉树了。

2 楼 airu 2013-08-27  

xugangqiang 写道

请问图示的abcd例子，如何应用到二叉树分析？
这个算法我写过两个版本，但是没有想到使用二叉树的遍历。
这是一个很好的想法。
但是我没有从楼主的代码里面看到二叉树的遍历。

这不是二叉树，兄弟。

1 楼 xugangqiang 2013-08-26  

请问图示的abcd例子，如何应用到二叉树分析？
这个算法我写过两个版本，但是没有想到使用二叉树的遍历。
这是一个很好的想法。
但是我没有从楼主的代码里面看到二叉树的遍历。