# Efficient Enumeration on m-combinations of the powerset of a set

• May 30th, 2012, 02:56 AM
liaomingxue
Efficient Enumeration on m-combinations of the powerset of a set
Input:
s: A set of n elements, for example {1,2,3}
t: The power set of s, for example {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Output:
all sets: {u}, each u is an m-combination of t, and each element of u can not be a proper subset of another element, for example:
{{},{},{}}
{{1},{1},{1}}
{{1},{1},{2}}
{{1},{1},{3}}
{{1},{1},{23}}
{{1},{2},{2}}
{{1},{2},{3}}
{{1},{3},{3}}
{{1},{23},{23}}
{{2},{2},{2}}
{{2},{2},{3}}
{{2},{2},{13}}
{{2},{3},{3}}
{{2},{13},{13}}
{{2},{13},{23}}
{{3},{3},{3}}
{{3},{3},{12}}
{{3},{12},{12}}
{{12},{12},{12}}
{{12},{12},{13}}
{{12},{12},{23}}
{{12},{13},{13}}
{{12},{13},{23}}
{{12},{23},{23}}
{{13},{13},{13}}
{{13},{13},{23}}
{{23},{23},{23}}
{{123},{123},{123}}

The problem:
1 We do not know how many sets will be produced.
2 We hope for an efficient algorithm that produce all sets in a minimum steps.
• June 4th, 2012, 07:25 PM
nuzzle
Re: Efficient Enumeration on m-combinations of the powerset of a set
Have you tried an "inefficient" enumeration first?

It's always good to have an initial working solution even if it won't win you the Nobel price.