差三角

chyanog

9# hujunhua
1-21和1-28的穷举后发现似乎不存在

chyanog

这个稍快

1. 
   
2. n = 5;
   
3. Join @@ NestList[Abs@Differences@# &, {a, b, c, d, e}, n - 1]
   
4. table = Table[%, {a, #}, {b, #}, {c, #}, {d, #}, {e, #}] &[ n (n + 1)/2]~Flatten~(n - 1);
   
5. fmt = MatrixForm@Internal`PartitionRagged[Reverse@#, Range[n]] &;
   
6. Do[If[Unequal @@ i, If[(And @@ Positive /@ i), Print@fmt@i]], {i,  table}] // Timing
   
7. Clear["`*"]
   

复制代码

gxqcn

今天白天本想跟帖说：这是一个非常适合编程擂台的题目，
现在打开居然已经有代码了。

hujunhua

12#的代码中第3行人工生成的table大小为15^5, 用排列函数，代码和结果都可略有优化。

1. n = 5; m = n (n + 1)/2;
   
2. f = Abs@Differences@# &;
   
3. Flatten@NestList[f, #, n - 1] &
   
4. table =% /@ Permutations[Range[m], {n}];
   
5. fmt = MatrixForm@Internal`PartitionRagged[Reverse@#, Range[n]] &;
   
6. Do[If[Unequal @@ i, Print@fmt@i], {i, table}] // Timing

复制代码

试了一下，第3行用Flatten比Join约快1倍。

chyanog

14# hujunhua
不过这个总运行时间反而长了，应该还能够优化

hujunhua

在我的电脑上，
12#的时间最快的为2.230814
14#的时间最快的为0.998406
--------------------------------------------------------
是的，上述时间都不是总时间，总时间14#慢些。14#生成排列表很快，但随后又对排列表进行操作生成table耗费了大量时间。

chyanog

这个版本速度有了较大提升，不过牺牲一些可读性

1. 
   
2. t1 = AbsoluteTime[];
   
3. n = 5;
   
4. k = n (n + 1)/2;
   
5. cf = Compile[{{ls, _Integer, 1}},
   
6.      #[ls],
   
7.      RuntimeAttributes -> {Listable}
   
8.      ] &[Evaluate[
   
9.       Flatten@NestList[Abs@Differences@# &, Array[Slot, n],
   
10.         n - 1]] & /. Slot[x_] :> #[[x]]];
    
11. table = cf@Permutations[Range[k], {n}];
    
12. fmt = MatrixForm@Internal`PartitionRagged[Reverse@#, Range[n]] &;
    
13. Do[If[Unequal @@ i, Print@fmt@i], {i, table}]
    
14. AbsoluteTime[] - t1
    
15. Clear["`*"]
    

复制代码

chyanog

13# gxqcn
我写的C代码太难看了，中间比较长的部分还是mathematica生成的，

wayne

18# chyanog

mathematica生成？

有才，我还没这么玩过呢

chyanog

19# wayne
其实没什么技术含量的。1-21和1-28的差三角似乎不存在，更大的就不清楚了

1. 
   
2. xx = Table[Symbol["x" <> ToString[i]], {i, 15}]
   
3. StringReplace[
   
4. xx == (ToLowerCase@ToString@CForm@# & /@
   
5.       Join @@ NestList[Abs@Differences@# &, {a, b, c, d, e}, 4]) //
   
6.    Thread // ToString, {"," -> ";", "{" | "}" -> "", "==" -> "="}]
   
7. 
   
8. LogicalExpand[Unequal @@ xx]
   
9. And @@ Thread[xx > 0]
   
10. "" <> Table["%d ", {15}]
    

复制代码