Efficient Enumeration on m-combinations of the powerset of a set
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

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

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

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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center