β

java组合实现算法

天地一MADAO的个人空间 126 阅读

组合的话原理上比排列简单,我想大一拿C嘎嘎写汉诺塔程序是很常见的,这个原理类似,也是直接交换元素

public class A_private {
	public static void zuhe(char[] all, int times) {
		if (all.length == times) {
			System.out.println(new String(all));
		} else {
			for (int i = times; i < all.length; i++) {
				if (times != i){
					swap(all, times, i);
				}
				zuhe(all, times + 1);
				if (times != i){
					swap(all, i, times);
				}
			}
		}
	}
	private static void swap(char[] a, int x, int y) {
		char temp = a[x];
		a[x] = a[y];
		a[y] = temp;
	}
}

看起来貌似比我排列的程序常,其实除去swap方法,代码量很小

过程我就不用图表示了:↓表示递归前,↑表示递归后,(递归次数,循环次数)

↓(0,0)asd→asd
↓(1,1)asd→asd
↓(2,2)asd→asd
(3)asd
↑(2,2)asd→asd
↑(1,1)asd→asd
↓(1,2)asd→ads
↓(2,2)ads→ads
(3)ads
↑(2,2)ads→ads
↑(1,2)ads→asd
↑(0,0)asd→asd
↓(0,1)asd→sad
↓(1,1)sad→sad
↓(2,2)sad→sad
(3)sad
↑(2,2)sad→sad
↑(1,1)sad→sad
↓(1,2)sad→sda
↓(2,2)sda→sda
(3)sda
↑(2,2)sda→sda
↑(1,2)sda→sad
↑(0,1)sad→asd
↓(0,2)asd→dsa
↓(1,1)dsa→dsa
↓(2,2)dsa→dsa
(3)dsa
↑(2,2)dsa→dsa
↑(1,1)dsa→dsa
↓(1,2)dsa→das
↓(2,2)das→das
(3)das
↑(2,2)das→das
↑(1,2)das→dsa
↑(0,2)dsa→asd

原理和汉诺塔其实是一样的,因为递归后面的步骤其实是还原,最后冗余的3步最明显。


作者:天地一MADAO的个人空间
天地一MADAO的博客
原文地址:java组合实现算法, 感谢原作者分享。

发表评论