www.webdeveloper.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Subset question (math)

Hybrid View

  1. #1
    Join Date
    Dec 2013
    Posts
    6

    Smile Subset question (math)

    OK, to be brutally honest I dont know squat about programming but I do need some help from someone who does.

    I need a list generated (or a use-able script) of all possible subset combinations for the set 1,2,3,4,5,6,7,8,9,10,12. Select six. Numbers cannot repeat.

    Example subset: 1,2,3,4,5,6 (six selected, no repeats).

    Example of what I dont need: 1,1,2,2,3,3,4,4,5,5,12,12 or 1,1,1,1,1,6.

    I will also need the opposites removed, meaning...if I have 1,3,5,7,9,11 then I need 2,4,6,8,10,12 eliminated from the final list.

    This is for a game, where you must select all numbers right or no numbers right. In case anyone is wondering.

    Thanks in advance.

  2. #2
    Join Date
    Dec 2005
    Location
    FL
    Posts
    7,443

    Lightbulb

    Here's a start...
    Code:
    <!DOCTYPE html>
    <html lang="en">
    <head>
    <meta charset="UTF-8" />
    
    <title> Untitled </title>
    
    </head>
    <body>
    <div id="debug"></div>
    
    <script type="text/javascript">
    function makeArray(N) { 
      var arr = [];  for (var i=0; i<N; i++) { arr.push(i+1); }  return arr;
    }
    function randOrd(){ return (Math.round(Math.random())-0.5); } 
    var origArr = makeArray(12); 
    document.getElementById('debug').innerHTML = 'Original: '+origArr;
    var rndArr = origArr.sort(randOrd);
    document.getElementById('debug').innerHTML += '<p>Randomized: '+rndArr;
    var have = rndArr.splice(0,6);
    var havenot = rndArr.splice(0);
    document.getElementById('debug').innerHTML += '<p>have: '+have+'<p>havenot: '+havenot;
    
    </script>
    
    </body>
    </html>

  3. #3
    Join Date
    Dec 2013
    Posts
    6

    Smile

    Quote Originally Posted by JMRKER View Post
    Here's a start...
    Code:
    <!DOCTYPE html>
    <html lang="en">
    <head>
    <meta charset="UTF-8" />
    
    <title> Untitled </title>
    
    </head>
    <body>
    <div id="debug"></div>
    
    <script type="text/javascript">
    function makeArray(N) { 
      var arr = [];  for (var i=0; i<N; i++) { arr.push(i+1); }  return arr;
    }
    function randOrd(){ return (Math.round(Math.random())-0.5); } 
    var origArr = makeArray(12); 
    document.getElementById('debug').innerHTML = 'Original: '+origArr;
    var rndArr = origArr.sort(randOrd);
    document.getElementById('debug').innerHTML += '<p>Randomized: '+rndArr;
    var have = rndArr.splice(0,6);
    var havenot = rndArr.splice(0);
    document.getElementById('debug').innerHTML += '<p>have: '+have+'<p>havenot: '+havenot;
    
    </script>
    
    </body>
    </html>
    Thats pretty good but I still dont know how I can get a complete list generated. and It would be ideal if the numbers werent randomized as far as order. 1,2,3,4,5,6 - 1,2,3,4,5,7 - 1,2,3,4,5,8 ...is what I need, similar to the odometer on your car.

  4. #4
    Join Date
    Dec 2011
    Location
    Centurion, South Africa
    Posts
    795
    OK, my turn

    index.html
    Code:
    <!DOCTYPE html>
    <html lang="en">
    	<head>
    		<meta charset="utf-8" />
    		<title>Subset question (math)</title>
    	</head>
    	<body>
    		<!-- http://www.webdeveloper.com/forum/showthread.php?288073-Subset-question-(math) -->
    		<script type="text/javascript">
    
    			var
    				subset = [1, 2, 3, 4, 5, 5], notset,
    				i, j, n, u, c = 1;
    
    			while (c) {
    				for (i = subset.length - 1, j = 1; j && (i > -1); --i) {
    					n = subset[i] + 1;
    					if (n > 12) {n = 1; j = 1; if (!i) {c = 0;}} else {j = 0;}
    					subset[i] = n;
    				}
    				for (i = 0, u = 1; i < subset.length; ++i) {for (j = 0; j < subset.length; ++j) {if (i !== j) {
    					if (subset[i] === subset[j]) {
    						u = 0;
    					}
    				}}}
    				if (u) {
    					for (i = 1, notset = []; i <= 12; ++i) {
    						for (j = 0; j < subset.length; ++j) {if (i === subset[j]) {break;}}
    						if (j >= subset.length) {notset.push(i);}
    					}
    					document.write(subset.join(', '), ' || ', notset.join(', '), '<br />');
    				}
    			}
    
    		</script>
    	</body>
    </html>
    Output

    1, 2, 3, 4, 5, 6 || 7, 8, 9, 10, 11, 12
    1, 2, 3, 4, 5, 7 || 6, 8, 9, 10, 11, 12
    1, 2, 3, 4, 5, 8 || 6, 7, 9, 10, 11, 12
    1, 2, 3, 4, 5, 9 || 6, 7, 8, 10, 11, 12
    1, 2, 3, 4, 5, 10 || 6, 7, 8, 9, 11, 12
    1, 2, 3, 4, 5, 11 || 6, 7, 8, 9, 10, 12
    1, 2, 3, 4, 5, 12 || 6, 7, 8, 9, 10, 11
    ...
    12, 11, 10, 9, 8, 1 || 2, 3, 4, 5, 6, 7
    12, 11, 10, 9, 8, 2 || 1, 3, 4, 5, 6, 7
    12, 11, 10, 9, 8, 3 || 1, 2, 4, 5, 6, 7
    12, 11, 10, 9, 8, 4 || 1, 2, 3, 5, 6, 7
    12, 11, 10, 9, 8, 5 || 1, 2, 3, 4, 6, 7
    12, 11, 10, 9, 8, 6 || 1, 2, 3, 4, 5, 7
    12, 11, 10, 9, 8, 7 || 1, 2, 3, 4, 5, 6


    It takes a while to generate the entire list, it's quite long so be patient

  5. #5
    Join Date
    Dec 2013
    Posts
    6
    Quote Originally Posted by bionoid View Post
    OK, my turn

    index.html
    Code:
    <!DOCTYPE html>
    <html lang="en">
    	<head>
    		<meta charset="utf-8" />
    		<title>Subset question (math)</title>
    	</head>
    	<body>
    		<!-- http://www.webdeveloper.com/forum/showthread.php?288073-Subset-question-(math) -->
    		<script type="text/javascript">
    
    			var
    				subset = [1, 2, 3, 4, 5, 5], notset,
    				i, j, n, u, c = 1;
    
    			while (c) {
    				for (i = subset.length - 1, j = 1; j && (i > -1); --i) {
    					n = subset[i] + 1;
    					if (n > 12) {n = 1; j = 1; if (!i) {c = 0;}} else {j = 0;}
    					subset[i] = n;
    				}
    				for (i = 0, u = 1; i < subset.length; ++i) {for (j = 0; j < subset.length; ++j) {if (i !== j) {
    					if (subset[i] === subset[j]) {
    						u = 0;
    					}
    				}}}
    				if (u) {
    					for (i = 1, notset = []; i <= 12; ++i) {
    						for (j = 0; j < subset.length; ++j) {if (i === subset[j]) {break;}}
    						if (j >= subset.length) {notset.push(i);}
    					}
    					document.write(subset.join(', '), ' || ', notset.join(', '), '<br />');
    				}
    			}
    
    		</script>
    	</body>
    </html>
    Output

    1, 2, 3, 4, 5, 6 || 7, 8, 9, 10, 11, 12
    1, 2, 3, 4, 5, 7 || 6, 8, 9, 10, 11, 12
    1, 2, 3, 4, 5, 8 || 6, 7, 9, 10, 11, 12
    1, 2, 3, 4, 5, 9 || 6, 7, 8, 10, 11, 12
    1, 2, 3, 4, 5, 10 || 6, 7, 8, 9, 11, 12
    1, 2, 3, 4, 5, 11 || 6, 7, 8, 9, 10, 12
    1, 2, 3, 4, 5, 12 || 6, 7, 8, 9, 10, 11
    ...
    12, 11, 10, 9, 8, 1 || 2, 3, 4, 5, 6, 7
    12, 11, 10, 9, 8, 2 || 1, 3, 4, 5, 6, 7
    12, 11, 10, 9, 8, 3 || 1, 2, 4, 5, 6, 7
    12, 11, 10, 9, 8, 4 || 1, 2, 3, 5, 6, 7
    12, 11, 10, 9, 8, 5 || 1, 2, 3, 4, 6, 7
    12, 11, 10, 9, 8, 6 || 1, 2, 3, 4, 5, 7
    12, 11, 10, 9, 8, 7 || 1, 2, 3, 4, 5, 6


    It takes a while to generate the entire list, it's quite long so be patient
    Wow I'm pretty impressed! Keep it coming

  6. #6
    Join Date
    Dec 2011
    Location
    Centurion, South Africa
    Posts
    795
    Quote Originally Posted by pinned38 View Post
    Wow I'm pretty impressed! Keep it coming
    uh, you are going to generate the list on your computer right? I wouldn't be able to upload it here anyway.
    I did a count and there are 665280 possible combinations.

  7. #7
    Join Date
    Mar 2011
    Posts
    61
    Do you need all combinations ( 123 is the same as 132, 213, 231, 312 and 321), or all variations (123 is different from 132 ...)?
    Bioniods code gives all variations. The code underneath all combinations.
    Code:
    function combinations(numArr, choose, callback) {
      var n = numArr.length,
          c = [],
          inner = function(start, choose_) {
            if (choose_ == 0) {
              callback(c);
            } else {
              for (var i = start; i <= n - choose_; ++i) {
                c.push(numArr[i]);
                inner(i + 1, choose_ - 1);
                c.pop();
              }
            }
          };
      inner(0, choose);
    }
    
    var set = [1,2,3,4,5,6,7,8,9,10,11,12],
        choices = 6,
        combinationsArray = [],
        callback = function(c){
          combinationsArray.push(c.slice(0));
        };
    
    combinations(set, choices, callback);
    
    document.write(combinationsArray.join('<br>'));
    document.write('<hr>');
    combinationsArray.length = combinationsArray / 2; // cut of the last half, which are opposites of the first half.
    document.write(combinationsArray.join('<br>'));

  8. #8
    Join Date
    Dec 2005
    Location
    FL
    Posts
    7,443
    What kind of game is this that requires so many combinations or variations?

  9. #9
    Join Date
    Dec 2013
    Posts
    6
    Quote Originally Posted by JMRKER View Post
    What kind of game is this that requires so many combinations or variations?
    Its for a drawing.

    Also, I dont need varying order such as 123, 321, 312. Just 123 will do since order doesnt matter because if the game draws 6,3,4,2,1,5 the player will still win by drawing 1,2,3,4,5,6. He just has to pick the numbers, order doesnt matter therefore I need all possible combinations and not all possible variations. I do apologize about my poor math language, just like programming - its not my specialty! But thanks for your patience and if I'm not clear then feel free in asking me to clarify.

  10. #10
    Join Date
    Dec 2013
    Posts
    6
    Also, towards the bottom of the list I noticed the numbers start to mirror the top of the list, so somehow half of the subsets need to be removed. This is an "all or nothing" game, so the player only needs to choose all of the numbers correct or none of the numbers correct to win.

  11. #11
    Join Date
    Dec 2013
    Posts
    6
    I hadnt checked out that list before now and It looks great, if you are able to remove the variations and just do combinations I thing I'll be set.

  12. #12
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,276
    Like said Bionoid thanks in binary !

    Then each integer containing 6 bits of ranks less or equal to 11 (from 0 to 11) describes a subset of six integers of the set 1, 2, 3, ... 11, 12.

    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></title>
    <style type="text/css">
    
    </style>
    </head>
    <body>
    <div id="rsp"></div>
    <script type="text/javascript">
    var i,j,k,n=0,bts,prm='',pow=[1,2,4,8,16,32,64,128,256,512,1024,2048];
    
    for (i=63;i<=8064;i++) {j=i;
    	bts=1;while (j&=j-1) bts++;
    	if (bts==6) {prm+='<br>n '+(++n)+' '+i+'=>( ';
    	  for (k=0;k<12;k++) if (i&pow[k]) prm+=(k+1)+' '
    	  prm+=')';
    	}
    }
    document.getElementById('rsp').innerHTML=prm;
    </script>
    </body>
    </html>
    63 is 111111 and 8064 is 111111000000
    CQFD
    Last edited by 007Julien; 12-24-2013 at 12:35 PM.

  13. #13
    Join Date
    Dec 2011
    Location
    Centurion, South Africa
    Posts
    795
    Quote Originally Posted by pinned38 View Post
    , similar to the odometer on your car.
    Well my mindset was stuck on the variation style, as an odometer doesn't reorder its numbers :P
    I believe what Kever submitted is what you're actually looking for
    Actually, 007Julien's code is pretty cool as well :P

  14. #14
    Join Date
    Oct 2010
    Location
    Versailles, France
    Posts
    1,276
    Yes but I make a mistake. You have to stop with 4032 which is 111111000000

    It's probably useful to work with this integers to store in an array of length 924...
    Last edited by 007Julien; 12-24-2013 at 04:48 PM.

  15. #15
    Join Date
    Mar 2011
    Posts
    61
    I messed up as well. The bottom half of the list are indeed opposites of the the top half. The easiest way to get rid of them, is to cut the array in half. This can be done by setting it's length to half of it's original length.
    Code:
    combinationsArray.length = combinationsArray / 2;
    
    should be
    
    combinationsArray.length = combinationsArray.length / 2;

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