查找字符串邻居达2不同立场 [英] Finding Strings Neighbors By Up To 2 Differing Positions
本文介绍了查找字符串邻居达2不同立场的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
由于种子字符串，我想找到它的邻国最多不同的2个位置。所有的数字涉及生成字符串只有四个（即0,1,2,3）。这就是例子我的意思：
＃在这个例子中，第一列
＃为邻，只有1位不同。
＃列的其余2个位置不同
种子= 000
100 110 120 130 101 102 103
200 210 220 230 201 202 203
300 310 320 330 301 302 303
010 011 012 013
020 021 022 023
030 031 032 033
001
002
003
种子= 001
101 111 121 131 100 102 103
201 211 221 231 200 202 203
301 311 321 331 300 302 303
011 010 012 013
021 020 022 023
031 030 032 033
000
003
002
因此给定长度为L的标签
我们将有3 * L + 9L（L-1）/ 2的邻居
但是，为什么这$ C $矿C未能正确产生的呢？特别是当种子字符串是比000。
其他其他的方法也受到了欢迎，escpecially与速度的提升。以来 我们要处理数以百万计长度为34的种子标签为36。
的#include＆LT;的iostream＆GT;
＃包括＆LT;载体＆GT;
＃包括＆LT; fstream的＆GT;
＃包括＆LT; sstream＆GT;
使用名字空间std;
字符串ConvertInt2String（INT INTVAL）{
标准::字符串S;
性病:: stringstream的了;
出＆LT;＆LT; INTVAL;
S = out.str（）;
返回S;
}
串Vec2Str（矢量＆lt; INT＆GT; NTG）{
字符串STTG =;
为（无符号I = 0; I＆LT; NTg.size（）;我++）{
STTG + = ConvertInt2String（NTG [I]）;
}
返回STTG;
}
模板＆LT; typename的T＆GT;无效prn_vec（常量的std ::矢量＆lt; T＆GT;＆安培;阿根廷，串月=）
{
为（无符号N = 0; N＆LT; arg.size（）; N ++）{
COUT＆LT;＆LT; ARG [N]＆LT;＆LT; 9月;
}
返回;
}
矢量＆lt; int的＆GT;邻居（矢量＆lt; INT＆GT;＆安培;阿根廷，INT posNo，诠释baseNo）{
//通过基地位置，并返回邻居
矢量＆lt; int的＆GT; transfVec;
transfVec = ARG;
//根据strager的第一篇文章修改
transfVec [posNo％arg.size（）] = baseNo;
返回transfVec;
}
诠释的main（）{
矢量＆lt; int的＆GT; numTag;
numTag.push_back（0）;
numTag.push_back（0）;
numTag.push_back（1）; //如果000这个code ++工程，但不是001或其他
//注意在实际实践numTag可大于3
INT TagLen =＆的static_cast其中; INT＆GT;（numTag.size（））;
为（中间体p值= 0; P＆所述; TagLen，P ++）{
//第一个循环是生成标记1的位置不同
为（中间体B = 1; b将= 3; b ++）{
INT BVAL = B;
如果（numTag [P] == B）{
BVAL = 0;
}
矢量＆lt; int的＆GT; nbnumTag =邻居（numTag，对，BVAL）;
字符串SnbnumTag = Vec2Str（nbnumTag）;
COUT＆LT;＆LT; SnbnumTag;
COUT＆LT;＆LT; \ N的;
//二回路标签2的位置不同
为（中间体升= P + 1; L＆其中; TagLen;升++）{
对于（INT C = 1; C＆LT; = 3; C ++）{
INT CVAL = C;
如果（nbnumTag [L] == C）{
CVAL = C;
}
矢量＆lt; int的＆GT; nbnumTag2 =邻居（nbnumTag，L，CVAL）;
字符串SnbnumTag2 = Vec2Str（nbnumTag2）;
COUT＆LT;＆LT; \ t的＆LT;＆LT; SnbnumTag2;
COUT＆LT;＆LT; \ N的;
}
}
}
}
返回0;
}
解决方案
这会做到这一点？它列举可能的字符串的树，从原来> 2的差异修剪所有。
无效步行（的char * S，诠释我，诠释ndiff）{
焦炭C = S [I]
如果（ndiff＆GT; 2）返回;
如果（C =='\ 0'）{
如果（ndiff大于0）打印（S）;
}
其他 {
S [I] ='0';走路（S，I + 1，（S [I] ==çndiff：ndiff + 1）;
S [i]于='1';走路（S，I + 1，（S [I] ==çndiff：ndiff + 1）;
S [I] ='2';走路（S，I + 1，（S [I] ==çndiff：ndiff + 1）;
S [I] ='3';走路（S，I + 1，（S [I] ==çndiff：ndiff + 1）;
S [i] = C;
}
}
焦炭种子[] =000;
主要（）{
走路（种子，0，0）;
}
Given a seed string, I want to find its neighbors with at most differ in 2 positions. All the digits involve in generating string are only four (i.e. 0,1,2,3). This is the example for what I mean:
# In this example, 'first' column
# are neighbors with only 1 position differ.
# The rest of the columns are 2 positions differ
Seed = 000
100 110 120 130 101 102 103
200 210 220 230 201 202 203
300 310 320 330 301 302 303
010 011 012 013
020 021 022 023
030 031 032 033
001
002
003
Seed = 001
101 111 121 131 100 102 103
201 211 221 231 200 202 203
301 311 321 331 300 302 303
011 010 012 013
021 020 022 023
031 030 032 033
000
003
002
Hence given a tag of length L
we will have 3*L + 9L(L-1)/2 neighbors
But why this code of mine fails to generate it correctly? Especially when the seed string is other than "000".
Other approaches are also welcomed, escpecially with speed improvement. Since we will be processing millions of seed tags of length 34 to 36.
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;
string ConvertInt2String(int IntVal) {
std::string S;
std::stringstream out;
out << IntVal;
S = out.str();
return S;
}
string Vec2Str (vector <int> NTg) {
string StTg = "";
for (unsigned i = 0; i < NTg.size(); i++) {
StTg += ConvertInt2String(NTg[i]);
}
return StTg;
}
template <typename T> void prn_vec(const std::vector < T >&arg, string sep="")
{
for (unsigned n = 0; n < arg.size(); n++) {
cout << arg[n] << sep;
}
return;
}
vector <int> neighbors(vector<int>& arg, int posNo, int baseNo) {
// pass base position and return neighbors
vector <int> transfVec;
transfVec = arg;
//modified according to strager's first post
transfVec[posNo % arg.size()] = baseNo;
return transfVec;
}
int main () {
vector <int> numTag;
numTag.push_back(0);
numTag.push_back(0);
numTag.push_back(1); // If "000" this code works, but not 001 or others
// Note that in actual practice numTag can be greater than 3
int TagLen = static_cast<int>(numTag.size());
for ( int p=0; p< TagLen ; p++ ) {
// First loop is to generate tags 1 position differ
for ( int b=1; b<=3 ; b++ ) {
int bval = b;
if (numTag[p] == b) {
bval = 0;
}
vector <int> nbnumTag = neighbors(numTag, p, bval);
string SnbnumTag = Vec2Str(nbnumTag);
cout << SnbnumTag;
cout << "\n";
// Second loop for tags in 2 position differ
for (int l=p+1; l < TagLen; l++) {
for (int c=1; c<=3; c++) {
int cval = c;
if (nbnumTag[l] == c) {
cval = c;
}
vector <int> nbnumTag2 = neighbors(nbnumTag, l, cval);
string SnbnumTag2 = Vec2Str(nbnumTag2);
cout << "\t" << SnbnumTag2;
cout << "\n";
}
}
}
}
return 0;
}
解决方案
Would this do it? It enumerates the tree of possible strings, pruning all with >2 differences from the original.
void walk(char* s, int i, int ndiff){
char c = s[i];
if (ndiff > 2) return;
if (c == '\0'){
if (ndiff > 0) print(s);
}
else {
s[i] = '0'; walk(s, i+1, (s[i]==c ? ndiff : ndiff+1);
s[i] = '1'; walk(s, i+1, (s[i]==c ? ndiff : ndiff+1);
s[i] = '2'; walk(s, i+1, (s[i]==c ? ndiff : ndiff+1);
s[i] = '3'; walk(s, i+1, (s[i]==c ? ndiff : ndiff+1);
s[i] = c;
}
}
char seed[] = "000";
main(){
walk(seed, 0, 0);
}
这篇关于查找字符串邻居达2不同立场的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
