إنشاء العديد من التبديلات المقيدة والعشوائية للقائمة
-
01-07-2019 - |
سؤال
أحتاج إلى عمل قائمة عشوائية من التباديل.يمكن أن تكون العناصر أي شيء باستثناء افتراض أنها الأعداد الصحيحة من 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.
المحلول
يمكن تحسين هذا، ولكن يبدو أنه يقوم بالمهمة (بايثون):
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)
نصائح أخرى
حسنًا، إحدى الطرق لتقريب ذلك:
1 - خلط القائمة الخاصة بك
2 - خذ العناصر y الأولى لتكوين الصف التالي
4- كرر (2) ما دام لديك أرقام في القائمة
5 - إذا لم يكن لديك أرقام كافية لإنهاء القائمة، قم بإعادة ترتيب القائمة الأصلية وأخذ العناصر المفقودة، مع التأكد من عدم إعادة الأرقام.
6- ابدأ من الخطوة (2) طالما أنك بحاجة إلى صفوف
أعتقد أن هذا يجب أن يكون عشوائيًا قدر الإمكان وسيتبع بالتأكيد معاييرك.بالإضافة إلى ذلك، لديك اختبارات قليلة جدًا للعناصر المكررة.
أولاً، يمكنك دائمًا فرز القائمة بشكل عشوائي في النهاية، لذلك دعونا لا نقلق بشأن إجراء "تباديل عشوائي" (صعب)؛وما عليك سوى القلق بشأن 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.
بناءً على التفاصيل الجديدة في التعليقات، قد يكون الحل ببساطة هو تنفيذ خوارزمية توليد التقليب العشوائي القياسية.هناك مناقشة مطولة حول خوارزميات توليد التقليب العشوائي هنا:
http://www.techuser.net/randpermgen.html
(من بحث جوجل:توليد التقليب العشوائي)
هذا يعمل في روبي:
# 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