W**********U
发帖数: 132 | 1 怎么产生一个5000个字符串(alphanumeric: a ~ z, A ~ Z, 0 - 9),使得其中任何四个
相邻的字符组成的子串都不相同。比如，这个字符串就满足条件：
Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3。。
。。。。
谢谢。 |
h**********c
发帖数: 4120 | 2 生成四个字符的字典，字典没有重复，
然后参考TCP协议的sliding window
【在 W**********U 的大作中提到】
: 怎么产生一个5000个字符串(alphanumeric: a ~ z, A ~ Z, 0 - 9),使得其中任何四个
: 相邻的字符组成的子串都不相同。比如，这个字符串就满足条件：
: Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3。。
: 。。。。
: 谢谢。
|
h**********c
发帖数: 4120 | |
h**********c
发帖数: 4120 | 4 我觉得是不是伪站搞的，还是都学那个node js 搞async,说话都半拉卡几，语无伦次，
吞吞吐吐，云山雾绕。 |
W**********U
发帖数: 132 | 5 》 Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3
在这个例子里， 相邻的四个字符组成的子串包括： Aa0A, a0Aa, 0Aa1, Aa1A, a1Aa,.
..
【在 h**********c 的大作中提到】
: 四个
: 相邻怎么相邻，是二维的吗？
|
h**********c
发帖数: 4120 | 6 估计汉语是您第二语言吧，四个连续字符的子窜。
用一个hashset,
随机生成四窜，set里有就加，没有就过，
用dequeue来做sliding window.
Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3
,.
【在 W**********U 的大作中提到】
: 》 Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3
: 在这个例子里， 相邻的四个字符组成的子串包括： Aa0A, a0Aa, 0Aa1, Aa1A, a1Aa,.
: ..
|
w***g
发帖数: 5958 | 7 Aa0 Aa1 Aa2 Aa3 ... Aa9
Ab0 Ab1 Ab2 Ab3 ... Ab9
Ac0 Ac1 Ac2 Ac3 ... Ac9
...
Az0 Az1 Az2 Az3 ... Az9
Ba0 Ba1 Ba2 Ba3 ... Ba9
...
就这么下去一直到
Zz0 Zz1 Zz2 Zz3 ... Zz9
这样产生出来的串长度一共26*26*10= 6760
我觉得能满足要求。
一般问题是一个在四字母字串作为节点的有向图上找long path的问题。
基本套路是深度优先搜索。但是这个问题的longest path版本是著名的
NP难问题。深度优先搜索如果没法立即出结果，那等多久才能出结果
就不好说了。或者说5000可能立刻就出结果了，但是改成50000可能永远
也出不了结果。
【在 W**********U 的大作中提到】
: 怎么产生一个5000个字符串(alphanumeric: a ~ z, A ~ Z, 0 - 9),使得其中任何四个
: 相邻的字符组成的子串都不相同。比如，这个字符串就满足条件：
: Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3。。
: 。。。。
: 谢谢。
|
d***a
发帖数: 13752 | 8 按前面wdong说的，把这个pattern继续下去，就可以了。下面这个也可以：
abc0abc1abc2...abcAabcBabcC...bcd0bcd1bcd2...
长度可以达到5000。可以证明四个字符长度的子串不会重复。
你的问题，不会是要穷举吧，那就是另一回事了。
【在 W**********U 的大作中提到】
: 怎么产生一个5000个字符串(alphanumeric: a ~ z, A ~ Z, 0 - 9),使得其中任何四个
: 相邻的字符组成的子串都不相同。比如，这个字符串就满足条件：
: Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8Aa9Ab0Ab1Ab2Ab3Ab4Ab5Ab6Ab7Ab8Ab9Ac0Ac1Ac2Ac3。。
: 。。。。
: 谢谢。
|
w***g
发帖数: 5958 | 9 我傻了，竟然重新发明了他题目里的pattern。
【在 d***a 的大作中提到】
: 按前面wdong说的，把这个pattern继续下去，就可以了。下面这个也可以：
: abc0abc1abc2...abcAabcBabcC...bcd0bcd1bcd2...
: 长度可以达到5000。可以证明四个字符长度的子串不会重复。
: 你的问题，不会是要穷举吧，那就是另一回事了。
|
g****t
发帖数: 31659 | 10 改成5万的话不知道可不可以这样做。
长度为L的字符串S，有L－3个满足要求的4字子串。
Let S子串的集合为f(S)
Let S最后3位的串 g(S)
加一个新字母只需要查最新的4字子串是否和L－3个相同就可以了。
这个检查似乎可以承受。
选最新字母的时候启发式，选一个x,导致g(S) + x组成的四子字串
和f(S)的平均值距离最近，不知道可以吗。
这样可以启发式的节省字母。
或者nearest neighborhood之类的选一个新字母。
回头我写个程序试试。
【在 d***a 的大作中提到】
: 按前面wdong说的，把这个pattern继续下去，就可以了。下面这个也可以：
: abc0abc1abc2...abcAabcBabcC...bcd0bcd1bcd2...
: 长度可以达到5000。可以证明四个字符长度的子串不会重复。
: 你的问题，不会是要穷举吧，那就是另一回事了。
|
d***a
发帖数: 13752 | 11 呵呵...思路都差不多的。
【在 w***g 的大作中提到】
: 我傻了，竟然重新发明了他题目里的pattern。
|
p****o
发帖数: 1340 | 12 不知道你这种greedy的办法是不是就是最优解啊。四个字母的字串图的对称性很强。不
知道有没有可以利用的地方。
反正是NP问题，我想这样还不如就用heteroclinic的方法，但是引入随机性，通模拟退
火的办法，求一个近似解算了。
【在 g****t 的大作中提到】
: 改成5万的话不知道可不可以这样做。
: 长度为L的字符串S，有L－3个满足要求的4字子串。
: Let S子串的集合为f(S)
: Let S最后3位的串 g(S)
: 加一个新字母只需要查最新的4字子串是否和L－3个相同就可以了。
: 这个检查似乎可以承受。
: 选最新字母的时候启发式，选一个x,导致g(S) + x组成的四子字串
: 和f(S)的平均值距离最近，不知道可以吗。
: 这样可以启发式的节省字母。
: 或者nearest neighborhood之类的选一个新字母。
|
h**********c
发帖数: 4120 | 13 很沮丧的一天，拖着疲惫的身体带着一脑袋问题回家，其实是回到公寓。
想睡觉的时候过劲了。 |
g****t
发帖数: 31659 | 14 模拟退火或者遗传算法等也要有个启发式的优化指标。
所以问题的核心是以下启发式策略是否管用：
“尽可能和过去的字符串集合靠拢以便于节省字母”
如果这个启发式办法比纯随机穷举快，那就有意思。
: 不知道你这种greedy的办法是不是就是最优解啊。四个字母的字串图的对称性很
强。不
: 知道有没有可以利用的地方。
: 反正是NP问题，我想这样还不如就用heteroclinic的方法，但是引入随机性，通
模拟退
: 火的办法，求一个近似解算了。
【在 p****o 的大作中提到】
: 不知道你这种greedy的办法是不是就是最优解啊。四个字母的字串图的对称性很强。不
: 知道有没有可以利用的地方。
: 反正是NP问题，我想这样还不如就用heteroclinic的方法，但是引入随机性，通模拟退
: 火的办法，求一个近似解算了。
|
