최대 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;
}
}
}
}
}
}
이는 4 스파이 알파벳에 걸쳐 2의 해밍 거리 내에서 모든 줄을 생성하는 것과 동일해야합니다. 나는 그것에 대한 알고리즘을 보았지만 지금 당장 그것을 찾기 위해 잃어 버렸습니다. 아마도 이것은 올바른 방향으로 포인터 역할을 할 수 있습니다.
너의 문제 [편집 : 원래의 것 (이전 질문 수정 참조)] 내부 루프에서 '다음'요소 만 할당하는 것입니다. 빠른 수정은 쓰기를 포장하는 것입니다 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;
}
이 수정은 배열에 2 ~ 3 개의 항목이있을 때만 작동합니다. 더 많은 것을 원한다면 길이가 3보다 큰 경우를 처리하지 않으므로 알고리즘을 다시 작성해야합니다. (심지어 사용 할 필요는 없습니다. 사용하는 알고리즘은 너무 제한적입니다.)
이 두 사람은 :
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++) {
Strager가 주요 문제인 루프 조건을 식별 한 것 같습니다. 알파벳은 0,1,2,3이므로 전체 범위에 걸쳐 반복해야합니다. 코드는 코드를 처리하려고 시도하기 때문에 0은 특별한 경우가 아닙니다. 특별한 경우는 알파벳 값이 키의 값과 동일 할 때 반복을 건너 뛰는 것입니다.
아래는 내 알고리즘의 내 버전입니다. 루프 구조에 대한 몇 가지 대안 아이디어가 있으며 키를 수정하여 키를 복사하지 않습니다. 변경하여 알파벳의 크기를 변경할 수도 있습니다. 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을 건너 뛰는 것입니다. 내가하고있는 방식은 그들 모두를 반복하고 종자와 동일한 벡터 또는 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;
}
}
제휴하지 않습니다 StackOverflow
