Backtracking Algorithm To Create A "jumbled" But Not Random Array
I have written this backtracking algorithm to make a jumbled-looking array of 70 items from an input array of 10 items. The rules it needs to follow are: No repeat item in each gr
Solution 1:
It's not having too many inputs that's a problem. If you run the code enough times I think that you will find that sometimes it will work, but other times, depending on the result of the shuffle, it's just impossible to fit any of the remaining inputs onto the output array.
It's like playing Solitaire: There might be a solution at the start, but depending on the decisions you make as you go (picking items out of the input array) you might still lose.
You should at a minimum track if you have looped completely through the input array without any success.
If you have looped completely through the input list with no success, you never will. Then you have a couple of options:
- Return the output you have and the remaining input (might be helpful just to see that it failed.
- Whether or not you log the failed attempt, you can then restart and then try again. Just brute force attempts at random to find a solution.
One way to do it:
<!DOCTYPE HTML><html><head><metahttp-equiv="content-type"content="text/html" /><title>Backtracking Pseudo Randomiser</title></head><body><buttononclick=go();>Go</button><script>functiongo() {
var tracker = 0functionpseudoRan(input,output) {
if (output.length==70) {
output=listToMatrix(output,5);
printIt(output);
returntrue;
}
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);
returnpseudoRan(input,output);
}
else {
tracker++
if (tracker > input.length) {
console.log('Failed this time.')
output=listToMatrix(output,5);
console.log('output-----------------------');
printIt(output);
console.log('input------------------------');
printIt(input);
returnfalse// FAILED to finish
}
input.push(tmp);
returnpseudoRan(input,output);
}
}
}
var input=["A","B","C","D","E","F","G","H","I","K"];
input=pool(input,300);
// run until we get an answerdo {
var output=[];
tracker = 0;
// operate on copy of the data
runInput=yatesShuffle(JSON.parse(JSON.stringify(input)));
} while (!pseudoRan(runInput, output))
// analyse itvar 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;
}
}
functionpool(array,total) {
var factor=total/array.length;
var newArray=[];
for (a=0;a<factor;a++) {
for (b=0;b<array.length;b++) {
newArray.push(array[b]);
}
}
//console.log(newArray);return newArray;
}
functionyatesShuffle (array) {
for (var i = array.length - 1; i > 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;
}
functionlistToMatrix(list, elementsPerSubArray) {
var matrix = [], i, k;
for (i = 0, k = -1; i < list.length; i++) {
if (i % elementsPerSubArray === 0) {
k++;
matrix[k] = [];
}
matrix[k].push(list[i]);
}
return matrix;
}
functionprintIt(array) {
for (i=0;i<array.length;i++) {
var str=" ";
for (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><divid="1"style="font-family:'Courier New';"></div><br /><divid="2"></div></body></html>
Post a Comment for "Backtracking Algorithm To Create A "jumbled" But Not Random Array"