algorithm - All Possible Combinations from non uniform table, with only one value from each column -


background

in grade 11 in school, required take 4 subjects , english list of predefined subjects. today, given grid helps make our combo, such can take 1 subject each column.

the grid

|    economics     |   maths  | psychology/politcal science |                     english                      |     geography    | | hindi/psychology |  history |          sociology          |                       art                        | elective english | |      maths       |  account |          commerce           |                    economics                     |      english     | |     english      |  physics |          chemistry          | biology/computer applications/mecahnical drawing |       maths      |

the problem

i'm trying write program list out possible legal combinations table. rules are:

  • english must present
  • there must total of 5 subjects (english + 4)
  • no 2 subjects can same column
  • no subjects in final 5 may duplicate (note elective english , english separate subjects)

now pretty task if normal 4 5 matrix. however, [row 1, column 3], [row 2, column 1] , [row 4, column 4] contain more 1 subject, out of can still pick one. combination of cells can subdivided more combinations.

i'm having trouble coming algorithm this. i'm not asking free code, instead algorithm. i'm comfortable major languages (java, javascript, php etc), , pseudo codes , flowcharts work too.

this solution can, in theory, work infinite number of columns , infinite , varying number of rows within columns.

  1. split multi-subject rows separate rows while filling columns.
  2. put columns in array , order english-containing columns being first.
  3. iterate following while still have english in columns (we'll remove one-by-one):
    1. always take first column. contains english.
    2. choose english first element of combinations in iteration.
    3. construct combinations other columns recursively, taking care eliminate duplicates. doable, if pass around current combination.
    4. remove english column , sort columns again (based on whether have english or not).

this should combinations start english , eliminate duplicates.

edit: implemented solution above , seems work. check here - https://github.com/zupper/so-answers/tree/master/raghavcombos


Comments

Post a Comment

Popular posts from this blog

monitor web browser programmatically in Android? -

i've got tricky question here. need users make payment bank (namely barclaycard) in uk. so, have https url , add parameters (such amount pay, order reference, etc) url, start http connection intent.actionview, redirect user browser can enter credit card details on bank's webpage , make payment our account successfully. far ? the code use below (i changed values privacy reasons) problem is, need app when user has completed/failed/cancelled payment. barclaycardautomatically redirects particular url when payment has succeeded, 1 if failed. there no way of knowing when barclaycard payment has succeeded go android app somehow ? button cardbutton = (button) findviewbyid(r.id.card_button); cardbutton.setonclicklistener(new view.onclicklistener() { @override public void onclick(view arg0) { string prehashstring = new string(); string prohashstring = new string(); string shapassphrase = new string(); shapassphrase = "gsvth£h70zkh...
Read more

Shrink a YouTube video to responsive width -

i have youtube video embedded on our website , when shrink screen tablet or phone sizes stops shrinking @ around 560px in width. standard youtube videos or there can add code make go smaller? you can make youtube videos responsive css. wrap iframe in div class of "videowrapper" , apply following styles: .videowrapper { float: none; clear: both; width: 100%; position: relative; padding-bottom: 56.25%; padding-top: 25px; height: 0; } .videowrapper iframe { position: absolute; top: 0; left: 0; width: 100%; height: 100%; } the .videowrapper div should inside responsive element. padding on .videowrapper necessary keep video collapsing. may have tweak numbers depending upon layout.
Read more

wpf - PdfWriter.GetInstance throws System.NullReferenceException -

i'm trying create pdf document using itextsharp 5.3.4 using following document document = new document(); filestream stm = new filestream(filename, filemode.create); pdfwriter writer = pdfwriter.getinstance(document, stm); i'm getting system.nullreferenceexception following stack trace: system.nullreferenceexception occurred hresult=-2147467261 message=la référence d'objet n'est pas définie à une instance d'un objet. source=itextsharp stacktrace: à itextsharp.text.version.getinstance() innerexception: i've verified neither document nor stm null, , if select "continue" in vs12 document created - exception thrown. updated itextsharp 5.4.0 , it's still occurring. can't find information on anywhere - got ideas? make sure not catching exceptions. nullreferenceexception can 1 caught , handled inside itextsharp, don't care it. fact can continue supports theory. change following setting verify: debug -> exceptions ...
Read more