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:
This almost works, but only if I make my input array bigger than my output array, which then breaks rule 3. If I make my input array length 70, the algorithm sometimes works but sometimes 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 it
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=[];
for (a=0;a<factor;a++) {
for (b=0;b<array.length;b++) {
newArray.push(array[b]);
}
}
//console.log(newArray);
return newArray;
}
function yatesShuffle (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;
}
function listToMatrix(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;
}
function printIt(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>
<div id="1" style="font-family:'Courier New';"></div>
<br />
<div id="2"></div>
</body>
</html>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:
One way to do 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 this time.')
output=listToMatrix(output,5);
console.log('output-----------------------');
printIt(output);
console.log('input------------------------');
printIt(input);
return false // FAILED to 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 we get an answer
do {
var output=[];
tracker = 0;
// operate on copy of the data
runInput=yatesShuffle(JSON.parse(JSON.stringify(input)));
} while (!pseudoRan(runInput, output))
// analyse it
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=[];
for (a=0;a<factor;a++) {
for (b=0;b<array.length;b++) {
newArray.push(array[b]);
}
}
//console.log(newArray);
return newArray;
}
function yatesShuffle (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;
}
function listToMatrix(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;
}
function printIt(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>
<div id="1" style="font-family:'Courier New';"></div>
<br />
<div id="2"></div>
</body>
</html>