How to find all possible n-elements subsets of a set?

Question

For a set of k-elements, I need to find all possible n-element subsets (n < k).

How should I approach this problem?

Just a suggestion will be helpful Thanks!

Answer 1

I saw this in topcoder's algorithm tutorials.Take some time and understand how it works.

Iterate through all k-element subsets of {0, 1, … N-1}

   int s = (1 << k) - 1;
   while (!(s & 1 << N))
   {
     // do stuff with s
     int lo = s & ~(s - 1);       // lowest one bit
     int lz = (s + lo) & ~s;      // lowest zero bit above lo
     s |= lz;                     // add lz to the set
     s &= ~(lz - 1);              // reset bits below lz
     s |= (lz / lo / 2) - 1;      // put back right number of bits at end
   }

Answer 2

When I needed to get all combinations (or subsets) of an ArrayList of Strings in Java, I used this method.

public static List<List<String>> powerset(ArrayList<String> list) {
        List<List<String>> ps = new ArrayList<List<String>>();
        ps.add(new ArrayList<String>());

        // for every item in the original list
        for (String item : list) {
            List<List<String>> newPs = new ArrayList<List<String>>();

            for (List<String> subset : ps) {
                // copy all of the current powerset's subsets
                newPs.add(subset);

                // plus the subsets appended with the current item
                List<String> newSubset = new ArrayList<String>(subset);
                newSubset.add(item);
                newPs.add(newSubset);
            }

            // powerset is now powerset of list.subList(0, list.indexOf(item)+1)
            ps = newPs;
        }
        return ps;
}

It's an expensive operation and probably not the perfect solution for your situation. But if I were trying to come up with a solution quickly, I would do something along these lines. You can check to see if the newSubset was less than n, the size of the subsets you want, and only add item to it if it is less than n. This would stop you from generating subset greater than n. At the end, you could iterate through ps and remove any arraylist that is less than n. Again, this solution is in no way perfect....but it should do the trick

Answer 3

Sentence: Set A is set of whole numbers less than 10.

Written As:

A={0,1,2,3,4,5,6,7,8,9}

it is called listing or roster method