# Subset question (math)

Printable View

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• 12-22-2013, 10:43 PM
pinned38
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.
• 12-23-2013, 10:46 AM
JMRKER
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>```
• 12-23-2013, 03:02 PM
pinned38
Quote:

Originally Posted by JMRKER
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.
• 12-23-2013, 04:08 PM
bionoid
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 ;)
• 12-23-2013, 04:18 PM
pinned38
Quote:

Originally Posted by bionoid
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
• 12-23-2013, 04:28 PM
bionoid
Quote:

Originally Posted by pinned38
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.
• 12-23-2013, 04:29 PM
Kever
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>'));```
• 12-23-2013, 06:03 PM
JMRKER
What kind of game is this that requires so many combinations or variations?
• 12-24-2013, 10:12 AM
pinned38
Quote:

Originally Posted by JMRKER
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.
• 12-24-2013, 10:41 AM
pinned38
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-24-2013, 10:51 AM
pinned38
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.
• 12-24-2013, 12:26 PM
007Julien
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
• 12-24-2013, 01:09 PM
bionoid
Quote:

Originally Posted by pinned38
, 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
• 12-24-2013, 04:44 PM
007Julien
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...
• 12-24-2013, 05:03 PM
Kever
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;```
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last

## X vBulletin 4.2.2 Debug Information

• Page Generation 0.08959 seconds
• Memory Usage 2,425KB
• Queries Executed 11 (?)
More Information
Template Usage (24):
• (1)ad_footer_end
• (1)ad_footer_start
• (1)ad_global_above_footer
• (1)ad_global_below_navbar
• (1)ad_global_header1
• (1)ad_global_header2
• (1)ad_navbar_below
• (7)bbcode_code_printable
• (5)bbcode_quote_printable
• (1)footer
• (1)gobutton
• (1)header
• (1)headinclude
• (1)headinclude_bottom
• (1)navbar_moderation
• (1)navbar_noticebit
• (2)option
• (1)pagenav
• (1)pagenav_curpage
• (1)pagenav_pagelink
• (1)printthread
• (15)printthreadbit
• (1)spacer_close
• (1)spacer_open

Phrase Groups Available (3):
• global
• postbit
• showthread
Included Files (19):
• ./printthread.php
• ./global.php
• ./includes/class_bootstrap.php
• ./includes/init.php
• ./includes/class_core.php
• ./includes/config.php
• ./includes/functions.php
• ./includes/functions_navigation.php
• ./includes/class_friendly_url.php
• ./includes/class_hook.php
• ./includes/class_bootstrap_framework.php
• ./vb/vb.php
• ./vb/phrase.php
• ./includes/functions_facebook.php
• ./includes/functions_calendar.php
• ./includes/class_bbcode_alt.php
• ./includes/class_bbcode.php
• ./includes/functions_bigthree.php
• ./includes/functions_notice.php

Hooks Called (43):
• init_startup
• init_startup_session_setup_start
• database_pre_fetch_array
• database_post_fetch_array
• init_startup_session_setup_complete
• global_bootstrap_init_start
• global_bootstrap_init_complete
• cache_permissions
• fetch_threadinfo_query
• fetch_threadinfo
• fetch_foruminfo
• load_show_variables
• load_forum_show_variables
• global_state_check
• global_bootstrap_complete
• global_start
• style_fetch
• global_setup_complete
• printthread_start
• friendlyurl_resolve_class
• friendlyurl_clean_fragment
• friendlyurl_geturl
• pagenav_page
• cache_templates
• cache_templates_process
• template_register_var
• template_render_output
• fetch_template_start
• fetch_template_complete
• parse_templates
• fetch_musername
• notices_check_start
• notices_noticebit
• process_templates_complete
• pagenav_complete
• bbcode_fetch_tags
• bbcode_create
• bbcode_parse_start
• bbcode_parse_complete_precache
• bbcode_parse_complete
• printthread_post
• printthread_complete
• page_templates