تعداد كافة السلاسل التي تلبي القيود المحددة

Question

أنا أبحث عن اسم فئة المشكلة التالية، حتى أتمكن من البحث في جوجل عن خوارزميات فعالة ومزيد من المعلومات.

لدي أبجدية مكونة من ثلاثة أحرف {-1، 0، 1}.

أحتاج إلى إنشاء جميع السلاسل التي يبلغ طولها 24 بشكل فعال والتي تكون في الغالب {0} ولكنها تحتوي على صفر إلى ثمانية أحرف {1,-1} موزعة في أنماط معينة.(تتضمن الأنماط قيودًا على عدد وأزواج {-1}).إجمالي سلاسل الأرقام التي تلبي معاييري متواضعة جدًا:حوالي 128.000.

إذن ما هو اسم هذه الفئة من المشاكل/الخوارزميات؟

Answer 1

لست متأكدًا من وجود "فئة خوارزمية" محددة جيدًا لهذا الغرض؛إنه مجرد تمرين في التوافقيات.يمكنك القيام بالتوليد في ثلاث خطوات:

1. قم بإنشاء جميع أرقام 24 بت مع مجموعة 8 بتات أو أقل (قد تتمكن من تسريع ذلك قليلاً إذا قمت بحساب بعض جداول البحث مسبقًا)
2. لكل رقم 24 بت مع مجموعة n من البتات، قم بالتكرار على جميع أرقام n-bit
3. إذا كانت البتة k من رقم n هي 0، فسيتم طباعة بت المجموعة k من الرقم 24 بت كـ -1، وإلا فسيتم طباعتها كـ 1

لشرح الخطوات من 2 إلى 3 بشكل أفضل، قل أن رقم 24 بت الخاص بك يحتوي على 4 بتات ويبدو كذلك

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

بعد ذلك، نقوم بالتكرار على جميع الأرقام الستة عشر المكونة من 4 بتات 0 0 0 0 ل 1 1 1 1, ، وعلى سبيل المثال:

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0

Answer 2

إذا كنت تحتاج فقط إلى حل هذا مرة واحدة، وربما كنت قد مجرد القوة الغاشمة ووضعها النتائج في جدول بحث في التطبيق الخاص بك. هناك أقل من تريليون 24 متواليات قليلا من 0،1، -1 للتحقق.

إذا ربما انا اقوم الرياضيات خاطئة أو تحتاج إلى حل المشكلة في وقت التشغيل بشكل حيوي، وأود أن تنظر في المشكلة باعتباره نظاما من 24 متغيرات كل محدود إلى -1، 0، 1 والاقتراب بأنها < وأ href = "http://en.wikipedia.org/wiki/Constraint_satisfaction_problem" يختلط = "نوفولو noreferrer"> القيد رضا مشكلة ، على افتراض انك يمكن تعداد القيود الخاصة بك بطريقة أو بأخرى. قلقي، مع ذلك، هو أنه منذ كنت تحتاج إلى رؤية <م> جميع حلول وليس مجرد مجموعة فرعية، قد لا تزال يكون عالقا باستفاضة البحث في الفضاء المشكلة.

وهذه الورقة يبدو الحق في زقاق الخاص بك: تعداد جميع حلول لمشاكل رضا القيد . على الرغم من أنني لم يكن لديك الوصول إلى النص الكامل للورقة لمعرفة ما اذا كان يساعد.

وأنا قد ينبح حتى الشجرة خاطئة جميعا، ولكن ربما هذا هو مكان انطلاق

Answer 3

والجواب منفصلة تماما عن تقريري الأخير، كرمز العمل يميل إلى وصلات ورقة رابحة للبحث عن الأوراق، وجدت هذا الرمز على الموقع المنتدى الفيزياء و لا يمكن أن الفضل في ذلك بنفسي، أنا فقط ثابتة ذلك حتى انها جمعت تحت ز ++ وتغيير لثوابت للبحث عن 8 بت في 24. وبسرعة كبيرة تعداد كافة 24 سلاسل بت مع 8 بت على، وهناك فقط حوالي 735،000 من هؤلاء. تظهر هذه "القوالب" أنماط الوحيدة الصالحة لشخصياتك غير الصفرية. كنت ثم لإجراء كل هذه الإجابات 735000 ورمي في جميع أنحاء - علامات / + وتقرر ما إذا كان كل يلبي لك المعايير، ولكن هذه الطريقة التي بدأت من 735k الحلول الممكنة بدلا من 200 مليار

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }