algorithm - Calculating number of lines with N or greater bits set -


i'm looking ip multicasting @ moment, , determining number of unique multicast groups required address possible combinations of n hosts.

for instance, if have 3 end hosts (a, b, c), total of 4 multicast groups need created enable possible combinations of these hosts addressed (ab, ac, bc, abc), excluding instances 1 or 0 hosts being addressed.

as far can tell, number of unique groups excluding instances 1 or 0 hosts being addressed can expressed [2^n - (n + 1)], n = number of hosts.

however, i'm interested in looking @ how many groups exist when @ least percentage of systems addressed.

for instance, if had 5 systems, have total of 26 multicast groups. however, if excluded groups 3 or fewer systems being addressed (only looking @ groups 4 or systems addressed), have 6 groups. can determine hand, shown below.

is there formula can use calculate instead? so, if have n hosts , want create multicast groups include y hosts or greater, means have z multicast groups. in above example, y = 4, z determined 6.

any assistance or feedback appreciated

1 0 bits set 00 - 00000  5 1 bit set 01 - 00001 02 - 00010 04 - 00100 08 - 01000 16 - 10000  10 2 bits set 03 - 00011 05 - 00101 06 - 00110 09 - 01001 10 - 01010 12 - 01100 18 - 10010 20 - 10100 17 - 10001 24 - 11000  10 3 bits set 07 - 00111 11 - 01011 13 - 01101 14 - 01110 19 - 10011 21 - 10101 22 - 10110 25 - 11001 26 - 11010 28 - 11100  5 4 bits set 15 - 01111 23 - 10111 27 - 11011 29 - 11101 30 - 11110  1 5 bits set 31 - 11111

treating combination problem should help. see http://en.wikipedia.org/wiki/combination

out of n bits want know sum of combinations have y n bits set.

something pseudo-code:

for k y..n   total += (n choose k)

where n choose k can calculated n! / (k! * (n-k)!)

for example get:

5 choose 4 = 5 5 choose 5 = 1 --------------      total = 6

Comments

Post a Comment

Popular posts from this blog

jquery - Invalid Assignment Left-Hand Side -

i trying assign class tag via jquery, resulting in error through firebug says "invalid assignment left-hand side" on fourth line below. <cfoutput> $('.pngfix a').each(function(index) { var hreflink = $(this).attr("href"); if (hreflink.tolowercase() = '../audio.cfm') { $(this).addclass('audioimg'); } }); </cfoutput> looking around online, looks syntax problem, don't seem see it... any tips? thanks if (hreflink.tolowercase() = '../audio.cfm') that attempts assign value, rather check equality. change = operator == .
Read more

java - Play! framework 2.0: How to display multiple image? -

i need display gallery of photos. here template: @(photos: list[photo]) @title = { <bold>gallery</bold> } @main(title,"photo"){ <ul class="thumbnails"> @for(photo <- photos) { <li class="span3"> <a href="#" class="thumbnail"> <img src="@photo.path" alt=""> </a> </li> } </ul> } and here controller method: public static result getphotos() { return ok(views.html.photo.gallery.render(photo.get())); } and here photo bean : @entity public class photo extends model { @id public long id; @required public string label; public string path; public photo(string path, string label) { this.path = path; this.label = label; } private static finder<long, photo> find = new finder<long, photo>( long.class, photo.class); public static list<phot...
Read more

gmail - Is there any documentation for read-only access to the Google Contacts API? -

i want read-only access user's google contacts. there stackoverflow member wanted this, , received following answer : yes, there is, use https://www.googleapis.com/auth/contacts.readonly scope , "view contacts". this exchange reference read-only access google contacts can find using google. simply using access token obtained attempt read usual google contacts api (i.e. https://www.google.com/m8/feeds ) fails insufficient permissions. similarly, using google contacts api on new target fails 404 errors (for example https://www.googleapis.com/auth/contacts.readonly/default/full ). is there documentation anywhere on how use api, or permissible way access google contacts api full read-write access?
Read more