Finding Cordas Vizinhos em até 2 posições divergentes
https://stackoverflow.com/questions/680011
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Dada uma seqüência de semente, eu quero encontrar os seus vizinhos, com no máximo diferem em 2 posições. Todos os dígitos envolver na geração de corda são apenas quatro (isto é, 0,1,2,3). Este é o exemplo para o que eu quero dizer:
# 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
Mas por que este código da mina deixa de gerá-lo corretamente? Especialmente quando a corda semente é que não "000".
Outras abordagens também são bem-vindas, escpecially com melhoria de velocidade. Desde a estaremos processando milhões de etiquetas de sementes de comprimento 34 a 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;
}
Solução
Será que isso faz? Ele enumera a árvore de possíveis cordas, poda todos com> 2 diferenças a partir do 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);
}
Outras dicas
Aqui está uma maneira de fazê-lo que deve funcionar para qualquer número de caracteres e comprimento da string:
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;
}
}
}
}
}
}
Esta deve ser equivalente à geração de todas as cordas dentro de uma distância Hamming de 2, mais de um 4-símbolo do alfabeto. Eu vi algoritmos para isso, mas eu estou em uma perda para encontrá-los agora. Talvez isso possa servir como um ponteiro na direção certa.
Seu problema [ EDIT: o original (ver revisões anteriores de interrogação) ] é que, em seu circuito interno, você está atribuindo apenas o 'próximo' elemento. Uma solução rápida é envolver a gravação em 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;
}
Esta correção só funciona quando você tem dois ou três itens em sua matriz. Se você quiser mais, você precisa reescrever seu algoritmo, pois não lidar com casos em que o comprimento é maior que três em tudo. (Ele não precisa, mesmo. O algoritmo utiliza é muito restritiva.)
Estes dois se de:
if (numTag[p] == b) {
bval = 0;
}
if (nbnumTag[l] == c) {
cval = c;
}
deve sim ter corpos de continue.
Estas duas voltas deve começar no 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++) {
Parece que strager identificou o principal problema: as condições de loop. O seu alfabeto é 0,1,2,3, então você deve varrer todo esse intervalo. 0 não é um caso especial, como seu código tenta tratá-la. O caso especial é pular a iteração quando o valor alfabeto é igual ao valor em sua chave, que é o que a continuar sugerido por Realiza strager.
Abaixo está a minha versão do seu algoritmo. Ele tem algumas idéias alternativas para estruturas de loop, e evita copiar a chave, modificando-o no lugar. Note que você também pode alterar o tamanho do alfabeto, alterando as constantes MIN_VALUE e MAX_VALUE.
Aqui está a saída para o caso "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
E aqui está o código:
#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;
}
}
}
Eu tentei corrigir o seu algoritmo, ficar o mais próximo possível ao original:
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";
}
}
}
}
O problema é que você não iterar sobre todos os 4 valores possíveis (0,1,2,3), mas você pular 0 por algum motivo. A maneira que eu estou fazendo é para iterar sobre todos eles e ignorar (por usar um continue) o vetor que é o mesmo com a semente ou a tag diferente de 1 ponto calculado na fase 1.
Dito isto, acredito que algoritmos melhores do que o seu são propostos e que seria melhor para considerar um deles.
Aqui está a minha solução feio, hacky:
#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;
}
}
