Поиск строк, Соседних До 2-х Различных позиций
https://stackoverflow.com/questions/680011
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Учитывая начальную строку, я хочу найти ее соседей, которые отличаются не более чем в 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;
}
Решение
Сработает ли это?Он перечисляет дерево возможных строк, удаляя все с >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);
}
Другие советы
Вот один из способов сделать это, который должен работать для любого количества символов и длины строки:
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;
}
}
}
}
}
}
Это должно быть эквивалентно генерации всех строк в пределах расстояния Хэмминга 2 по алфавиту из 4 символов.Я видел алгоритмы для этого, но сейчас я не могу их найти.Возможно, это может послужить указателем в правильном направлении.
Твоя проблема [Редактировать:оригинальный (см. предыдущие редакции вопроса)] заключается в том, что в вашем внутреннем цикле вы назначаете только элемент 'next' .Быстрое решение заключается в том, чтобы обернуть запись в 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;
}
Это исправление работает только тогда, когда у вас есть два или три элемента в вашем массиве.Если вы хотите большего, вам нужно переписать свой алгоритм, поскольку он вообще не обрабатывает случаи, когда длина больше трех.(Даже в этом не должно быть необходимости.Алгоритм, который вы используете, просто слишком ограничительный.)
Эти два "если":
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++) {
Похоже, стрейджер определил главную проблему:условия цикла.Ваш алфавит равен 0,1,2,3, поэтому вы должны перебрать весь этот диапазон.0 не является особым случаем, поскольку ваш код пытается его обработать.Особым случаем является пропуск итерации, когда значение алфавита равно значению в вашем ключе, чего и добивается continue, предложенный 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;
}
}
}
Я попытался исправить ваш алгоритм, оставаясь как можно ближе к исходному:
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.Способ, которым я это делаю, заключается в переборе всех из них и игнорировании (с помощью continue) вектора, который совпадает с начальным значением или тегом, отличающимся на 1 точку, вычисленным на этапе 1.
Сказав это, я считаю, что предложены лучшие алгоритмы, чем ваш, и было бы лучше рассмотреть один из них.
Вот мое уродливое, хакерское решение:
#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;
}
}
