排列组合算法1：生成全部有序列

生成长度为N的全部有序列(n-tuples)

同样的图添加到MSN后： 。什么世道！），常遇到的话题之一是怎么生成一个有序列的所有组合，一个集合的所有子集（幂集），或者所有的全排列。一些论坛上也常出现类似的问题。很有意思的话题。在编程中时不时要遇到之外，也是锻炼大脑防止老年痴呆的上佳练习材料，尤其适合好静坐，喜油条， 30岁以上从不上健身房的程序员。不用左右看了。就是老大您！做这类题目还有个好处：重温当年写小程序的快乐。不知道多少人会享受搭建工资管理系统的全过程，津津有味地调试奇形怪状的API，反复修改庞杂的XML配置文件。反正我不会。写小程序就不同了。没有最后期限的压力，不用担心系统的羁绊，无需顾虑程序的架构。可以纠缠算法的每一个细节，也可以执着于提高代码的每一分性能。施主随喜。心智澄明，目光通透，心随意动，运指如飞。敲下的字符直切问题要害，摧枯拉朽。层层屏障随着代码的延伸支离破碎。写小程序解谜题的过程，就好像懵懂小孩儿扎堆游戏，纯粹为了好玩儿。一晃眼，一下午过去。他们满身泥浆，精疲力尽。但他们眼神依然兴奋，依然盼望下一次游戏。嗯，今年不收礼，收礼只收智力题。

一个N-tuple是一个包含N个元素的序列，一般写作 。比如说 就是一个6-tuple。注意tuple和集合的区别。Tuple里可以包含重复的元素。而且Tuple的元素是有序的，就跟数组的元素一样。

那么给定一个N-tuple, ，我们怎么生成全部有序列呢？由简入繁总是学习的不二法门。所以我们从简单的二进制N元有序列（binary n-tuple）开始：二进制N元有序列的每个元素都是一个bit，非0即1。比如说一个二进制3-tuple，生成的全部有序列为

一共8个。二进制N元有序列虽然简单，却已经有了广泛的用途。比如说知道怎么生成二进制N元有序列，我们也就知道怎么生成幂集：一个N元集合 ，我们规定 属于于一个子集，当且仅当对应的二进制N元有序列的元素 。用上面的3－tuple作例子。给出一个集合 ，则

生成全部二进制N元有序列的方法再简单不过：我们从二进制数 开始，逐次加一，直到得到 为止。利用进位加法，我们刚好遍历了所有的N-tuples。简单，但是美妙。代码用Ruby实现的。因为Ruby的代码和伪代码差别不大，会不会Ruby的老大都可以看懂。再说算法就是算法。无所谓那门语言。学算法时非找到《XXX语言算法》，纯属无聊。

defbinary_all_tuples(tuple_length)
tuple=Array.new(tuple_length,0)

loopdo
putstuple.inspect

j=tuple_length-1
whiletuple[j]==1do
tuple[j]=0
j-=1
end

returnifj==-1
tuple[j]+=1
end
end

我们知道循环一共进行了 次。所以我们不用每次判断j的值。不过这是细节，无关主旨。

def binary_all_tuples_2(tuple_length)
 tuple = Array.new(tuple_length, 0)

1.upto(1<<tuple_length) do |i|
 puts tuple.inspect 
 j = tuple_length - 1

 while tuple[j] == 1 do
 tuple[j] = 0
 j -= 1
 end 

 tuple[j] += 1 
 end
end

def each_tuple(tuple_length=0, &proc)
 tuple = Array.new(tuple_length, 0)

 loop do
  yield tuple 

 j = tuple_length - 1
  while tuple[j] == 1 do
 tuple[j] = 0
 j -= 1
 end 
 return if j == -1

 tuple[j] += 1
  end
end

require ’set’
def powerset(set = [])
each_tuple(set.size) do |tuple|
 puts “tuple: #{tuple.inspect}” 

 subset = []
  tuple.each_index do |index|
 subset << set[index] if tuple[index] == 1
 end 

 puts subset.inspect
 end
end

这么简单的算法也有精彩的引申。比如说，我们可以把二进制扩展到10进制。十进制的N-tuple: 里， 。所以我们只需要把 逐步递加到 。我们还能进一步总结，处理多进制序列。也就是说，n元序列里的任意元素 的进制是 ，用公式表达为:

对不同的 , 不一定相同。本质上，生成全序列的方法并没有改变。我们现在只需要对混合进制的数执行累加。这个混合进制的数可以写为：

累加的算法仍然直观：对满足条件(1)的混合进制序列，我们不断在公式（2）里的数上累加1。进位规则与以前统一进制的进位规则没有本质区别。在第 位时，加到 再进位就行了。

def all_tuples(radix_list = [])
 tuple_length = radix_list.size
 tuple = Array.new(tuple_length, 0) 

 loop do
 puts tuple.inspect 

 j = tuple_length - 1
 while tuple[j] == radix_list[j] -1 do
 tuple[j] = 0
 j -= 1
 end



 return if j == -1

 tuple[j] += 1
 end
end

公式(3)里的 表示空字串， 表示把序列 里每一个字串前加一个0，组成新的序列，而 则表示把序列 翻转，然后把里面每一字串前置一个1，形成新的序列。看看前N = 3的情况：

n = 0 ，我们得到空序列

n = 1, ，所以我们得到唯一的格雷码：0, 1

n = 2, = 0(0, 1), 1(1, 0) = 00, 01, 11, 10

n = 3, = 0(00, 01, 11), 1(11, 01, 00) = 000， 001， 011， 111， 101， 000 直观上也好理解，所有序列都是从无到有搭建起来的。所以 和 里所有字串都是符合格雷码定义――相邻字串相差一位。而 的最后一个字串刚好等于 的第一个字串，所以分别加上0和1后， 的最后一个字串和 刚好相差一位。有了直观的概念，归纳法证明近乎琐碎（本来公式就是用来表达我们的直观思想的）。前面的例子可算初始条件，假设 是格雷码，下面的步骤不用写出来了吧？因为公式（3）是递归定义，我们能直接把它转换成代码：

def gray_rec(n)
 return [] if n == 0
 return [“0″,“1″] if n == 1

 partial = gray_rec(n-1) 

 return partial.collect{ |e| “0″+e} + partial.reverse.collect{|e|“1″+e}
end

def gray_rec_helper(count, max, partial_result)
 return [] if max == 0
 return partial_result if count == max

 return gray_rec_helper(count+1,
 max, 
        partial_result.collect{ |e| “0″+e}+ partial_result.reverse.collect{ |e| “1″+e})
end

def tail_gray(n)
 return gray_rec_helper(1, n, [“0″,“1″])
end