-
May 30th, 2012, 02:56 AM
#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.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|