CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

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

1. Junior Member
Join Date
May 2012
Posts
1

## 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.

2. Elite Member
Join Date
May 2009
Posts
2,413

## 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•