o*d
发帖数: 72 | 1 打算用matlab写一个小程序，但是没什么经验。
大概就是说，从1到3n这么多数字的集合，有一个从幂集到正实数的函数f
事先把这3n个数3等分组，这个函数是只依赖于该子集里各组成员个数的
比如f(A)=k_1*b_1+k_2*b_2+k_3*b_3, b_i是固定常数（整数即可），
k_i是这个子集A里包含的各组成员个数，从小到大排列
然后具体要做的就是随便固定一个数字g \in{1..,3n}.
遍历所有(3n)!个，分别计算f(A&g)-f(A),
A是该排列里位于g之前的元素子集（不考虑顺序），求和，最后取平均。
之后想做的就是调整n和b_i，能测试个十几组就够了。
不过也有可能要看情况check(4n)甚至(5n)的相应case。
想问的就是：
1.如果n会取到接近10甚至更高，会不会过于耗时？比如要run 30!次甚至更高。
有没有可能简化公式？因为函数本身还是很规律性的。
比如像对于任意两个排列，只要g之前的所有元素是一样的子集A,f(A&g)-f(A)的结果就
一样。
2.对结果精确度要求并不高，用随机模拟是否可行？或者是近似公式？
谢谢谢谢！ |
d*****u
发帖数: 17243 | 2 你所说的“把这3n个数3等分组”是什么意思
是分成元素个数相同的三组？那k又是什么意思
你最好把要问的问题简化成更简单的等价数学问题
然后再来想算法
【在 o*d 的大作中提到】
: 打算用matlab写一个小程序，但是没什么经验。
: 大概就是说，从1到3n这么多数字的集合，有一个从幂集到正实数的函数f
: 事先把这3n个数3等分组，这个函数是只依赖于该子集里各组成员个数的
: 比如f(A)=k_1*b_1+k_2*b_2+k_3*b_3, b_i是固定常数（整数即可），
: k_i是这个子集A里包含的各组成员个数，从小到大排列
: 然后具体要做的就是随便固定一个数字g \in{1..,3n}.
: 遍历所有(3n)!个，分别计算f(A&g)-f(A),
: A是该排列里位于g之前的元素子集（不考虑顺序），求和，最后取平均。
: 之后想做的就是调整n和b_i，能测试个十几组就够了。
: 不过也有可能要看情况check(4n)甚至(5n)的相应case。
|
o*d
发帖数: 72 | 3 是我没说清
3等分就是你说的意思，比如A组1~n，B组n+1~2n，C组剩下的
然后其实是说事先给定一个从任一子集到正实数的对应
这个对应依赖于这个子集里包含各组成员个数，
比如挑出12个元素的子集，5个A组的，7个B组的，k_1=5，k_2=7之类的
如果是全排列遍历，直接写程序应该很容易，我就怕没法控制时间。
自己也在想有没有从计算本身化简的方法，
还有就是希望能请教一下什么样的编程技巧可以用上提高效率
（比如用移位，矩阵计算之类的）
【在 d*****u 的大作中提到】
: 你所说的“把这3n个数3等分组”是什么意思
: 是分成元素个数相同的三组？那k又是什么意思
: 你最好把要问的问题简化成更简单的等价数学问题
: 然后再来想算法
|
D***r
发帖数: 7511 | 4 那对于某一个排列，F(A&g)和F(A)的差别就在于前者的输入里多一个元素g？
那如果知道g是哪一组的，那差值不就始终是b_i中相应的那一个吗？
估计是哪里理解错了
【在 o*d 的大作中提到】
: 是我没说清
: 3等分就是你说的意思，比如A组1~n，B组n+1~2n，C组剩下的
: 然后其实是说事先给定一个从任一子集到正实数的对应
: 这个对应依赖于这个子集里包含各组成员个数，
: 比如挑出12个元素的子集，5个A组的，7个B组的，k_1=5，k_2=7之类的
: 如果是全排列遍历，直接写程序应该很容易，我就怕没法控制时间。
: 自己也在想有没有从计算本身化简的方法，
: 还有就是希望能请教一下什么样的编程技巧可以用上提高效率
: （比如用移位，矩阵计算之类的）
|
