论坛 › 编程擂台 › 三重内积的最小值

王守恩 发表于 2025-9-19 01:16:07

三重内积的最小值

A070735——Let r, s, t be three permutations of the set {1, 2, 3, ..., n}; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).
例如：
a(1)=1,1×1×1=1,
a(2)=6,1×2×2+2×1×1=6,
r={1, 2},
s={2, 1},
t={2, 1}.

a(3)=18,1×3×2+2×1×3+3×2×1=18,
r={1, 2, 3},
s={3, 1, 2},
t={2, 3, 1}.

a(4)=44,1×4×3+2×2×2+3×1×4+4×3×1=44,
r={1, 2, 3, 4},
s={4, 2, 1, 3},
t={3, 2, 4, 1}.

a(5)=89,1×5×3+2×2×4+3×3×2+4×1×5+5×4×1=89,
r={1, 2, 3, 4, 5},
s={5, 2, 3, 1, 4},
t={3, 4, 2, 5, 1}.

a(6)=162,1×6×5+2×4×3+3×2×4+4×3×2+5×1×6+6×5×1=162,
r={1, 2, 3, 4, 5, 6},
s={6, 4, 2, 3, 1, 5},
t={5, 3, 4, 2, 6, 1}.

a(7)=271,1×7×5+2×5×4+3×2×6+4×3×3+5×4×2+6×1×7+7×6×1=271,
r={1, 2, 3, 4, 5, 6, 7},
s={7, 5, 2, 3, 4, 1, 6},
t={5, 4, 6, 3, 2, 7, 1}.

a(8)=428,1×8×7+2×5×5+3×3×6+4×4×3+5×6×2+6×2×4+7×1×8+8×7×1=428,
r={1, 2, 3, 4, 5, 6, 7, 8},
s={8, 5, 3, 4, 6, 2, 1, 7},
t={7, 5, 6, 3, 2, 4, 8, 1}.

a(9)=642,——OEIS没有列出相应的 r, s, t。
......
前32项为 1, 6, 18, 44, 89, 162, 271, 428, 642, 930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 9587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773.

a(16)-a(19) from Hiroaki Yamanouchi, Aug 21 2015

a(20) onwards from Martin Fuller, Aug 06 2023

Martin Fuller, Table of n, a(n) for n = 1~204——记住Martin Fuller这个狠角色, 冲到a(204)。

王守恩 发表于 2025-9-19 06:15:59

更进一步，四重内积 A070736——Let r, s, t, u be four permutations of the set { 1, 2, 3, ..., n }; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i)*u(i).

a(1)=1,1×1×1×1=1,
1,
1,
1,
1,

a(2)=8,1×1×2×2+2×2×1×1=8,
1,2,
1,2,
2,1,
2,1,

a(3)=33,1×1×3×3+2×3×1×2+3×2×2×1=33,
1,2,3,
1,3,2,
3,1,2,
3,2,1,

a(4)=96,1×2×3×4+2×1×4×3+3×4×1×2+4×3×2×1=96,
1,2,3,4,
2,1,4,3,
3,4,1,2,
4,3,2,1,

a(5)=231,1×2×4×5+2×3×2×4+3×1×5×3+4×4×3×1+5×5×1×2=231,
1,2,3,4,5,
2,3,1,4,5,
4,2,5,3,1,
5,4,3,1,2,

a(6)=484,1×2×6×6+2×3×3×5+3×5×2×3+4×1×5×4+5×4×4×1+6×6×1×2=484,
1,2,3,4,5,6,
2,3,5,1,4,6,
6,3,2,5,4,1,
6,5,3,4,1,2,

1, 8, 33, 96, 231, 484, 915, 1608, 2664, 4208, 6392, 9392, 13418, 18706, 25540, 34224, 45108, 58588, 75101, 95120, 119179, 147856, 181786, 221648, 268195, 322220, 384588, 456232, 538138, 631362, ——a(100)。

a(11) onwards from Martin Fuller, Aug 06 2023

Martin Fuller, Table of n, a(n) for n = 1..100，——还是这个Martin Fuller 冲到a(100)。

五重内积 A260356：1, 12, 60, 214, 600, 1443, 3089, ——a(7)。——冰火两重天。

六重内积 A260357：1, 16, 108, 472, 1564, 4320, ——a(6)。

七重内积 A260358：1, 24, 198, 1043, 4074, ——a(5)。

八重内积 A260359：1, 32, 360, 2304, 10618, ——a(5)。

九重内积——还没有人计算。

王守恩 发表于 2025-9-19 07:30:14

不能不说——二重内积。

a(1)=1,1×1=1,
1,
1,

a(2)=4,1×2+2×1=4,
1,2,
2,1,

a(3)=10,1×3+2×2+3×1=10,
1,2,3,
3,2,1,

a(4)=20,1×4+2×3+3×2+4×1=20,
1,2,3,4,
4,3,2,1,

a(5)=35,1×5+2×4+3×3+4×2+5×1=35,
1,2,3,4,5,
5,4,3,2,1,

a(6)=56,1×6+2×5+3×4+4×3+5×2+6×1=56,
1,2,3,4,5,6,
6,5,4,3,2,1,

1, 4, 10, 20, 35, 56, 84, 120, 165, 220, 286, 364, 455, 560, 680, 816, 969, 1140, 1330, 1540, 1771, 2024, 2300, 2600, 2925, 3276, 3654, 4060, ——A000292

二重内积——可参考我们的帖子《2025个数码,求最小的45位数》。

王守恩 发表于 2025-9-19 10:10:49

重点还是在主帖。——这些排列是怎么来的。求助！！谢谢！！！

a(1)=1,1×1×1=1,
1,
1,
1,

a(2)=6,1×2×2+2×1×1=6,
1,2,
2,1,
2,1,

a(3)=18,1×3×2+2×1×3+3×2×1=18,
1,2,3,
3,1,2,
2,3,1,

a(4)=44,1×4×3+2×2×2+3×1×4+4×3×1=44,
1,2,3,4,
4,2,1,3,
3,2,4,1,

a(5)=89,1×5×3+2×2×4+3×3×2+4×1×5+5×4×1=89,
1,2,3,4,5,
5,2,3,1,4,
3,4,2,5,1,

a(6)=162,1×6×5+2×4×3+3×2×4+4×3×2+5×1×6+6×5×1=162,
1,2,3,4,5,6,
6,4,2,3,1,5,
5,3,4,2,6,1,

a(7)=271,1×7×5+2×5×4+3×2×6+4×3×3+5×4×2+6×1×7+7×6×1=271,
1,2,3,4,5,6,7,
7,5,2,3,4,1,6,
5,4,6,3,2,7,1,

a(8)=428,1×8×7+2×5×5+3×3×6+4×4×3+5×6×2+6×2×4+7×1×8+8×7×1=428,
1,2,3,4,5,6,7,8,
8,5,3,4,6,2,1,7,
7,5,6,3,2,4,8,1,

a(9)=642,1×9×8+2×5×7+3×4×6+4×6×3+5×7×2+6×3×4+7×2×5+8×1×9+9×8×1=642,
1,2,3,4,5,6,7,8,9,
9,5,4,6,7,3,2,1,8,
8,7,6,3,2,4,5,9,1,

a(10)=930,
a(11)=1304,
a(12)=1781,
a(13)=2377,

OEIS 没有列出相应的 r, s, t。

王守恩 发表于 2025-9-19 16:49:11

好不容易搞了个a(10)≤931, 离正确答案930还差1。

a(10)=931,1×10×9+2×6×8+3×4×7+4×5×5+5×7×3+6×8×2+7×3×4+8×2×6+9×1×10+10×9×1=931,
01,2,3,4,5,6,7,8,09,10,
10,6,4,5,7,8,3,2,01,09,
09,8,7,5,3,2,4,6,10,01,

mathe 发表于 2025-9-19 17:14:42

这个问题关键是排列不等式和平均不等式。
3个1-n的排列，其中每组第一个数，我们不妨假设从1-n顺序排列。
由于这3n个数的乘积是\((n!)^3\),根据平均不等式，最终结果\(\ge n\sqrt{(n!)^3}\), 这n组乘积相互之间越接近，结果应该越靠近这个下界。
于是我们应该尽量让每组三个数的乘积靠近几何平均\(\sqrt{(n!)^3}\),这个值可以通过Stirling公式计算。
于是对于第一组，我们应该尽量优先搜索另外两个数的乘积接近\(\frac{\sqrt{(n!)^3}}n\)的组合，
   而设定第一组的数以后，我们同样可以直到余下数的几何平均，并且估计第二另外两个数的理想乘积结果，并且优先搜索考虑这个乘积的组合，等等
。。。
而在找到一些比较优秀的结果以后，每次搜索到一定的步骤，我们均可以利用平均不等式计算余下数能够构成乘积的理论下界，如果发现这个理论下界对应的情况已经比当前已经找到的最优结果差了，就可以直接剪枝，不继续搜索了，通过这种剪枝，可以大幅度降低搜索空间。

另外由于上面搜索过程我们会大量用到两个数乘积的排序结果，可以先将所有两个数的乘积结果进行排序，然后每次得到当前一个期望的理想乘积结果以后，就可以使用二分法找到这个结果在排序数列中对应位置，然后从中间像两边开始进行枚举，并且跳过那些部分数字已经被使用的组合即可。当然这种方案对于越前面的组越有效。

另外要求搜索顺序为顺序排列的一个理由是由于平均值\(\sqrt{(n!)^3}\approx \frac{n^3}{e^3}\), 第一个数字为1的化，对于稍微大一点的n,基本上会要求另外两个数的乘积越大越好，搜索复杂度比较小，可以大大降低搜索复杂度

mathe 发表于 2025-9-19 17:39:32

以n=8为例子，那么第一组面临平均数约为53.3，所以另外两个数只能选择7*8最接近，所以优先尝试
1*7*8, 然后余下7组平均数调整为52.9，所以除了2，余下两个数乘积需要接近26.5，优先考虑4*7或5*5
对于1*7*8+2*5*5,第3组余下两个数乘积需要接近20.0，由于两组都已经使用了5，不能使用5*4，所以优先考虑3*7,然后考虑3*6，可以先分析
1*7*8+2*5*5+3*3*7 （需要注意中间数字已经使用7,所以新的7只能放在最后），
然后下一轮余下两数期望乘积为12.9, 优先考虑12=2*6 （3*4中3已经被使用), 得到
1*7*8+2*5*5+3*3*7+4*2*6或 1*7*8+2*5*5+3*3*7+4*6*2
然后下一轮两数乘积期望10.55 （不能使用10=2*5,12=3*4,)可以尝试12=6*2,得到
1*7*8+2*5*5+3*3*7+4*2*6+5*6*2或 1*7*8+2*5*5+3*3*7+4*6*2+5*2*6，两组本质相同，以前一个为例子
中间数字余下{1,4,8},右边数字余下{1,3,4}
下一轮两数乘积期望为8.4,所以可以选择8*1，得到
1*7*8+2*5*5+3*3*7+4*2*6+5*6*2+6*8*1
最后两轮得到1*7*8+2*5*5+3*3*7+4*2*6+5*6*2+6*8*1+7*4*3+8*1*4=441，已经是一个比较靠近最优结果428的结果了。
当然对1*7*8结果遍历结束必然能够搜索到428.
然后比如我们查看假设第一组是1*7*6， 那么余下7组理论平均值可以算出为55.19，对应7组和386.37，加上1*7*6=42为428.37>428，所以我们会发现1*7*6可以直接裁剪，完全不需要搜索。

northwolves 发表于 2025-9-19 21:04:57

01        2        3        4        5        6        7        8        09        10
10        6        4        8        5        3        7        2        01        09
09        7        8        3        4        5        2        6        10        01

s = {{01, 2, 3, 4, 5, 6, 7, 8, 09, 10}, {10, 6, 4, 8, 5, 3, 7, 2, 01,09}, {09, 7, 8, 3, 4, 5, 2, 6, 10, 01}}; Times@@s//Total
930

王守恩 发表于 2025-9-20 12:28:28

northwolves 发表于 2025-9-19 21:04
01        2        3        4        5        6        7        8        09        10
10        6        4        8        5        3        7        2        01        09
09        7        8        3        4        5        2        6        10        01

鹦鹉学舌,没学好。 离正确答案总是差1。

a(11)=1305,1*11*10 + 2*7*9 + 3*5*8 + 4*6*5 + 5*9*3 + 6*3*6 + 7*4*4 + 8*8*2 + 9*2*7 + 10*1*11 + 11*10*1=1305, 正确答案=1304。
01,2,3,4,5,6,7,8,9,10,11,
11,7,5,6,9,3,4,8,2,01,10,
10,9,8,5,3,6,4,2,7,11,01,

a(12)=1782,1*12*11 + 2*8*10 + 3*6*9 + 4*7*5 + 5*10*3 + 6*4*7 + 7*5*4 + 8*9*2 + 9*3*6 + 10*2*8 + 11*1*12 + 12*11*1=1782, 正确答案=1781。
01,02,3,4,05,6,7,8,9,10,11,12,
12,08,6,7,10,4,5,9,3,02,01,11,
11,10,9,5,03,7,4,2,6,08,12,01,

a(13)=2378,1*13*12 + 2*8*11 + 3*7*10 + 4*11*4 + 5*5*8 + 6*6*5 + 7*9*3 + 8*4*6 + 9*3*7 + 10*10*2 + 11*2*9 + 12*1*13 + 13*12*1=2378, 正确答案=2377。
01,02,03,04,5,6,7,8,9,10,11,12,13,
13,08,07,11,5,6,9,4,3,10,02,01,12,
12,11,10,04,8,5,3,6,7,02,09,13,01,

northwolves 发表于 2025-9-20 12:55:46

王守恩 发表于 2025-9-20 12:28
鹦鹉学舌,没学好。 离正确答案总是差1。

a(11)=1305,1*11*10 + 2*7*9 + 3*5*8 + 4*6*5 + 5*9*3 + 6*3 ...

s={{01,2,3,4,5,6,7,8,9,10,11}, {11,7,5,6,8,3,9,4,2,01,10}, {10,9,8,5,3,6,2,4,7,11,01}};Times@@s//Total

查看完整版本: 三重内积的最小值