Algorithm for counting n-element subsets of m-element set divisible by k -


suppose {1, 2, 3, ..., m} set. choose n distinct elements set. can write algorithm counts number of such subsets sum divisible k (ordering not mattering)?

this problem have been easier if ordering mattered, doesn't , don't have clue how approach. can please help?

this can done in time o(n·k·m) , space o(n·k) method similar outlined below. let s set m elements. definition of set , subset, elements of s distinct, elements of s-subset.

first, consider simpler problem count s-subsets number of elements instead of n elements. let n(w,r) number of w-subsets u such Σu (the sum of elements of u) equal r mod k. if w subset of s, let w' w + z, z ∈ s\w; is, z element of s not in w. n(w', (r+z)%k) = n(w, (r+z)%k) + n(w, r) because n(w, (r+z)%k) number of w'-subsets u Σu≡(r+z)%k) don't contain z , n(w, r) number of w'-subsets u Σu≡(r+z)%k) contain z. repeat construction, treating each element of s in turn until w' = s, @ point desired answer n(s,0). time o(k·m), space o(k).

to adapt above process exact subset sizes, change n(w,r) n(w,h,r), h subset size, , adapt equations n(w',r) n(w',h,r) in obvious way. time o(k·n·m), space o(k·n).


Comments

Post a Comment

Popular posts from this blog

curl - PHP fsockopen help required -

i trying work on cloudflare api , have found in documentation. unfortunately have no idea how can use in fsockopen or through curl. here example of post request. need know how can make request below data post using curl or fsockopen curl https://www.cloudflare.com/api_json.html -d 'a=cache_lvl' \ -d 'tkn=8afbe6dea02407989af4dd4c97bb6e25' \ -d 'email=sample@example.com' \ -d 'z=example.com' \ -d 'v=agg' here link cloudflare https://www.cloudflare.com/docs/client-api.html#s4.2 try one: $ch = curl_init("https://www.cloudflare.com/api_json.html"); curl_setopt($ch, curlopt_returntransfer,1); curl_setopt($ch, curlopt_followlocation, 1); curl_setopt($ch, curlopt_ssl_verifypeer,false); // handling of -d curl parameter here. $param = array( 'a' => 'cache_lvl', 'tkn' => '8afbe6dea02407989af4dd4c97bb6e25', 'email' => 'sample@example.com', 'z' =...
Read more

HTTP/1.0 407 Proxy Authentication Required PHP -

i working in restricted network/limited access internet. since have use proxy make web service call. here php code calling web service , response . $client = new soapclient("http: //www.xyz.com/abc/wsdls/login.wsdl", array("trace" => 1, "exceptions" => 1, 'proxy_host' => $proxy_host, 'proxy_port' => $proxy_port, 'proxy_login' => $proxy_login, 'proxy_password' => $proxy_password)); response is fatal error: uncaught soapfault exception: [wsdl] soap-error: parsing wsdl: couldn't load ' http://www.xyz.com/abc/wsdls/login.wsdl ' : failed load external entity if copy url error message , paste in browser(with same proxy settings) works. 2nd scenario is, if pass values instead of variables giving me diffarant response $client = new soapclient("http: //www.xyz.com/abc/wsdls/login.wsdl", array("trace" => 1, "exceptions" => 1, 'proxy_host' ...
Read more

java - More than one row with the given identifier was found: 1, for class: com.model.Diagnosis -

below model, service implementation , error trace of code. model class: @entity @table(name = "ph_diagnosis_history") @jsonidentityinfo(generator = objectidgenerators.propertygenerator.class, property = "id",scope=diagnosis.class) public class diagnosis extends abstractentity { @column(name = "diagnosis_notes", length=255) @length(max = 255, message = iprprop.max_len_255_msg) private string diagnosisnote; @enumerated(enumtype.string) private diagnosistypeenum type; @temporal(temporaltype.date) @column(name = "diagnosis_date") @jsonserialize(using = jsondateserializer.class) private date diagnosisdate; @manytoone @joincolumn(name = "patient_chart_id") private patientchart patientchart; public string getdiagnosisnote() { return diagnosisnote; } public void setdiagnosisnote(string diagnosisnote) { this.diagnosisnote = diagnosisnote; } public d...
Read more