差三角

chyanog

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

chyanog

这个稍快

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

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

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的差三角似乎不存在，更大的就不清楚了

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, {"," -> ";", "{" | "}" -> "", "==" -> "="}]
8. LogicalExpand[Unequal @@ xx]
9. And @@ Thread[xx > 0]
10. "" <> Table["%d ", {15}]

复制代码