c++ - 通过最多 2 个不同的位置查找字符串邻居

Question

给定一个种子字符串，我想找到最多有 2 个位置不同的邻居。生成字符串所涉及的所有数字只有四个(即 0、1、2、3)。这是我的意思的例子:

# 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  

但为什么我的这段代码无法正确生成呢？特别是当种子字符串不是“000”时。

也欢迎使用其他方法，尤其是提高速度。自从我们将处理数百万个长度为 34 到 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;
}

Answer 1

这样可以吗？它枚举可能的字符串树，修剪所有与原始字符串有 >2 个差异的字符串。

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);
}