回溯算法以创建“混乱"的算法.但不是随机数组 [英] Backtracking algorithm to create a "jumbled" but not random array
问题描述
我已经编写了此回溯算法，以从10个项目的输入数组中制作出一个由70个项目组成的混乱数组.它需要遵循的规则是:
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:
- 每5个一组中没有重复的项目
- 在5个连续的3组中，没有一个项目出现在同一位置
- 每个项目总共出现7次
这几乎可行，但前提是我使输入数组大于输出数组，这会破坏规则3.如果我使输入数组的长度为70，则算法有时会起作用，但有时会溢出.
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:
- 返回您拥有的输出和其余的输入(可能会发现输出失败可能会有所帮助.
- 无论您是否记录失败的尝试，都可以重新启动，然后重试.只是蛮力试图随机找到解决方案.
一种方法:
<!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>
这篇关于回溯算法以创建“混乱"的算法.但不是随机数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
