किसी ऑब्जेक्ट के तत्वों को यादृच्छिक रूप से किसी अन्य सरणी के रूप में कैसे चिह्नित करें जब कुछ वस्तुओं को एक साथ जोड़ा जाने से बचना चाहिए?

Question

मैं एक ऐसा गेम बना रहा हूं जिसमें खिलाड़ियों को स्क्रीन पर ऑब्जेक्ट को सही लक्ष्य स्थानों में सॉर्ट करने की आवश्यकता होगी। मैं ऑब्जेक्ट्स को घुमाने के लिए एक रास्ता ढूंढ रहा हूं ताकि कोई ऑब्जेक्ट सही स्थान पर शुरू न हो। इसलिए हम डबल नकारात्मकों की पागल दुनिया में नहीं भरे हैं, मैं इस तरह के "सही उत्तर" स्थानों को "से बचने" स्थानों और "गलत उत्तर" स्थानों को "मान्य" स्थान कहने जा रहा हूं।

सरणियों इस प्रकार दिखाई देंगे:

var sort_items = [ 
    {"avoid": ["target1", "target2"]}, 
    {"avoid": ["target1", "target2"]}, 
    {"avoid": ["target3"]}, 
    {"avoid": ["target4", "target5"]}, 
    {"avoid": ["target4", "target5"]}, 
]; 

var sort_locations = [ 
    {"id": "target1"}, 
    {"id": "target2"}, 
    {"id": "target3"}, 
    {"id": "target4"}, 
    {"id": "target5"}, 
]; 

तो, उदाहरण के लिए, sort_items में पहली और दूसरी वस्तुओं target3, target4, या , लेकिन नहीं target1 या target2 पर रखा जा सकता है।

मैंने कई अलग-अलग तरीकों की कोशिश की है, लेकिन उनमें से सभी को समस्या है कि क्रम के अंत तक शेष शेष स्थान शेष sort_items के लिए अक्सर अमान्य होते हैं। उदाहरण के लिए:

sort_items[0] placed on target3, 
sort_items[1] placed on target5, 
sort_items[2] placed on target2, 
sort_items[3] placed on target1, 
Error: sort_items[4] cannot be placed on target4 

यहां तक ​​कि इस उदाहरण में, यादृच्छिक पर एक और उठा और अदला-बदली के साथ यह एक बुरा विचार की तरह लगता है क्योंकि दूसरों के आधे भी एक स्वैप पर गलत मैच का कारण होगा।

क्या ऐसा करने के लिए एक अच्छी विधि है?

Answer 1

यदि आप यह गारंटी देना चाहते हैं कि प्रत्येक आइटम की उस स्थिति में से किसी एक पर समाप्त होने की समान संभावनाएं हैं, जिस पर इसे लागू करने की अनुमति दी गई है, बिना किसी प्रक्रिया के प्रेरित किए गए पूर्वाग्रहों से प्रेरित, मैं यह सोचने के इच्छुक हूं कि एक पूरी तरह से यादृच्छिक सूची के साथ शुरू करने के लिए केवल 'आसान' तरीका है।

फिर, आप सूची के माध्यम से चल सकते हैं और प्रत्येक अमान्य आइटम को उसके बाद सामना करने वाले पहले वैध आइटम को स्वैप करने का प्रयास कर सकते हैं।

// initial random list 
["target1", "target5", "target2", "target4", "target3"] 
// 1st position is invalid -> swap "target1" and "target5" 
["target5", "target1", "target2", "target4", "target3"] 
// 2nd position is invalid -> swap "target1" and "target2" 
["target5", "target2", "target1", "target4", "target3"] 
// 2nd position is still invalid -> swap "target2" and "target4" 
["target5", "target4", "target1", "target2", "target3"] 
// -> valid list 

यह हर बार सफल नहीं होगा:

दरअसल, नीचे एल्गोरिथ्म यह इस तरह से कर रही है। और जब यह विफल हो जाता है, तो आपको स्क्रैच से पुनरारंभ करना होगा।

यह किसी दिए गए क्रम में स्लॉट को एक-एक करके भरने की कोशिश करने से अधिक उचित है, और जब तक हमें वैध नहीं मिलता है तब तक सूची को शफ़ल करने से अधिक कुशल होता है।

(कि हम यह खारिज करने से पहले 'फिक्स' यह करने के लिए प्रयास करें।)

var sort_items = [ 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target3"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
    {"avoid": ["target4", "target5"]} 
 
]; 
 
var sort_locations = [ 
 
    {"id": "target1"}, 
 
    {"id": "target2"}, 
 
    {"id": "target3"}, 
 
    {"id": "target4"}, 
 
    {"id": "target5"} 
 
]; 
 

 
var list = sort_locations.map(function(i) { return i.id; }); 
 

 
while(!list.every(function(item, i) { 
 
    for(var j = i + 1; sort_items[i].avoid.indexOf(item) != -1; j++) { 
 
    if(j == list.length) { 
 
     return false; 
 
    } 
 
    item = list[j]; 
 
    list[j] = list[i]; 
 
    list[i] = item; 
 
    } 
 
    return true; 
 
})) { 
 
    list.sort(function() { return Math.random() < 0.5 ? -1 : 1; }); 
 
} 
 
console.log(list);

संपादित मैं कुछ आगे परीक्षण जो संकेत मिलता है कि यह अभी भी अधिक पक्षपाती की तुलना में मैं था है किया यह होने की उम्मीद है।

इसके लायक होने के लिए, यहां एक सरल, 100% परीक्षण-और-त्रुटि संस्करण है। यह निष्पक्ष होने की गारंटी है।

var sort_items = [ 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target3"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
    {"avoid": ["target4", "target5"]} 
 
]; 
 

 
var sort_locations = [ 
 
    {"id": "target1"}, 
 
    {"id": "target2"}, 
 
    {"id": "target3"}, 
 
    {"id": "target4"}, 
 
    {"id": "target5"} 
 
]; 
 

 
var list = sort_locations.map(function(i) { return i.id; }); 
 

 
while(!list.every(function(item, i) { 
 
    return sort_items[i].avoid.indexOf(item) == -1; 
 
})) { 
 
    list.sort(function() { return Math.random() < 0.5 ? -1 : 1; }); 
 
} 
 
console.log(list);

Answer 2

यहाँ एक समाधान है कि प्रत्यावर्तन के माध्यम से सभी संभव समाधान उत्पन्न करता है, और फिर एक यादृच्छिक एक उठाता है।यादृच्छिक परीक्षण-और-त्रुटि समाधानों की तुलना में, यह तेजी से परिणाम दे सकता है जहां समाधान की संख्या बहुत इनपुट के आकार की तुलना में सीमित है।

दूसरा, यह गारंटी देता है कि प्रत्येक समाधान को उठाए जाने की समान संभावना होती है।

ध्यान दें कि स्क्रिप्ट को ES6 समर्थन की आवश्यकता है।

function findSolutions(items, locations) { 
 
    // Transform the data structure to a simple array of Sets with allowed location numbers per item number, to avoid costly `indexOf` calls. 
 
    var locNums = locations.map((o, i) => i); 
 
    var locs = locations.reduce((o, loc, i) => Object.assign(o, { [loc.id]: i }) , {}); 
 
    var allowed = items.map(item => { 
 
     var allowed = new Set(locNums); 
 
     item.avoid.forEach(loc => allowed.delete(locs[loc])); 
 
     return allowed; 
 
    }); 
 
    // Now find all possible solutions through recursion 
 
    var occupied = new Set(); 
 
    var solutions = []; 
 
    var solution = []; 
 
    (function recurse(itemNo) { 
 
     var loc; 
 
     if (itemNo >= allowed.length) { 
 
      solutions.push(solution.slice()); 
 
      return; 
 
     } 
 
     for (loc of allowed[itemNo]) { 
 
      if (!occupied.has(loc)) { 
 
       solution.push(locations[loc].id); 
 
       occupied.add(loc); 
 
       recurse(itemNo+1); 
 
       occupied.delete(loc); 
 
       solution.pop(); 
 
      } 
 
     } 
 
    })(0); 
 
    return solutions; 
 
} 
 

 
// Sample data 
 
var sort_items = [ 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target1", "target2"]}, 
 
    {"avoid": ["target3"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
    {"avoid": ["target4", "target5"]}, 
 
]; 
 

 
var sort_locations = [ 
 
    {"id": "target1"}, 
 
    {"id": "target2"}, 
 
    {"id": "target3"}, 
 
    {"id": "target4"}, 
 
    {"id": "target5"}, 
 
]; 
 

 
// Get all solutions 
 
var solutions = findSolutions(sort_items, sort_locations); 
 

 
// Pick random solution from it 
 
var randomSolution = solutions[Math.floor(Math.random() * solutions.length)]; 
 

 
// Output result 
 
console.log(randomSolution);