关于可重排列的面试题一道

• 计算 1, 2, 3 的和为 N 的一个可重组合
• 输出这个组合的所有排列

# coding:utf-8
$size = 0

# 把 n个1, m个2，l个3 的所有排列附加到 s 的后面输出
def out s, n, m, l
  if (n == 0 and m == 0 and l == 0)
    $size += 1
    puts s
    return
  end
  out "#{s}1", n - 1, m, l if n > 0
  out "#{s}2", n, m - 1, l if m > 0
  out "#{s}3", n, m, l - 1 if l > 0
end

# 寻找和为 sum 的 1, 2, 3 的可重组合
def out_steps sum
  # sum = 3l + 2m + n
  0.upto sum / 3 do |l|
    rest = sum - l * 3
    0.upto rest / 2 do |m|
      n = rest - m * 2
      out '', n, m, l
    end
  end
end

out_steps ARGV[0].to_i
$stderr.puts "total:#$size"

$ time ruby perm.rb 23 > res.txt
total:755476

real    0m3.878s
user    0m0.000s
sys     0m0.016s

$ time ruby perm.rb 30 > res.txt
total:53798080

real    4m42.528s
user    0m0.000s
sys     0m0.030s

# coding:utf-8
# 设 n 级台阶的走法为 f(n) 种，容易知道：
# f(n) = f(n-1) + f(n-2) + f(n-3)
def f n
  a = 1, 2, 4, 7
  4.upto n do
    a << (a[-1] + a[-2] + a[-3])
  end
  return a[n - 1]
end
puts f 23 #=> 755476
puts f 30 #=> 53798080

我觉得只要用树来展开一下就可以了，而且更简洁：

import java.util.Stack;

public class StepCompositor {

	private Stack<String> steps = new Stack<String>();

	public void printSteps(int n) {
		if (n == 1) {
			printStack("1");
			return;
		} else if (n == 2) {
			printStack("1 1");
			printStack("2");
			return;
		} else if (n == 3) {
			printStack("1 1 1");
			printStack("1 2");
			printStack("2 1");
			printStack("3");
			return;
		} else if (n <= 0) {
			return;
		}

		for (int i = 1; i <= 3; i++) {
			steps.push("" + i);  //存放路径节点
			printSteps(n - i);  //展开节点
			steps.pop();
		}
	}

	private void printStack(String tail) {
		for (String s : steps)
			System.out.print(s + " ");
		System.out.println(tail);
	}

	public static void main(String[] args) {
		new StepCompositor().printSteps(5);
	}

}

一共打印出了13种，测试了23步台阶的情况下效率还是很高的，在控制台打印的话开销会很大。

我在笔记本上试了一下用Java写的输出结果到硬盘上的代码，求30步台阶的时候也用了4分40秒左右，看来瓶颈都在硬盘了，看不出效率。我改了一下“打印”的代码：

private String printStack(String tail) {
	String r = "";
	for (String s : steps)
		r = s;
	r = tail;
	return r;
}

 求30步台阶用了75秒左右，不知道LZ的Ruby代码，如果不输出到硬盘上的话，大概得用了多长时间 我想了解一下Java递归的效率，我的机器是Core i3 330M的笔记本。

# coding: utf-8

# 缓存 1..3
Cache = [
  [], %w[1], %w[11 2], %w[111 12 21 3]
].each {|a| a.each { |s| s << "\n" } }

# 缓存 4..15
12.times {
  Cache << [1, 2, 3].flat_map {|i|
    Cache[-i].map {|s| "#{i}#{s}" }
  }
}

def print_steps s, n
  if ts = Cache[n]
    ts.each {|t| print s, t }
    return
  end
  1.upto(3) {|i| print_steps "#{i}#{s}", n - i }
end

print_steps "", ARGV[0].to_i

C = [ [], %w[1], %w[11 2], %w[111 12 21 3] ]
N = ARGV[0].to_i
4.upto N do
  C << [1, 2, 3].flat_map {|i| C[-i].map {|s| "#{i}#{s}" } }
end
puts C[N]

C = [ [], %w[1], %w[11 2], %w[111 12 21 3] ]
N = ARGV[0].to_i
4.upto N do
  C << [1, 2, 3].flat_map {|i| C[-i].map {|s| "#{i}#{s}" } }
end
puts C[N]

好难看懂