javascript - Backtracking algorithm to create a "jumbled" but not random array -
i have written backtracking algorithm make jumbled-looking array of 70 items input array of 10 items. rules needs follow are:
- no repeat item in each group of 5
- no item appears in same position in of 3 consecutive groups of 5
- each item appears 7 times in total
this works, if make input array bigger output array, breaks rule 3. if make input array length 70, algorithm works overflows.
<!doctype html> <html> <head> <meta http-equiv="content-type" content="text/html" /> <title>backtracking pseudo randomiser</title> </head> <body> <button onclick=go();>go</button> <script> function go() { function pseudoran(input,output) { if (output.length==70) { output=listtomatrix(output,5); printit(output); return; } else { var tmp=input.shift(); var mod=output.length % 5; if (output.slice(-mod-1).indexof(tmp)==-1 && output[output.length-5]!=tmp && output[output.length-10]!=tmp) { output.push(tmp); pseudoran(input,output); } else { input.push(tmp); pseudoran(input,output); } } } var input=["a","b","c","d","e","f","g","h","i","k"]; var output=[]; input=pool(input,70); input=yatesshuffle(input); pseudoran(input, output); //analyse var freqs=output.bycount(); var strfreqs=""; for(a=0;a<freqs.length;a++){ strfreqs+="item: " + freqs[a].item + " ..." + freqs[a].frequency + "<br />"; document.getelementbyid("2").innerhtml=strfreqs; } } function pool(array,total) { var factor=total/array.length; var newarray=[]; (a=0;a<factor;a++) { (b=0;b<array.length;b++) { newarray.push(array[b]); } } //console.log(newarray); return newarray; } function yatesshuffle (array) { (var = array.length - 1; > 0; i--) { var j = math.floor(math.random() * i); // no +1 here! var temp = array[i]; array[i] = array[j]; array[j] = temp; } return array; } function listtomatrix(list, elementspersubarray) { var matrix = [], i, k; (i = 0, k = -1; < list.length; i++) { if (i % elementspersubarray === 0) { k++; matrix[k] = []; } matrix[k].push(list[i]); } return matrix; } function printit(array) { (i=0;i<array.length;i++) { var str=" "; (j=0;j<array[i].length;j++) { str+=array[i][j]+" "; } document.getelementbyid("1").insertadjacenthtml('beforeend',str + "</br>"); //console.log(array[i]); } } array.prototype.bycount= function(){ var itm, a= [], l= this.length, o= {}; for(var i= 0; i<l; i++){ itm= this[i]; if(!itm) continue; if(o[itm]== undefined) o[itm]= 1; else ++o[itm]; } for(var p in o) a[a.length]= {item: p, frequency: o[p]}; return a.sort(function(a, b){ return o[b.item]-o[a.item]; }); } </script> <div id="1" style="font-family:'courier new';"></div> <br /> <div id="2"></div> </body> </html>
it's not having many inputs that's problem. if run code enough times think find work, other times, depending on result of shuffle, it's impossible fit of remaining inputs onto output array.
it's playing solitaire: there might solution @ start, depending on decisions make go (picking items out of input array) might still lose.
you should @ minimum track if have looped through input array without success.
if have looped through input list no success, never will. have couple of options:
- return output have , remaining input (might helpful see failed.
- whether or not log failed attempt, can restart , try again. brute force attempts @ random find solution.
one way it:
<!doctype html> <html> <head> <meta http-equiv="content-type" content="text/html" /> <title>backtracking pseudo randomiser</title> </head> <body> <button onclick=go();>go</button> <script> function go() { var tracker = 0 function pseudoran(input,output) { if (output.length==70) { output=listtomatrix(output,5); printit(output); return true; } else { var tmp=input.shift(); var mod=output.length % 5; console.log('input.length::tracker ==>', input.length + '::' + tracker) if (output.slice(-mod-1).indexof(tmp)==-1 && output[output.length-5]!=tmp && output[output.length-10]!=tmp) { tracker = 0 output.push(tmp); return pseudoran(input,output); } else { tracker++ if (tracker > input.length) { console.log('failed time.') output=listtomatrix(output,5); console.log('output-----------------------'); printit(output); console.log('input------------------------'); printit(input); return false // failed finish } input.push(tmp); return pseudoran(input,output); } } } var input=["a","b","c","d","e","f","g","h","i","k"]; input=pool(input,300); // run until answer { var output=[]; tracker = 0; // operate on copy of data runinput=yatesshuffle(json.parse(json.stringify(input))); } while (!pseudoran(runinput, output)) // analyse var freqs=output.bycount(); var strfreqs=""; for(a=0;a<freqs.length;a++){ strfreqs+="item: " + freqs[a].item + " ..." + freqs[a].frequency + "<br />"; document.getelementbyid("2").innerhtml=strfreqs; } } function pool(array,total) { var factor=total/array.length; var newarray=[]; (a=0;a<factor;a++) { (b=0;b<array.length;b++) { newarray.push(array[b]); } } //console.log(newarray); return newarray; } function yatesshuffle (array) { (var = array.length - 1; > 0; i--) { var j = math.floor(math.random() * i); // no +1 here! var temp = array[i]; array[i] = array[j]; array[j] = temp; } return array; } function listtomatrix(list, elementspersubarray) { var matrix = [], i, k; (i = 0, k = -1; < list.length; i++) { if (i % elementspersubarray === 0) { k++; matrix[k] = []; } matrix[k].push(list[i]); } return matrix; } function printit(array) { (i=0;i<array.length;i++) { var str=" "; (j=0;j<array[i].length;j++) { str+=array[i][j]+" "; } document.getelementbyid("1").insertadjacenthtml('beforeend',str + "</br>"); console.log(array[i]); } } array.prototype.bycount= function(){ var itm, a= [], l= this.length, o= {}; for(var i= 0; i<l; i++){ itm= this[i]; if(!itm) continue; if(o[itm]== undefined) o[itm]= 1; else ++o[itm]; } for(var p in o) a[a.length]= {item: p, frequency: o[p]}; return a.sort(function(a, b){ return o[b.item]-o[a.item]; }); } </script> <div id="1" style="font-family:'courier new';"></div> <br /> <div id="2"></div> </body> </html>
Comments
Post a Comment