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

一个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语言算法》，纯属无聊。 

def binary_all_tuples(tuple_length)
  tuple = Array.new(tuple_length, 0)
    
  loop do
    puts tuple.inspect 

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

    return if j == -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