-
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.
-
June 4th, 2012, 07:25 PM
#2
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.
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
|