www.webdeveloper.com
Results 1 to 8 of 8

Thread: [ASK/HELP] Make shuffle of array not same (per index) with previous array

  1. #1
    Join Date
    Nov 2012
    Posts
    4

    Question [ASK/HELP] Make shuffle of array not same (per index) with previous array

    I have some assignment to make a game n i choose the game puzzle like sudoku (more like Elemental at Android, if you had play this game). well, with think so long, i think i need to make arrays of number for each row which each indexs of arrays cannot be same to make 1 column and 1 row consist of 1 full array (without same number at one arrangement of array).

    so i have made one and near of success because sometime the result as i want, sometime not. the problem is sometime there was arrays with "undefined" and the time took longer than the right results.

    please, i really need your help to complete my codes. or maybe you can give me another codes that same with i need. i had search for it, but i can't find that i need.

    Code:
    <head>
    <style type="text/css">
    	td	{ border:1px solid #ccc; text-align:center; padding:0.3em }
    </style>
    <script type="text/javascript">
    function showArray(){
    	var firstArray = ['1','2','3','4','5'];
    	var sizeArray = firstArray.length;
    	var compArray = new Array();
    	var t = document.getElementById('tes');
    	
    	//make array for row
    	var row=0;
    	while(row<sizeArray){
    		var shufArray = arrayShuffle(firstArray);
    		var tr = t.appendChild(document.createElement('tr'));
    		
    		if(compArray.length>0)
    			var shufArray = makeShuffle(shufArray, compArray);
    		
    		//write the array for one row
    		for (var i=0,col=0;col<sizeArray;col++)
    			tr.appendChild(document.createElement('td')).innerHTML = shufArray[i++];
    			
    		compArray.push(shufArray); //<-- add shufArray to compArray => become reference for next row
    			
    		row++;
    	}
    }
    
    //function to cek shufArray, ensure to not same with previous arrays per indexs
    function makeShuffle(oldShufArray, shufArrayAll){
    	var shufArray2 = new Array();
    	var temp = oldShufArray;
    	for(j=0;j<=(oldShufArray.length-1);j++){
    		var compArray2 = new Array();
    		
    		//array from shufArray, where index=j
    		for(x=0;x<=(shufArrayAll.length-1);x++)
    			compArray2.push(shufArrayAll[x][j]);
    		
    		//if temp[j] not in compArray2 and shufArray2
    		if(compArray2.indexOf(temp[j])<0 && shufArray2.indexOf(temp[j])<0){
    			shufArray2.push(temp[j]); //<-- pust into shufArray2
    		}else{
    			sliceArray = temp.slice(j);
    			shufSliceArray = arrayShuffle(sliceArray); //<-- slice temp from j that problematic
    			temp = shufArray2.concat(shufSliceArray); //<-- merge with previous index that didnt have problem
    			j-=1; //<-- set j-1 so the next j become now j
    		}
    	}
    	
    	return shufArray2;
    }
    
    //function to shuffle array, i get from searching in google
    function arrayShuffle(oldArray) {
    	var newArray = oldArray.slice();
     	var len = newArray.length;
    	var i = len;
    	while(i--){
    	//for(i=len-1;i>=0;i--){
    		var p = parseInt(Math.random()*len);
    		var t = newArray[i];
      		newArray[i] = newArray[p];
    	  	newArray[p] = t;
     	}
    	return newArray; 
    };
    </script>    
    </head>
    
    <body onLoad="showArray();">
    <table><tbody id="tes"></tbody></table>
    </body>
    thanks before. i hope you can help me

  2. #2
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,273
    You will probably build all the 5x5 «Sudoku» grids (without sub-grid) ?

    Some elements...

    It's probably easier to work with the 5!=120 permutations of 1,2,3,4 and 5.
    These permutations are constructed and stored as follows by breaking their ranks of 4!, 3!, 2!, and 1!.

    Code:
    <script type="text/javascript">
    function prm(n){
    	var i,s='12345',t=[24,6,2,1],p='',j;
    	for (i=0;i<5;i++) {j=Math.floor(n/t[i]);n%=t[i];
    		p+=s.substr(j,1);s=s.substr(0,j)+s.substr(j+1);}
      return p;
    }
    var c=[];
    for (i=0;i<120;i++) c[c.length]=prm(i);
    alert(c);
    
    </script>
    Then you have probably to work only with arrays or strings of length 25. The lines are given by dividing the rank (from 0 to 24) by 5 line=Math.floor(rank) and the column=rank%5;

    The first line could be 12345 (it's always possible to apply a permutation to find the others solutions =>x120 solutions)...

    EDIT : When you have a solution. It's possible to permute all the lines except for the first (=>x24 solutions).
    Last edited by 007Julien; 11-21-2012 at 09:03 AM. Reason: complement

  3. #3
    Join Date
    Nov 2012
    Posts
    4
    thanks for the solution
    really, i didn't think to use permutation.
    but, i'm so sorry, i can't understand yet about this :
    The lines are given by dividing the rank (from 0 to 24) by 5 line=Math.floor(rank) and the column=rank%5;
    can u explain it more? maybe because my english so bad, so i can't catch mean of that sentence.

    thanks before

  4. #4
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,273
    My English is to a bit random...

    I just wanted to say that a solution can be described either by a string or an array. Then the n-th element (n from 0 to 24) is in the Math.floor(n/5)-th line (from 0 to 4) and in the (n%5)-th column (from 0 to 4).

    It's probably difficult to find solution with random shuffles !

    We have probably to avoid DOM manipulation, with somethings like the followings ?

    Code:
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <html>
    <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta name="generator" content="PSPad editor, www.pspad.com">
    <title>Sudoku 5x5</title>
    <style type="text/css">
    p {display:block;width:56px;float:left;margin:2px; 
    </style>
    </head>
    <body>
    <div id="rsp"></div>
    <script type="text/javascript">
    
    // A string to describe a solution
    var strSol='42315 54231 25143 13524 31452';
    
    // A javascript String (without spaces) 
    var stjSol=strSol.replace(/ /g,'');
    
    // An array to describe the same solution 
    var arrSol=stjSol.split('');
    
    // A htmlCode to show the solution
    function html(stj){
    	var h='<p>'+stj.replace(/(\d)(?=([\d]{5})+($|<))/g,'$1<br>')+'<p>';
    	document.getElementById('rsp').innerHTML+=h;
    }
    html(stjSol);
    
    // This solution can be permute to transform the first column => 12345
    function toStandardFirstCol(str){var i,s,a=[];
    	for (i=0;i<5;i++) {s=str.substr(5*i,5);a[s.substr(0,1)]=s;}
    	return a.join('');
    }
    stjStl=toStandardFirstCol(stjSol);
    html(stjStl);
    
    // This solution can be permute to transform the first line => 12345
    function toStandardFirstLine(str){var i,j,a=str.split(''),r=[],c;
    	for (i=0;i<5;i++) {
    		c=a[i]-1; // The first line elem give the new col
    		for (j=0;j<5;j++) r[5*j+c]=a[5*j+i];}
    	return r.join('');
    }
    stjStd=toStandardFirstLine(stjStl);
    html(stjStd);
    </script>
    </body>
    </html>
    Then the problem is to find all the standard solutions...

  5. #5
    Join Date
    Nov 2012
    Posts
    4
    wow..
    thank you very much, Julien.
    really, your solutions help me so much

    thank you, thank you..

    just reference to others, i'll share my codes with based from 007Julien's solution of permutations (or maybe you or the others can tell me other codes like this but more efficient)

    Code:
    <html>
    <head>
    <style type="text/css">
    	td	{ border:1px solid #ccc; text-align:center; padding:0.3em }
    </style>
    <script type="text/javascript">
    function buildNum(firstNum, amountNum){
    	var lastNum = firstNum + (amountNum-1);
    	var c=[],resPrm,amountPrm,arr=[],index,conTable='';
    	
    	for(resPrm=1,j=amountNum;j>1;j--)
    		resPrm *= j;
    	
    	amountPrm = resPrm/amountNum;
    	
    	//create array 2 dimension c[i][j] with i=amountNum and j=amountPrm
    	for (var x=0;x<amountNum;x++){
    		c[x]=[];
    		for (i=x*amountPrm;i<(x*amountPrm)+amountPrm;i++)
    			c[x][c[x].length]=prm(i,firstNum,lastNum);
    	}
    	
    	//create array for rows table. array per rows take from c[i][j] with i=index of rows, j=generate random 0-amountPrm and check the array with previous arrays
    	for(var x=0;x<amountNum;x++){
    		index = getRandom(0,amountPrm);
    		if(arr.length==0)
    			arr.push(c[x][index]);
    		else{
    			temp = [];
    			for(var i=0;i<amountNum;i++){
    				temp[i]=[];
    				for(j=0;j<arr.length;j++){
    					temp[i][j] = arr[j][i];
    				}
    			}
    			
    			for(var test=true,les=0,i=0;i<amountNum;i++){
    				if(temp[i].indexOf(c[x][index][i])>0){
    					test=test&&amp;amp;false;
    					if(les==0)
    						les=1;
    				}else
    					test=test&&amp;amp;true;
    			}	
    			
    			if(test)
    				arr.push(c[x][index]);
    			if(les>0)
    				x-=1;
    		}
    	}
    	
    	var shufArr = arrayShuffle(arr);
    	
    	//write to conTable
    	for(i=0;i<amountNum;i++){
    		conTable += "<tr>";
    		
    		for(j=0;j<shufArr[i].length;j++)
    			conTable += "<td>"+shufArr[i][j]+"</td>";
    			
    		conTable += "</tr>";
    	}
    	document.getElementById("test").innerHTML = conTable;
    };
    
    function prm(n,firstNum,lastNum){
    	var i,s='',temp,t=[],p=[],j;
    	for(i=firstNum;i<=lastNum;i++)
    		s+=i;
    	temp=s;
    	
    	for(i=s.length-1;i>0;i--){
    		for(x=1,j=i;j>1;j--)
    			x=x*j;
    		t.push(x);
    	}
    
    	for (i=0;i<temp.length;i++){
    		j=Math.floor(n/t[i]);
    		n%=t[i];
    		p.push(s.substr(j,1));
    		s=s.substr(0,j)+s.substr(j+1);
    	}
      return p;
    };
    
    function getRandom(min, max) {
        return Math.floor(Math.random() * (max - min) + min);
    };
    
    function arrayShuffle(oldArray) {
    	var newArray = oldArray.slice();
     	var len = newArray.length;
    	var i = len;
    	 while (i--) {
    	 	var p = parseInt(Math.random()*len);
    		var t = newArray[i];
      		newArray[i] = newArray[p];
    	  	newArray[p] = t;
     	}
    	return newArray; 
    };
    </script>
    </head>
    
    <body onload="buildNum(1,4)">
    <table><tbody id="test"></tbody></table>
    </body>
    </html>
    Last edited by narino; 11-22-2012 at 11:29 AM.

  6. #6
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,273
    A little script which give all the solutions (56) with standard first line and first column.
    Code:
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <html>
    <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta name="generator" content="PSPad editor, www.pspad.com">
    <title>Sudoku 5x5</title>
    <style type="text/css">
    body{font-family:Courier,monospace}
    p {display:block;width:56px;float:left;margin:2px;padding:0;border:1px solid red} 
    div {diplay:block;margin:0 auto;padding:0;width:880px;}
    </style>
    </head>
    <body>
    <div id="rsp"></div>
    
    <script type="text/javascript">
    // To see simple objects like array with alert 
    Object.prototype.toString=function(){var i,s='';for(i in this) s+=i+':'+this[i]+' ';return s}
    
    // The 120 permutations of '12345'
    function prm(n){
    	var i,s='12345',t=[24,6,2,1,1],p='',j;
    	for (i=0;i<5;i++) {j=Math.floor(n/t[i]);n%=t[i];
    		p+=s.substr(j,1);s=s.substr(0,j)+s.substr(j+1);}
      return p;
    }
    // Column constructor  
    function Column(k,v){this[k]=v}
    
    // Test a new line (str) in comparaison with the preceding in form of oldCols (an array of 5 Columns)  
    function tstNewline(str,oldCols){ var i,t=str.split('');
    	// There is no need to test the first column (i=5;while (i) if (oldCols[--i][t[i]]) return false;)
    	i=5;while (--i) if (oldCols[i][t[i]]) return false;
    	return true;
    }
    // To show the string 
    function html(stj){
    	var h='<p>'+stj.replace(/(\d)(?=([\d]{5})+($|<))/g,'$1<br>')+' </p>';
    	document.getElementById('rsp').innerHTML+=h;
    }
    var oldLvl=7;
     
    function search(prv){var i,l,c,oldCols=[],lng=prv.length,lvl=lng/5;
    	// oldCols an array of Columns which values are true for all the integers of the previous lines
    	for (i=0;i<lng;i++){
    		// Construction of objects with the first line
    		if (i<5) oldCols[i]=new Column(prv[i],true);
    		// Updated with the following
    		else oldCols[i%5][prv[i]]=true;}
    	// To add a new line beginning with lvl 	
    	for (i=24*lvl,l=i+24;i<l;i++) {c=prm(i); 
    		if (tstNewline(c,oldCols)) {
    			// to uncomment to see the process		
    		  	// if (lvl<oldLvl) document.getElementById('rsp').innerHTML+='<p style="clear:both">&nbsp;</p>';newLine=true;
    		   	oldLvl=lvl;
    			if (lvl==4) // to comment to see the process 
    				html(prv+c);
    			if (lvl<4) search(prv+c);
    		}
    	}
    }						 
    search('12345');
    </script>
    </body>
    </html>
    Unless I am mistaken, there would be 120x24x56 = 161 260 solutions. This seems consistent with this OEIS page

    EDIT : This script could be modified starting from a random permutation p=prm(Math.floor(Math.random()*120)) and trying to concatenate random permutations...
    Last edited by 007Julien; 11-22-2012 at 12:08 PM. Reason: complements

  7. #7
    Join Date
    Nov 2012
    Posts
    4
    i have a mistake at my previous script and had tried another with new script from 007Julien.
    then, i had script to build array based new script from 007Julien. but, it's only work until 5x5. maybe it's too much for 6x6 or more. hope can help the others that had some problem with me.
    Code:
    <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
    <html>
    <head>
    <meta http-equiv="content-type" content="text/html; charset=utf-8">
    <meta name="generator" content="PSPad editor, www.pspad.com">
    <title>Sudoku 5x5</title>
    <style type="text/css">
    body{font-family:Courier,monospace}
    p {display:block;width:56px;float:left;margin:2px;padding:0;border:1px solid red} 
    div {diplay:block;margin:0 auto;padding:0;width:880px;}
    </style>
    </head>
    <body>
    <div id="rsp"></div>
    
    <script type="text/javascript">
    var arr2=[];
    // To see simple objects like array with alert 
    Object.prototype.toString=function(){var i,s='';for(i in this) s+=i+':'+this[i]+' ';return s}
    
    // The 120 permutations of '12345'
    function prm(n,firstNum,lastNum){
    	var i,s='',temp,t=[],p='',j;
    	for(i=firstNum;i<=lastNum;i++)
    		s+=i;
    	temp=s;
    	
    	for(i=s.length-1;i>0;i--){
    		for(x=1,j=i;j>1;j--)
    			x=x*j;
    		t.push(x);
    	}
    	
    	for (i=0;i<temp.length;i++){
    		j=Math.floor(n/t[i]);
    		n%=t[i];
    		p+=s.substr(j,1);
    		s=s.substr(0,j)+s.substr(j+1);
    	}
      return p;
    }
    // Column constructor  
    function Column(k,v){this[k]=v}
    
    // Test a new line (str) in comparaison with the preceding in form of oldCols (an array of 5 Columns)  
    function tstNewline(str,oldCols,countNum){
    	var i,t=str.split('');
    	// There is no need to test the first column (i=5;while (i) if (oldCols[--i][t[i]]) return false;)
    	i=countNum;
    	while (--i){
    		if (oldCols[i][t[i]])
    			return false;
    	}
    	return true;
    }
    // To show the string 
    function html(stj,countNum){
    	//var h='<p>';
    	var arr=[];
    	for(i=0;i<countNum;i++){
    		x = i*countNum;
    		//h+=stj.slice(x,x+countNum)+'<br>';
    		arr.push(stj.slice(x,x+countNum));
    	}
    	/*h+='</p>';
    	document.getElementById('rsp').innerHTML+=h;*/
    	return arr;
    	/*var h='<p>'+stj.replace(/(\d)(?=([\d]{5})+($|<))/g,'$1<br>')+' </p>';
    	document.getElementById('rsp').innerHTML+=h;*/
    }
    
    function search(prv,firstNum,countNum){
    	var i,l,c,oldCols=[],lng=prv.length,lvl=lng/countNum,oldLvl,resPrm,amountPrm,arr;
    	var lastNum = firstNum + (countNum-1);
    	// oldCols an array of Columns which values are true for all the integers of the previous lines
    	for (i=0;i<lng;i++){
    		// Construction of objects with the first line
    		if (i<countNum)
    			oldCols[i]=new Column(prv[i],true);
    		// Updated with the following
    		else
    			oldCols[i%countNum][prv[i]]=true;
    	}
    	
    	for(resPrm=1,j=countNum;j>1;j--)
    		resPrm *= j;
    	
    	amountPrm = resPrm/countNum;
    	
    	// To add a new line beginning with lvl
    	for (i=amountPrm*lvl,l=i+amountPrm;i<l;i++){
    		c=prm(i,firstNum,lastNum); 
    		if (tstNewline(c,oldCols,countNum)){
    			// to uncomment to see the process		
    		  	//if (lvl<oldLvl) document.getElementById('rsp').innerHTML+='<p style="clear:both">&nbsp;</p>';newLine=true;
    			//alert(i+"\n"+lvl);
    		   	oldLvl=lvl;
    			if (lvl==countNum-1){ // to comment to see the process 
    				arr = html(prv+c,countNum);
    			}
    			if (lvl<countNum-1)
    				search(prv+c,firstNum,countNum);
    		}
    	}
    	if(lvl==countNum-1)
    		arr2.push(arr);
    	if(lvl==1){
    		arr = arr2;
    		arr2 = [];
    		return arr;
    	}
    }
    
    function buildNum(firstNum,countNum){
    	var lastNum = firstNum + (countNum-1);
    	var c=[],resPrm,amountPrm,arr=[],index,conTable='',prmArray,arrArray=[],tes;
    	
    	for(resPrm=1,j=countNum;j>1;j--)
    		resPrm *= j;
    	
    	amountPrm = resPrm/countNum;
    
    	//create array 1xxxx
    	for (i=0;i<amountPrm;i++){
    		c.push(prm(i,firstNum,lastNum));
    	}
    	
    	choose = Math.floor(Math.random()*amountPrm);
    	prmArray = search(c[choose],firstNum,countNum);
    	choose2 = Math.floor(Math.random()*prmArray.length);
    
    	for(i=0;i<prmArray[choose2].length;i++){
    		arrArray[i]=[];
    		for(j=0;j<prmArray[choose2][i].length;j++){
    			arrArray[i].push(prmArray[choose2][i].slice(j,j+1));
    		}
    	}
    
    	return arrArray;
    }
    
    function arrayShuffle(oldArray) {
    	var newArray = oldArray.slice();
     	var len = newArray.length;
    	var i = len;
    	 while (i--) {
    	 	var p = parseInt(Math.random()*len);
    		var t = newArray[i];
      		newArray[i] = newArray[p];
    	  	newArray[p] = t;
     	}
    	return newArray; 
    };
    
    document.getElementById("rsp").innerHTML = arrayShuffle(buildNum(1,3));
    </script>
    </body>
    </html>
    thanks Julien, you really help me
    because i didn't use more than 5x5, so that's really help me.
    thank you so much

  8. #8
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,273
    To work with Sudokus, an other approach is useful...
    • A Sudokus quizz is define by a string containing at least 81 digits (*), (and other signs to draw the HTML game),
    • An object containing cells consisting of integers representative of the state of the grid. These integers are 10 bits or flags : the first (rank 0) is true if the case is resolved (initial data or cell already resolved). The following (ranks : 1,2,3,4,5,6,7,8,9) are true if the value of their rank is possible or certain (initial data or cell already resolved).

    So the initial constructor of this Board object set all empty cells with the integer 1022 (2^10-2 = 1024-1-1 = 1023 - 1 => 10 bits On, subtracting 1 => 9 bits On and 1 bit off (blank cell).
    Then the method to fill a cell setCell(c,v) change the value of this cell (with a (1<<v) & 1) and updates the other cells of the same line, same column and same sub-grid with a cellValue&=1023-(1<<v); (see javascript bit operators).

    See the source of this old page which contains a hidden solver to valid a new grid...


    (*) See, for example, this page and particularly the collection of 49151 distinct Sudoku configurations with 17 entries.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center



Recent Articles