calculator_of_Onmyoji
calculator_of_Onmyoji copied to clipboard
jiajunsu
关于result_combinations，我觉得可以不用遍历所有
比如我自己的所有针女荒骷髅套组合，暴击从+85到+95，最后算下来2w6，26000C2有3亿组合，太长了。 \ 但是在excel里筛选一下就发现能用的6号位就5个，4号位也是个位数，其实每个位置都没有用到多少，所以我大致想了一下：\
- 每号位的每个御魂建一个set，里面是用到这个御魂的组合序号。
- 遍历所有组合（指的是2w6的直接御魂结果，不是3亿多的那个排列组合），对每个组合的6个位置，用全集减掉6个位置的set，得到的差集就是不重复的御魂组合，直接输出对应行就行了。
其他问题：
- 算2套时大概是O(n)吧，剩下都是调包操作也没多大，可能需要点内存有待商確。
- 算>2套时可能会有写逻辑问题，没细想。
我打了个草稿用来算所有组合，字比较丑凑乎看
思路就是先算2套独立，然后根据2独立的结果去算3独立，再直到n独立。
- 这样应该是$O(n_expect*combo_num)$,应该还是不慢的。就是集合运算本身可能不那么快。
- 内存的话，现在这种算一半也是崩，如果始终保持只打开一个大文件应该是够的
- 可能不能用dict?不知道dict value能不能是set
附议，现在计算量太大了，基本上都跑不出来。 建议是让用户输入最大尝试的套装数，程序就从2套开始计算，迭代到n套，其中2套计算完后也保存下来，这样也不浪费这次计算。
另外，从第3套开始，应该是用 第2套＋第1套 拼接而来；第4套是从第3套＋第1套拼接而来。
我自己尝试了半天，因为代码功底太差就做不下去，等待大佬们进行开发了。
我又来了，周末有空自己折腾了一下。结论是写入太慢（大概是主要原因之一？）。 所以还是要先多线程再考虑这个吧！毕竟py2也没有asyncio,有也不知道怎么和这个xlwt结合233.
这个问题本身可以转化成图论的问题。把每个御魂组合表示成图的顶点，顶点的边如果定义为公用同一个御魂，那么问题就变成了在这个图上寻找最大的独立集。 另外一种定义，图的顶点依然为御魂组合，两个组合如果不共用御魂则用一条边把他们连起来，这样问题就变成了在这个图上找Maximum clique。 这两个图互为补图，这两个问题都是NPC的，也就是基本上只能依靠穷举找到最优解，但是有一些近似解法可以考虑。 也可以生成Maximal clique/independent set，就是局部的最优解，但这里有一个问题比较关键，就是如果有不同的独立组合方案，那么如何定义哪一套更好？
这个问题本身可以转化成图论的问题。把每个御魂组合表示成图的顶点，顶点的边如果定义为公用同一个御魂，那么问题就变成了在这个图上寻找最大的独立集。 另外一种定义，图的顶点依然为御魂组合，两个组合如果不共用御魂则用一条边把他们连起来，这样问题就变成了在这个图上找Maximum clique。 这两个图互为补图，这两个问题都是NPC的，也就是基本上只能依靠穷举找到最优解，但是有一些近似解法可以考虑。 也可以生成Maximal clique/independent set，就是局部的最优解，但这里有一个问题比较关键，就是如果有不同的独立组合方案，那么如何定义哪一套更好？
这个只有一个解吧，还是NPC。我甚至想过最大流来着，也是一个解。这里应该是输出所有可能情况，不同方案可以按攻击x爆伤或类似的去比，但没必要，因为全都要啊。
而且我觉得IO瓶颈倒是挺严重的，完全不写文件的话上面写的那个naive的算法能十分钟算完50M文件，可以接受了。这方面的话我不知道写csv会不会比这个xls快，这几天都在超鬼王了233
这个问题本身可以转化成图论的问题。把每个御魂组合表示成图的顶点，顶点的边如果定义为公用同一个御魂，那么问题就变成了在这个图上寻找最大的独立集。 另外一种定义，图的顶点依然为御魂组合，两个组合如果不共用御魂则用一条边把他们连起来，这样问题就变成了在这个图上找Maximum clique。 这两个图互为补图，这两个问题都是NPC的，也就是基本上只能依靠穷举找到最优解，但是有一些近似解法可以考虑。 也可以生成Maximal clique/independent set，就是局部的最优解，但这里有一个问题比较关键，就是如果有不同的独立组合方案，那么如何定义哪一套更好？
这个只有一个解吧，还是NPC。我甚至想过最大流来着，也是一个解。这里应该是输出所有可能情况，不同方案可以按攻击x爆伤或类似的去比，但没必要，因为全都要啊。
而且我觉得IO瓶颈倒是挺严重的，完全不写文件的话上面写的那个naive的算法能十分钟算完50M文件，可以接受了。这方面的话我不知道写csv会不会比这个xls快，这几天都在超鬼王了233
全都要就意味着要遍历所有可能，不是时间太久就是内存不够或者两个问题都存在。
你说的算法，应该就是求Maximal clique的一种算法的扩展：已知一个大小为N的clique，尝试所有顶点可以扩展成N+1的clique（如果存在的话）。根据第二种定义的图，以所有的边作为起点（N=2的clique），可以找出N+1的clique的集合，然后重复这个过程。我实现了一个版本，但是处理1w种御魂方案就已经内存不够了。肝完鬼王我再去看看能不能优化一下... 我不太清楚你怎么写的，但是感觉IO不是大的问题才对，如果把中间结果缓存在内存里最后输出呢？可以贴个代码给大家参考一下。
这个问题本身可以转化成图论的问题。把每个御魂组合表示成图的顶点，顶点的边如果定义为公用同一个御魂，那么问题就变成了在这个图上寻找最大的独立集。 另外一种定义，图的顶点依然为御魂组合，两个组合如果不共用御魂则用一条边把他们连起来，这样问题就变成了在这个图上找Maximum clique。 这两个图互为补图，这两个问题都是NPC的，也就是基本上只能依靠穷举找到最优解，但是有一些近似解法可以考虑。 也可以生成Maximal clique/independent set，就是局部的最优解，但这里有一个问题比较关键，就是如果有不同的独立组合方案，那么如何定义哪一套更好？
这个只有一个解吧，还是NPC。我甚至想过最大流来着，也是一个解。这里应该是输出所有可能情况，不同方案可以按攻击x爆伤或类似的去比，但没必要，因为全都要啊。 而且我觉得IO瓶颈倒是挺严重的，完全不写文件的话上面写的那个naive的算法能十分钟算完50M文件，可以接受了。这方面的话我不知道写csv会不会比这个xls快，这几天都在超鬼王了233
全都要就意味着要遍历所有可能，不是时间太久就是内存不够或者两个问题都存在。
你说的算法，应该就是求Maximal clique的一种算法的扩展：已知一个大小为N的clique，尝试所有顶点可以扩展成N+1的clique（如果存在的话）。根据第二种定义的图，以所有的边作为起点（N=2的clique），可以找出N+1的clique的集合，然后重复这个过程。我实现了一个版本，但是处理1w种御魂方案就已经内存不够了。肝完鬼王我再去看看能不能优化一下... 我不太清楚你怎么写的，但是感觉IO不是大的问题才对，如果把中间结果缓存在内存里最后输出呢？可以贴个代码给大家参考一下。
https://github.com/jiajunsu/calculator_of_Onmyoji/compare/master...ZepKing:combine_dp 前两天写的，比较乱哈哈
这里面是有个矛盾的。
不写文件，内存是肯定吃不消的；写文件，频繁的IO会影响计算的效率（当然xlwt这个库本身在写处理上的开销就比较大）
不过目前计算上面是可以做下优化，把C(2,n)的结果拿来做C(3,n)的前置
之前有尝试过计算每个元素的独立集，然后在独立集里面再递归遍历取独立子集，最后发现内存吃不下。因为只有递归到最后了才能够退出，逐层退出递归的时候内存就爆炸了:(
写文件这里可以考虑改成输出csv，追加写方式，定期关闭文件句柄，减少内存消耗。csv格式excel也能打开，写入的速度也会快很多
找到一个maximum clique的C++实现，5000个vertex的图（随机生成edge，～3e6）在我的mbp上跑用1分钟。 https://github.com/ryanrossi/pmc
