تولد كل الثنائية سلاسل من طول ن مع ك بت تعيين

Question

ما هو أفضل خوارزمية إيجاد جميع الثنائية سلاسل من طول n التي تحتوي على ك بت ؟ على سبيل المثال ، إذا كان n=4 و k=3 ، وهناك...

0111
1011
1101
1110

أحتاج وسيلة جيدة لتوليد هذه أي ن و أي ك لذا أنا أفضل أن يتم ذلك مع السلاسل.

Answer 1

هذه الطريقة سوف تولد جميع الأعداد الصحيحة مع بت بالضبط N '1'.

من https://graphics.stanford.edu/~seAnder/Bithacks.html#nextbitbermilation.

حساب التقليب القادم المعجم التالي

لنفترض أن لدينا نمط من N بت مكتظة إلى 1 في عدد صحيح ونريد التقليب التالي من BITS N 1 في إحساس معجم. على سبيل المثال، إذا كان N 3 ونمط بت 00010011, ، ستكون الأنماط التالية 00010101, 00010110, 00011001, 00011010, 00011100, 00100011، وهكذا دواليك. فيما يلي طريقة سريعة لحساب التقليب التالي.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

ال __builtin_ctz(v) GNU C مترجم جوهري لمعالجة وحدات المعالجة المركزية X86 يعود عدد الأصفار الزائدة. إذا كنت تستخدم محامرة Microsoft ل X86، فإن الجوهري هو _BitScanForward. وبعد هؤلاء كلاهما ينبعث bsfالتعليمات، ولكن لا يمكن أن تكون المعادلات متاحة للهندسة الأخرى. إذا لم يكن الأمر كذلك، ففكر في استخدام إحدى طرق حساب البتات الصفرية المتتالية المذكورة سابقا. إليك نسخة أخرى تميل إلى أن تكون أبطأ بسبب مشغل القسم الخاص بها، لكنها لا تتطلب عد الأصفار الزائدة.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

بفضل داريو سنيدرمانيس الأرجنتين، الذي قدم هذا في 28 نوفمبر 2009.

Answer 2

بيثون

import itertools

def kbits(n, k):
    result = []
    for bits in itertools.combinations(range(n), k):
        s = ['0'] * n
        for bit in bits:
            s[bit] = '1'
        result.append(''.join(s))
    return result

print kbits(4, 3)

Output: ['1110', '1101', '1011', '0111']

تفسير:

أساسا نحتاج إلى اختيار مواقف 1 بت. هناك N اختر K طرق اختيار BITS K بين مجموع بت. itertools هي وحدة نمطية لطيفة تفعل هذا بالنسبة لنا. itertools..Combinations (المدى (ن)، ك) سيختار بتات K من [0، 1، 2 ... N-1]، ثم إنها مجرد بناء السلسلة بالنظر إلى هذه الفهارس بت.

نظرا لأنك لا تستخدم Python، فابحث في رمز الزائفة ل itertools.comBinations هنا:

http://docs.python.org/library/itertools.html#itertools.combinations.

يجب أن يكون من السهل التنفيذ بأي لغة.

Answer 3

ننسى تنفيذ ("يجب عليها القيام به مع سلاسل" هو الواضح تنفيذ المسألة!) -- فكر خوارزمية, بحق الله...تماما كما في أول الوسم يا رجل!

ما تبحث عنه هو مزيج من ك العناصر من مجموعة من ن (المؤشرات, 0 N-1 من مجموعة بت).ومن الواضح ان هذا أبسط للتعبير عن متكرر ، مثل شبة الكود:

combinations(K, setN):
  if k > length(setN): return "no combinations possible"
  if k == 0: return "empty combination"
  # combinations INcluding the first item:
  return (first-item-of setN) combined combinations(K-1, all-but-first-of setN)
   union combinations(K-1, all-but-first-of setN)

أي أن العنصر الأول هو إما موجودة أو غائبة:إذا كان موجودا لديك K-1 من اليسار إلى الذهاب (من الذيل الملقب ولكن التنوب) ، إذا كان غائبا لا يزال ك من اليسار إلى الذهاب.

نمط مطابقة اللغات الوظيفية مثل SML أو هاسكل قد تكون أفضل طريقة للتعبير عن هذا شبة الكود (إجرائية ، مثل بلدي الحب الكبير بيثون ، قد في الواقع قناع المشكلة بعمق من قبل بما في ذلك أيضا-وظائف الغنية ، مثل itertools.combinations, الذي يفعل كل العمل الشاق بالنسبة لك وبالتالي يخفي ذلك منك!).

ما هي أكثر دراية ، لهذا الغرض -- المخطط ، SML, هاسكل, ...?سأكون سعيدا ترجمة أعلاه شبة الكود بالنسبة لك.أستطيع أن أفعل ذلك في لغات مثل بايثون أيضا ، بطبيعة الحال -- ولكن منذ المرحلة هو الحصول على فهم آليات هذا الواجب لن تستخدم أيضا غنية وظائف مثل itertools.combinations, بل العودية (و العودية-القضاء إذا لزم الأمر) على أكثر وضوحا الأوليات (مثل الرأس والذيل ، سلسلة).ولكن من فضلك لا تدع لنا أن نعرف ما شبة الكود مثل اللغة كنت الأكثر دراية!(أنت لا تفهم أن المشكلة أنك الدولة هو مماثل equipotent "الحصول على كافة تركيبات من ك العناصر أو مجموعة(ن)", أليس كذلك؟).

Answer 4

تقوم طريقة C # بإرجاع عداد يقوم بإنشاء جميع المجموعات. نظرا لأنها تنشئ المجموعات التي تقوم فيها بتعدادها، إلا أنها تستخدم مساحة مكدس فقط، لذلك لا تقتصر على مساحة الذاكرة في عدد المجموعات التي يمكن أن تنشئها.

هذا هو الإصدار الأول الذي توصلت إليه. إنه محدود من خلال مساحة المكدس إلى طول حوالي 2700:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    if (length > bits) {
      foreach (string s in BinStrings(length - 1, bits)) {
        yield return "0" + s;
      }
    }
    if (bits > 0) {
      foreach (string s in BinStrings(length - 1, bits - 1)) {
        yield return "1" + s;
      }
    }
  }
}

هذه هي النسخة الثانية التي تستخدم انقسام ثنائي بدلا من تقسيم الحرف الأول، لذلك يستخدم المكدس بشكل أكثر كفاءة. إنه محدود فقط من خلال مساحة الذاكرة للحصول على السلسلة التي تنشئها في كل تكرار، وقد اختبرها ما يصل إلى 10000000:

static IEnumerable<string> BinStrings(int length, int bits) {
  if (length == 1) {
    yield return bits.ToString();
  } else {
    int first = length / 2;
    int last = length - first;
    int low = Math.Max(0, bits - last);
    int high = Math.Min(bits, first);
    for (int i = low; i <= high; i++) {
      foreach (string f in BinStrings(first, i)) {
        foreach (string l in BinStrings(last, bits - i)) {
          yield return f + l;
        }
      }
    }
  }
}

Answer 5

مشكلة واحدة مع العديد من الحلول القياسية لهذه المشكلة هي أن مجموعة السلاسل بأكملها يتم إنشاؤها، ثم يتم تكرار تلك الموجودة في هذه المجموعة، والتي قد تستنفد المكدس. يصبح بسرعة غير عملي لأي شيء ولكن أصغر مجموعات. بالإضافة إلى ذلك، في العديد من الحالات، هناك حاجة فقط إلى أخذ العينات الجزئية، ولكن الحلول المعيارية (العودية) عموما تقطع المشكلة في القطع المنحمة بشدة إلى اتجاه واحد (على سبيل المثال، النظر في جميع الحلول مع أعلى قليلا من البداية، ثم كل ذلك الحلول مع بت واحد البتة).

في كثير من الحالات، سيكون من المرغوب فيه أن تكون قادرا على نقل سلسلة بت (تحديد عنصر تحديد العنصر) إلى وظيفة ولديه إرجاع سلسلة البت التالية بحيث يكون لديك تغيير بسيط (يعرف هذا باسم رمادي الرمز) ولديه تمثيل لجميع العناصر.

يغطي دونالد نوث مجموعة مضيفة كاملة من الخوارزميات لهذا في Fasciple 3A، القسم 7.2.1.3: توليد جميع المجموعات.

هناك نهج لمعالجة خوارزمية الكود الرماد التكرار لجميع طرق اختيار عناصر K من N في http://answers.yahoo.com/Question/index؟qid=20081208224633AA0GDML.مع وجود رابط إلى رمز PHP النهائي المدرج في التعليق (انقر لتوسيعه) في أسفل الصفحة.

Answer 6

خوارزمية واحدة يجب أن تعمل:

generate-strings(prefix, len, numBits) -> String:
    if (len == 0):
        print prefix
        return
    if (len == numBits):
        print prefix + (len x "1")
    generate-strings(prefix + "0", len-1, numBits)
    generate-strings(prefix + "1", len-1, numBits)

حظ سعيد!

Answer 7

بطريقة أكثر واقعية، ستمنحك الوظيفة أدناه جميع مجموعات المؤشر الممكنة لمشكلة N اختر K التي يمكنك تطبيقها بعد ذلك على سلسلة أو أي شيء آخر:

def generate_index_combinations(n, k):

    possible_combinations = []

    def walk(current_index, indexes_so_far=None):
        indexes_so_far = indexes_so_far or []
        if len(indexes_so_far) == k:
            indexes_so_far = tuple(indexes_so_far)
            possible_combinations.append(indexes_so_far)
            return
        if current_index == n:
            return
        walk(current_index + 1, indexes_so_far + [current_index])
        walk(current_index + 1, indexes_so_far)

    if k == 0:
        return []
    walk(0)
    return possible_combinations

Answer 8

واحد ممكن 1.5 بطانة:

$ python -c 'import itertools; \
             print set([ n for n in itertools.permutations("0111", 4)])'

set([('1', '1', '1', '0'), ('0', '1', '1', '1'), ..., ('1', '0', '1', '1')])

.. أين k هو عدد 1S في "0111".

تشرح وحدة itertools مكافأة أساليبها؛ رؤية ما يعادل طريقة التقليب.

Answer 9

سأحاول الإصابة.

هناك N أرقام مع K منهم 1s. طريقة أخرى لعرض هذا هو التسلسل من فتحات K + 1 مع NK 0S الموزعة بينها. وهذا هو، (تشغيل 0s تليها 1) K مرات، ثم تليها تشغيل آخر من 0s. يمكن أن يكون أي من هذه التشغيل بطول صفر، ولكن يجب أن يكون الطول الإجمالي NK.

تمثل هذا كصفيف من الأعداد الصحيحة K + 1. تحويل إلى سلسلة في الجزء السفلي من العودية.

اتصل بشكل متكرر بالتعمق NK، وهي طريقة تزيد عنصر واحد من الصفيف قبل مكالمة متكررة ثم تنقله، K + 1 مرات.

في عمق NK، خرج السلسلة.

int[] run = new int[k+1];

void recur(int depth) {
    if(depth == 0){
        output();
        return;
    }

    for(int i = 0; i < k + 1; ++i){
        ++run[i];
        recur(depth - 1);
        --run[i];
    }

public static void main(string[] arrrgghhs) {
    recur(n - k);
}

لقد مر بعض الوقت منذ أن فعلت جافا، لذلك ربما هناك بعض الأخطاء في هذا الرمز، ولكن يجب أن تعمل الفكرة.

Answer 10

هي الأوتار أسرع من مجموعة من مجلس الاستثمار؟ جميع الحلول التي تستحضر السلاسل ربما تؤدي إلى نسخة من السلسلة عند كل تكرار.

لذلك ربما تكون الطريقة الأكثر فعالية هي مجموعة من int أو char التي تنجح. جافا لديه حاويات قدرة فعالة، أليس كذلك؟ استخدم ذلك، إذا كان أسرع من السلسلة. أو إذا كان biginteger فعالا، فهو بالتأكيد مدمج، لأن كل بت يأخذ قليلا فقط، وليس بايت كامل أو كثف. ولكن بعد ذلك للتكرار فوق البتات، تحتاج إلى قناع وتقليل قليلا، وقناع bitshift إلى موقع بت القادم. لذلك ربما أبطأ، ما لم تكن محطات الجبهة جيدة في هذه الأيام.

أود نشر هذا التعليق AA على السؤال الأصلي، لكن الكرمة ليست عالية بما فيه الكفاية. آسف.

Answer 11

بيثون (نمط وظيفي)

استخدام python'س itertools.combinations يمكنك توليد جميع خيارات k لدينا من n وخريطة تلك الخيارات إلى مجموعة ثنائية مع reduce

from itertools import combinations
from functools import reduce # not necessary in python 2.x

def k_bits_on(k,n):
       one_at = lambda v,i:v[:i]+[1]+v[i+1:]
       return [tuple(reduce(one_at,c,[0]*n)) for c in combinations(range(n),k)]

مثال على الاستخدام:

In [4]: k_bits_on(2,5)
Out[4]:
[(0, 0, 0, 1, 1),
 (0, 0, 1, 0, 1),
 (0, 0, 1, 1, 0),
 (0, 1, 0, 0, 1),
 (0, 1, 0, 1, 0),
 (0, 1, 1, 0, 0),
 (1, 0, 0, 0, 1),
 (1, 0, 0, 1, 0),
 (1, 0, 1, 0, 0),
 (1, 1, 0, 0, 0)]

Answer 12

حسنا ل هذه السؤال (حيث تحتاج إلى التكرار فوق جميع الحواسم في زيادة ترتيب عدد من البتات المحددة)، والذي تم وضع علامة عليه كنسخة مكررة من هذا.

يمكننا ببساطة التكرار فوق جميع الحواسم الخارجية تضيفها إلى متجه وفرزه وفقا لعدد BITs Set.

vector<int> v;
for(ll i=mask;i>0;i=(i-1)&mask)
    v.push_back(i);
auto cmp = [](const auto &a, const auto &b){
    return __builtin_popcountll(a) < __builtin_popcountll(b);
}
v.sort(v.begin(), v.end(), cmp);

هناك طريقة أخرى هي التكرار على جميع تايمز Subsucks وأضف رقما إلى المتجه إذا كان عدد البتات المحددة يساوي i في iTh التكرار.

كلا الاتجاهين لديها تعقيد O (N * 2 ^ n)