Algorithms – Faster Algorithm for Finding All Subsets

algorithms

This is the algorithm (pseudocode) I have right now for finding all subsets for a given set with length k:

void allSubsets(set[]) {
    for (i = 0; i<k; i++) {
        for (j = i + 1; j<k; j++) {
            print(set[i...j]);
        }
    }
}

But it's run-time is O(n^2). Can anybody improve this?

Best Answer

From what I understand this doesn't work. You wouldn't find "AC" in the set "ABCD" (i.e. holes). To find all subsets think that each element is either inside the subset or not. Which is basically a binary yes, no. Therefore you can cycle over all numbers with k 0/1 bits to find all combinations.

Related Solutions

An algorithm for finding converse duplicates of ordered pairs

Just collect the pairs in a set. (In Ruby, it will be a Set of two-element Arrays.)

let Set s = {}
for each pair [a,b]
   if s contains [a,b]
      // duplicate, do nothing
   else if s contains [b,a] // converse duplicate
      ...
   else
      add [a,b] to S

If you are writing Ruby, it is already capable of using arrays

Algorithms – How to Find Common Subsets in a List of Sets

I answered a similar question at https://stackoverflow.com/questions/26028124/the-intersection-of-all-combinations-of-n-sets/26028865#26028865 and the only difference in what you need is that the second map should map an element to the set of sets it is in, rather than every subset of that set.

Best Answer

Related Solutions

An algorithm for finding converse duplicates of ordered pairs

Algorithms – How to Find Common Subsets in a List of Sets

Related Topic