一个排列组合问题
用1到9这些数字各一次任意组成整数集合，其中所有的整数都是素数，比如{2,3,5,7,14689}，计算所有组合的个数（比如{2,3,5,7,14689}和{14689,2,3,5,7}被视作同一个组合）
很快就能想到最简单的暴力破解算法：
1.得到［1，2，3，4，5，6，7，8，9］的所有排列，有9！种可能
2.对每一种排列方式组合出所有的“分割”方法，比如[1,2,3]可以得到[ [1,2,3],[1,23],[12,3],[123] ]，有2^(array.length-1)种可能（递归即可）
3.对每一种分割进行判断，由于要排除重复的组合，可以排除掉非递增的数列，比如对于[1,2,3]的4种分割需要排除掉[12,3]（因为这个组合可以在[3,1,2]的分割里面被计算到），然后每个组合依次判断素性，如果遇到非素数就跳过，全部是素数则命中一次
ruby实现这个算法很快，但通过打印中间值来测试，至少要跑20分钟才能有结果，所以需要其他途径解决。
考虑了几天得到另外一个途径。本质还是排列组合加分割的思想：
1.考虑集合的组成特点，可以把问题看作是将9分割成为不同的和（比如可以是1个一位素数加1个八位素数，也可以是1个两位素数加1个七位素数），每个加数对应一个素数的位数，先找出所有9的加法分解方法（由于1到9组成的9位数只能是合数，以及一位的素数只有4个，所以可以排除掉这些分解方法），然后对每个分解方法做统计，比如将[1,1,1,6]（3个一位素数和1个六位素数）转化为[ [1,3],[6,1] ]
def sum_way(n)
res = [ [n] ]
(n/2).times do |nn|
res += sum_way(n-nn-1).map{|x|x+[nn+1]}
end
res.map{|x|x.sort}.uniq
end
sum_nine = sum_way(9).reject{|x|x.length==1 || x.count(1)>4}.map{|x|x.map{|y|[y,x.count(y)]}.uniq}
2.计算所有8或更低位数不包含重复数字的素数（同上，因为9个数字组成一个数只能是合数，所以不考虑），并且按其位数分开存起来，总共有43089个。Interger#prime?就是增加了一个简单的判别方法用（3..Math.sqrt(self).to_i).step(2)去除self
primes = {}
（1..8）.each do |n|
primes[n] = []
(1..9).to_a.combination(n).each do |an|
an.permutation.each do |anp|
primes[n] << anp.join.to_is if anp.join.to_i.prime?
略
3.最后一步遇到了一点实现上的障碍，几乎花了一整天来调试。
对于每一种9的加法分解，映射为对应的素数组成，然后根据步骤2里面存储的结果进行组合判断,比如对于[ [2,3],[3,1] ]这种分解，可以生成一个数组tmp =
[ [primes[2].combination(3).to_a.reject{|x|array_same_digit?(x)}],primes[3].combination(1).to_a.reject{|x|array_same_digit?(x)}] ]
主要是排除在相同位数的素数中取多个时有相同数字的情况（自己定义了一个方法判断数组里的数是否有相同数字,比如[23,29,31]是true，而[19,23,47]是false）。
然后对tmp[0]这个数组依次遍历，和tmp[1]的每个数比较，如果有相同数字则排除，否则保留。由于tmp数组的长度不定（可以是2，比如1+8，也可以是3,比如1+1+7），所以需要使用一个递归来遍历tmp，直到进入tmp[-1]，可以直接返回排除后的长度计数。并且在递归中记录已经出现过的数字。
在写这个方法时发现了一个feature，比如a=[1,2,3]，a[3]，a[4]，a[4,10]均返回nil，但a[3,10]返回[]
def distinct(a,d)
if a.length == 1
a[0].reject{|x|same_digit?(x.join.to_i,d)}.length
else
res = 0
a[0].each do |aa|
next if same_digit?(aa.join.to_i,d)
tmpd = (aa.join+d.to_s).to_i
res += distinct([a[1].reject{|x|same_digit?(x.join.to_i,tmpd)}]+a[2,10],tmpd)
end
res
end
end
其中a对应tmp数组，d负责记录已出现数字，same_digit?(a,b)用于判断a和b两个数是否有相同数字，array_same_digit?也基于这个自定义方法
这种方法用ruby可以15秒跑出答案（得到素数集合需要10秒）。最后实际测试了一下第一种方法大概需要25分钟。（但据说如果用西加加的话，第一种方法只需要30秒……）于是我有了一种作死的感觉。
综上所述：珍爱生命，莫要作题（si）
很快就能想到最简单的暴力破解算法：
1.得到［1，2，3，4，5，6，7，8，9］的所有排列，有9！种可能
2.对每一种排列方式组合出所有的“分割”方法，比如[1,2,3]可以得到[ [1,2,3],[1,23],[12,3],[123] ]，有2^(array.length-1)种可能（递归即可）
3.对每一种分割进行判断，由于要排除重复的组合，可以排除掉非递增的数列，比如对于[1,2,3]的4种分割需要排除掉[12,3]（因为这个组合可以在[3,1,2]的分割里面被计算到），然后每个组合依次判断素性，如果遇到非素数就跳过，全部是素数则命中一次
ruby实现这个算法很快，但通过打印中间值来测试，至少要跑20分钟才能有结果，所以需要其他途径解决。
考虑了几天得到另外一个途径。本质还是排列组合加分割的思想：
1.考虑集合的组成特点，可以把问题看作是将9分割成为不同的和（比如可以是1个一位素数加1个八位素数，也可以是1个两位素数加1个七位素数），每个加数对应一个素数的位数，先找出所有9的加法分解方法（由于1到9组成的9位数只能是合数，以及一位的素数只有4个，所以可以排除掉这些分解方法），然后对每个分解方法做统计，比如将[1,1,1,6]（3个一位素数和1个六位素数）转化为[ [1,3],[6,1] ]
def sum_way(n)
res = [ [n] ]
(n/2).times do |nn|
res += sum_way(n-nn-1).map{|x|x+[nn+1]}
end
res.map{|x|x.sort}.uniq
end
sum_nine = sum_way(9).reject{|x|x.length==1 || x.count(1)>4}.map{|x|x.map{|y|[y,x.count(y)]}.uniq}
2.计算所有8或更低位数不包含重复数字的素数（同上，因为9个数字组成一个数只能是合数，所以不考虑），并且按其位数分开存起来，总共有43089个。Interger#prime?就是增加了一个简单的判别方法用（3..Math.sqrt(self).to_i).step(2)去除self
primes = {}
（1..8）.each do |n|
primes[n] = []
(1..9).to_a.combination(n).each do |an|
an.permutation.each do |anp|
primes[n] << anp.join.to_is if anp.join.to_i.prime?
略
3.最后一步遇到了一点实现上的障碍，几乎花了一整天来调试。
对于每一种9的加法分解，映射为对应的素数组成，然后根据步骤2里面存储的结果进行组合判断,比如对于[ [2,3],[3,1] ]这种分解，可以生成一个数组tmp =
[ [primes[2].combination(3).to_a.reject{|x|array_same_digit?(x)}],primes[3].combination(1).to_a.reject{|x|array_same_digit?(x)}] ]
主要是排除在相同位数的素数中取多个时有相同数字的情况（自己定义了一个方法判断数组里的数是否有相同数字,比如[23,29,31]是true，而[19,23,47]是false）。
然后对tmp[0]这个数组依次遍历，和tmp[1]的每个数比较，如果有相同数字则排除，否则保留。由于tmp数组的长度不定（可以是2，比如1+8，也可以是3,比如1+1+7），所以需要使用一个递归来遍历tmp，直到进入tmp[-1]，可以直接返回排除后的长度计数。并且在递归中记录已经出现过的数字。
在写这个方法时发现了一个feature，比如a=[1,2,3]，a[3]，a[4]，a[4,10]均返回nil，但a[3,10]返回[]
def distinct(a,d)
if a.length == 1
a[0].reject{|x|same_digit?(x.join.to_i,d)}.length
else
res = 0
a[0].each do |aa|
next if same_digit?(aa.join.to_i,d)
tmpd = (aa.join+d.to_s).to_i
res += distinct([a[1].reject{|x|same_digit?(x.join.to_i,tmpd)}]+a[2,10],tmpd)
end
res
end
end
其中a对应tmp数组，d负责记录已出现数字，same_digit?(a,b)用于判断a和b两个数是否有相同数字，array_same_digit?也基于这个自定义方法
这种方法用ruby可以15秒跑出答案（得到素数集合需要10秒）。最后实际测试了一下第一种方法大概需要25分钟。（但据说如果用西加加的话，第一种方法只需要30秒……）于是我有了一种作死的感觉。
综上所述：珍爱生命，莫要作题（si）
