إنشاء العديد من التبديلات المقيدة والعشوائية للقائمة

Question

أحتاج إلى عمل قائمة عشوائية من التباديل.يمكن أن تكون العناصر أي شيء باستثناء افتراض أنها الأعداد الصحيحة من 0 إلى x-1.أريد إنشاء قوائم y، تحتوي كل منها على عناصر z.القواعد هي أنه لا يجوز لأي قائمة أن تحتوي على نفس العنصر مرتين، وأنه في جميع القوائم، يكون عدد مرات استخدام كل عنصر هو نفسه (أو أقرب ما يمكن).على سبيل المثال، إذا كانت عناصري هي 0,1,2,3، وy هي 6، وz هي 2، فإن أحد الحلول الممكنة هو:

0,3
1,2
3,0
2,1
0,1
2,3

يحتوي كل صف على عناصر فريدة فقط ولم يتم استخدام أي عنصر أكثر من 3 مرات.إذا كان y 7، فسيتم استخدام عنصرين 4 مرات، والباقي 3.

Answer 1

يمكن تحسين هذا، ولكن يبدو أنه يقوم بالمهمة (بايثون):

import math, random


def get_pool(items, y, z):
    slots = y*z

    use_each_times = slots/len(items)
    exceptions = slots - use_each_times*len(items)


    if (use_each_times > y or
        exceptions > 0 and use_each_times+1 > y):
        raise Exception("Impossible.")


    pool = {}
    for n in items:
        pool[n] = use_each_times

    for n in random.sample(items, exceptions):
        pool[n] += 1

    return pool

def rebalance(ret, pool, z):
    max_item = None
    max_times = None

    for item, times in pool.items():
        if times > max_times:
            max_item = item
            max_times = times


    next, times = max_item, max_times

    candidates = []
    for i in range(len(ret)):
        item = ret[i]

        if next not in item:
            candidates.append( (item, i) )


    swap, swap_index = random.choice(candidates)

    swapi = []
    for i in range(len(swap)):
        if swap[i] not in pool:
            swapi.append( (swap[i], i) )


    which, i = random.choice(swapi)

    pool[next] -= 1
    pool[swap[i]] = 1
    swap[i] = next

    ret[swap_index] = swap

def plist(items, y, z):
    pool = get_pool(items, y, z)

    ret = []
    while len(pool.keys()) > 0:
        while len(pool.keys()) < z:
            rebalance(ret, pool, z)

        selections = random.sample(pool.keys(), z)

        for i in selections:
            pool[i] -= 1
            if pool[i] == 0:
                del pool[i]

        ret.append( selections )

    return ret


print plist([0,1,2,3], 6, 2)

Answer 2

حسنًا، إحدى الطرق لتقريب ذلك:

1 - خلط القائمة الخاصة بك

2 - خذ العناصر y الأولى لتكوين الصف التالي

4- كرر (2) ما دام لديك أرقام في القائمة

5 - إذا لم يكن لديك أرقام كافية لإنهاء القائمة، قم بإعادة ترتيب القائمة الأصلية وأخذ العناصر المفقودة، مع التأكد من عدم إعادة الأرقام.

6- ابدأ من الخطوة (2) طالما أنك بحاجة إلى صفوف

أعتقد أن هذا يجب أن يكون عشوائيًا قدر الإمكان وسيتبع بالتأكيد معاييرك.بالإضافة إلى ذلك، لديك اختبارات قليلة جدًا للعناصر المكررة.

Answer 3

أولاً، يمكنك دائمًا فرز القائمة بشكل عشوائي في النهاية، لذلك دعونا لا نقلق بشأن إجراء "تباديل عشوائي" (صعب)؛وما عليك سوى القلق بشأن 1) إجراء التباديل (سهل) و2) توزيعها بشكل عشوائي (سهل).

إذا كنت تريد مجموعات عشوائية "حقًا"، عليك أن تقبل أن التوزيع العشوائي بطبيعته لا يسمح حقًا بتقييد "التوزيع المتساوي" للنتائج - فقد تحصل على ذلك أو قد تحصل على مجموعة من النتائج المتشابهة.إذا كنت تريد حقًا التوزيع المتساوي، قم أولاً بتوزيع المجموعات بالتساوي، ثم قم بتوزيعها بشكل عشوائي كمجموعة.

هل يجب عليك استخدام كل عنصر في المجموعة x بالتساوي؟ليس من الواضح من القواعد أنني لا أستطيع تقديم التفسير التالي:

لاحظ ما يلي:"في جميع القوائم، يكون عدد مرات استخدام كل عنصر هو نفسه (أو أقرب ما يمكن)"

بناءً على هذه المعايير، والقاعدة التي تنص على أن z < x*، أفترض أنه يمكنك ببساطة تعداد جميع العناصر الموجودة في جميع القوائم.لذلك تقوم تلقائيًا بإنشاء قائمة y بالعناصر التي تم تعدادها في الموضع z.المثال الخاص بك لا يفي بالقاعدة المذكورة أعلاه بنفس القدر الذي ستفعله نسختي.باستخدام مثالك على x={0,1,2,3} y=6 وz=2، أحصل على:0,1 0,1 0,1 0,1 0,1 0,1

الآن لم أستخدم 2 أو 3، لكنك لم تقل أنه يجب علي استخدامهم جميعًا.إذا اضطررت إلى استخدامها جميعًا ولا يهمني أن أكون قادرًا على إثبات أنني "أقرب ما يمكن" من الاستخدام المتساوي، فسأقوم فقط بإدراج جميع العناصر من خلال القوائم، مثل هذا:0,1 2,3 0,1 2,3 0,1 2,3

أخيرًا، لنفترض أنه يتعين عليّ حقًا استخدام جميع العناصر.لحساب عدد المرات التي يمكن أن يتكرر فيها كل عنصر، أقوم فقط بأخذ (y*z)/(count of x).وبهذه الطريقة، لن أضطر إلى الجلوس والقلق بشأن كيفية تقسيم العناصر الموجودة في القائمة.إذا كان هناك باقي، أو كانت النتيجة أقل من 1، فأنا أعلم أنني لن أحصل على عدد محدد من التكرارات، لذلك في تلك الحالات، لا يهم كثيرًا محاولة إهدار الطاقة الحسابية لجعلها مثالية.أنا أزعم أن النتيجة الأسرع لا تزال قائمة كما هو مذكور أعلاه، واستخدام الحساب هنا لإظهار سبب تحقيق أو عدم تحقيق نتيجة مثالية.يمكن تحقيق خوارزمية رائعة لاستخراج عدد المواضع التي ستكون مكررة من هذا الحساب، ولكن "الأمر طويل جدًا بحيث لا يمكن احتواؤه هنا في الهامش".

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

Answer 4

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

http://www.techuser.net/randpermgen.html

(من بحث جوجل:توليد التقليب العشوائي)

Answer 5

هذا يعمل في روبي:

# list is the elements to be permuted
# y is the number of results desired
# z is the number of elements per result
# equalizer keeps track of who got used how many times
def constrained_permutations list, y, z
  list.uniq! # Never trust the user. We want no repetitions.
  equalizer = {}
  list.each { |element| equalizer[element] = 0 }

  results = []
  # Do this until we get as many results as desired
  while results.size < y
    pool = []
    puts pool
    least_used = equalizer.each_value.min
    # Find how used the least used element was
    while pool.size < z
      # Do this until we have enough elements in this resultset
      element = nil
      while element.nil?
        # If we run out of "least used elements", then we need to increment
        # our definition of "least used" by 1 and keep going.
        element = list.shuffle.find do |x|
          !pool.include?(x) && equalizer[x] == least_used
        end
        least_used += 1 if element.nil?
      end
      equalizer[element] += 1
      # This element has now been used one more time.
      pool << element
    end
    results << pool
  end
  return results
end

استخدام العينة:

constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 0], [1, 3], [2, 5], [6, 0], [2, 5], [3, 6]]
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 5], [6, 3], [0, 2], [1, 6], [5, 4], [3, 0]]
enter code here

Answer 6

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle