Pages

Thursday, July 4, 2013

The Subset Problem

There are many variations of this problem, I will stay on the general problem of finding all subsets of a set. For example if our set is [1, 2, 3] - we would have 8 (2 to the power of 3) subsets: {[], [1], [2], [3], [1, 2], [1, 3], [1, 2, 3], [2, 3]}. So basically our algorithm can't be faster than O(2^n) since we need to go through all possible combinations.

There's a few ways of doing this. I'll mention two ways here - the recursive way, that we've been taught in high schools; and using a bit string.

Using a bit string involves some bit manipulation but the final code can be found easy to understand. The idea  is that all the numbers from 0 to 2^n are represented by unique bit strings of n bit width that can be translated into a subset. So for example in the above mentioned array we would have 8 numbers from 0 to 7 inclusive that would have a bit representation that is translated using the bit index as the index of the array.

Nr Bits Combination
0 000 {}
1 001 {1}
2 010 {2}
3 011 {1, 2}
4 100 {3}
5 101 {1, 3}
6 110 {2, 3}
7 111 {1, 2, 3}


It may look easier in the code:


Note:
- The Math.pow call computes 2 to the power of n
- The findLowestBitSet is a method I mentioned earlier. In Java it could look like this:



Or it could be optimized to look like this:


For comparison find below the code for the recursive algorithm:

3 comments:

  1. THE NATIONAL ACADEMYOF TELEVISION ARTS & SCIENCESANNOUNCES PRESENTERS FORTHE 46th ANNUAL DAYTIME EMMY® AWARDS Chef
    Jacques Pepin and Judge Judy Sheindlin to be Honored with Lifetime Achievement Awards Pasadena, CA – April 29th, 2019 –The National
    Academy of Television Arts & Sciences (NATAS) today announced the presenters for both the 46th Annual Daytime Creative Arts…
    Daytime Creative Arts Emmy® Daytime Emmy Awards 2019 Live Stream The Insider / April 16,
    2019 Daytime Emmy® Awards Hosts Announced MARIO LOPEZ & SHERYL UNDERWOOD ANNOUNCED AS HOSTS FOR THE 46th ANNUAL DAYTIME EMMY® AWARDS AND DAVID OSMOND
    AS HOST FOR THE CREATIVE ARTS AWARDS WITH CAROLYN HENNESY HOSTING THE RED CARPET LIVE AND POST SHOW INTERVIEWS WITH THE WINNERS LOS ANGELES, CA –
    April 16, 2019 – Announced today on the CBS Daytime program.

    ReplyDelete
  2. The main event sells itself, it is at worst two of the top three middleweights in the sport fighting for three of the four major titles at 160 pounds. The undercard has taken some hits, but nothing huge as it was never a great undercard to begin with. https://canelovsjacobsfights.com/how-to-watch-daniel-jacobs-vs-canelo-alvarez-press-conference/David Lemieux is out, but instead Bilal Akkawy will be the opponent for John Ryder, and that fight could still bang. That's right...it's a title unification fight and we'll tell you how to get a Canelo Alvarez vs Jacobs live stream, no matter where on Earth you are. The Saul 'Canelo' Alvarez vs Daniel Jacobs fight https://canelovsjacobsfights.com/how-to-watch-danny-jacobs-vs-canelo-alvarez-live-boxing-full-fight/ will take place on Saturday, May 4 at the T-Mobile Arena in Las Vegas. The main fight is set to start at somewhere around 11.30pm ET / 8.30pm PT (so 4.30am BST and 2.30pm AET on Sunday). https://canelovsjacobsfights.com/how-to-watch-jacobs-vs-alvarez-boxing-buy-las-vegas-tickets/ Canelo returns to the middleweight division to cement his dominanceafter fighting in another division against Rocky Fielding to obtain the WBA super middleweight title.The American boxer won the vacant IBF middleweight title stripped from Gennady Golovkin after winning by split decision against Sergiy Derevyanchenko last year. The Canelo Alvarez vs. https://canelovsjacobsfights.com/jacobs-vs-alvarez-boxing-buy-las-vegas-tickets‎/Daniel Jacobs fight is availableexclusively through the DAZN app.DAZN, the exclusive home of Canelo, GGG and Anthony Joshua, launched in the United States on Sept. 10 and is offering two different subscription packages for fight fans. New subscribers would be able to live stream the Canelo vs. Jacobs fight, along with dozens of other live events and original programming included in DAZN's multi-sport offering.Horn told ESPN when asked what his dream scenario https://canelovsjacobsfights.com/daniel-jacobs-vscanelo-alvarez-fight-time-date-channel/would be.Stream over 50 sports live & anytime on your TV or favourite device with KAYO SPORTS. The biggest Aussie sports and the best from overseas. Just $25/month. No lock-in contract. Get your 14 day free trial Everyone knows he’s very strong. A very, very good boxer.“I’d probably choose him or GGG [Gennady Gennadyevich Golovkin.

    ReplyDelete
  3. They are the two biggest names right now in boxing and they are two scalps I’d really like to get under my belt. I’d fight them.”The WGA handed out awards simultaneously in Los Angeles and New York. “Arrival” won the adapted-screenplay award in New York before the category had been announced in Los Angeleswhere “Arrival” screenwriter Eric Heisserer was. That timing problem has been common in recent years with the WGA, which is split between the WGA, https://emmyawardsdaytime.com/46th-daytime-emmy-awards-winners-dove-cameron/ West and WGA, East, each with its own ceremony.The win for “Moonlight” was particularly impressive, because Barry Jenkins and Tarell Alvin McCraney’s film was classified as an original screenplay by the WGA, putting it in a head-to-head competition with “La La Land” and “Manchester by the Sea.”Maisel), the Daytime Emmy Awards honor the people and programs that run between 2 a.m. and 6 p.m. https://emmyawardsdaytime.com/will-the-2019-daytime-emmy-awards-be-televised/The 2019 Daytime Emmy nominees include household names such as Ellen DeGeneres, Whoopi Goldberg, Kelly Ripa, Ryan Seacrest, and O's very own Gayle King. And while watching the show sounds like it'd be easy, things get somewhat tricky. The National Academy of Television Arts and Sciences (NATAS) also sub-divides the daytime ceremonies into regular and Creative Arts Awards. Confused yet? Don’t worry, we’ve got you covered. Here’s everything you need to know about the 46th annual Daytime Emmy Awards.

    ReplyDelete