العثور على سلاسل الجيران بما يصل إلى موقعين مختلفين
https://stackoverflow.com/questions/680011
-
22-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
بالنظر إلى سلسلة أولية، أريد العثور على جيرانها الذين يختلفون في موقعين على الأكثر.جميع الأرقام التي تنطوي عليها عملية إنشاء السلسلة هي أربعة فقط (أي: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 رموز.لقد رأيت خوارزميات لذلك، لكنني في حيرة من أمر العثور عليها الآن.وربما يكون هذا بمثابة مؤشر في الاتجاه الصحيح.
مشكلتك [يحرر:النسخة الأصلية (انظر المراجعات السابقة للسؤال)] هو أنه في حلقتك الداخلية، تقوم فقط بتعيين العنصر "التالي".الحل السريع هو التفاف الكتابة 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 ليست حالة خاصة، حيث يحاول الكود الخاص بك التعامل معها.الحالة الخاصة هي تخطي التكرار عندما تساوي القيمة الأبجدية القيمة الموجودة في مفتاحك، وهو ما تحققه المتابعة التي يقترحها 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";
}
}
}
}
المشكلة هي أنك لا تكرر جميع القيم الأربع المحتملة (0،1،2،3)، ولكنك تتخطى 0 لسبب ما.الطريقة التي أفعل بها ذلك هي التكرار عليها جميعًا وتجاهل (باستخدام الاستمرار) المتجه الذي هو نفسه مع البذرة أو العلامة المختلفة ذات النقطة الواحدة المحسوبة في المرحلة 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;
}
}
