查找字符串邻居高达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”。

其他

的其他方法也欢迎，escpecially与速度的提高。以来 我们将处理数百万的长度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);
}

Answer 2

下面是做到这一点应该对任何数量的字符和字符串的长度工作的一种方式：

string base = "000";
char values[] = {'0', '1', '2', '3' };

for (int i = 0; i < base.length(); ++i)
{
   for (int j = 0; j < countof(values); ++j)
   {
      if (base[i] != values[j])
      {
          string copy = base;
          copy[i] = values[j];
          cout << copy << endl;

          for (int k = i+1; k < base.length(); ++k)
          {
              for (int l = 0; l < countof(values); ++l)
              {
                   if (copy[k] != values[l])
                   {
                       string copy2 = copy;
                       copy[k] = values[l];
                       cout << copy2 << endl;
                   }
              }
          }
      }
   }
}

Answer 3

此应相当于产生2的汉明距离内的所有字符串，在4符号字母表。我已经看到了它的算法，但我很茫然，现在找他们。也许，这可以作为在一个正确的方向指针。

Answer 4

您的问题[修改：原单（见问题的以前版本）]是，在你的内部循环，你只分配“下一个”元素。快速的解决办法是在包裹neighbors写：

vector <int> neighbors(const vector<int>& arg, int posNo, int baseNo) {
    // pass base position and return neighbors

    vector <int> transfVec = arg

    transfVec[posNo % arg.size()] = baseNo;

    return transfVec;

}

当你有你的阵列中的两个或三个项目此修复才有效。如果您想了解更多，你需要重写你的算法，因为它不处理的情况下长度大于三的。 （它不应该需要，即使你使用的算法是太严格。）

Answer 5

这两个如果是：

 if (numTag[p] == b) {
     bval = 0;
 }

 if (nbnumTag[l] == c) {
     cval = c;
 }

应该代替具有continue的机构。

---

这两个环路应该从0开始：

for ( int b=1; b<=3 ; b++ ) {
for (int  c=1; c<=3; c++) {

// i.e.

for ( int b=0; b<=3 ; b++ ) {
for (int  c=0; c<=3; c++) {

Answer 6

它看起来像strager已确定的主要问题：循环条件。你的字母是0,1,2,3，所以你应该遍历该整个范围。 0是不是一个特例，因为你的代码试图把它。特殊情况是跳过迭代时，字母值等于在你的钥匙，这是继续通过什么建议strager实现价值。

下面是我对你的算法的版本。它有环结构的一些替代性的想法，它避免了在地方修改它复制的关键。请注意，您也可以通过改变MIN_VALUE和MAX_VALUE常数改变字母的大小。

以下是适用于 “001” 情况下的输出：

101 111 121 131 102 103 100
201 211 221 231 202 203 200
301 311 321 331 302 303 300
011 012 013 010
021 022 023 020
031 032 033 030
002
003
000

和下面的代码：

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

const int MIN_VALUE = 0;
const int MAX_VALUE = 3;

int increment(int& ch)
{
    if (ch == MAX_VALUE)
        ch = MIN_VALUE;
    else
        ++ch;
    return ch;
}

string stringKey(const vector<int>& key)
{
    ostringstream sout;
    for (int i = 0; i < key.size(); ++i) 
        sout << key[i];
    return sout.str();
}

int main()
{
    vector<int> key;
    key.push_back(0);
    key.push_back(0);
    key.push_back(1);

    for (int outerKeyPos = 0;  outerKeyPos < key.size(); ++outerKeyPos)
    {
        int outerOriginal = key[outerKeyPos];
        while (increment(key[outerKeyPos]) != outerOriginal)
        {
            cout << stringKey(key);
            for (int innerKeyPos = outerKeyPos + 1; innerKeyPos < key.size(); ++innerKeyPos)
            {
                int innerOriginal = key[innerKeyPos];
                while (increment(key[innerKeyPos]) != innerOriginal)
                {
                    cout << " " << stringKey(key);
                }
            }
            cout << endl;
        }
    }
}

Answer 7

我试图纠正你的算法，保持尽可能接近原来的一个：

 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=0; b<=3 ; b++ ) { // Loop over all 4 elements

         int bval = b;
         if (numTag[p] == b) {
             continue; // This is the seed vector, ignore it
         }

         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=0; c<=3; c++) {

                 int cval = c;

                 if (nbnumTag[l] == c) { // Loop over all 4 elements
                     continue; // This is nbnumTag, ignore it
                 }
                 vector <int> nbnumTag2 = neighbors(nbnumTag, l, cval);
                 string SnbnumTag2 = Vec2Str(nbnumTag2);

                 cout << "\t" << SnbnumTag2;
                 cout << "\n";
             }
         }
     }
 }

的问题是，不遍历所有4倍可能的值（0,1,2,3），但是由于某种原因跳过0。我这样做的方式是遍历所有这些，忽略（通过使用一个继续），其与在第1阶段中计算出的种子或1点不同的标签相同的载体中。

话虽如此，我相信比你更好的算法提出，这将是更好地考虑其中的一个。

Answer 8

这是我的难看，哈克溶液：

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

struct tri
{
    tri(int a, int b, int c)
    {
        switch (a)
        {
            case 0:
                m[0] = 0;
                m[1] = b;
                m[2] = c;
                break;
            case 1:
                m[0] = b;
                m[1] = 0;
                m[2] = c;
                break;
            case 2:
                m[0] = b;
                m[1] = c;
                m[2] = 0;
                break;
        }
    }
    int m[3];
};

int main()
{
    vector<tri> v;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 4; j++)
            for (int k = 0; k < 4; k++)
            {
                v.push_back(tri(i,j,k));
            }

    vector<tri>::iterator it;
    for (it = v.begin(); it != v.end(); ++it)
    {
        cout << (*it).m[0];
        cout << (*it).m[1];
        cout << (*it).m[2];
        cout << endl;
    }
}