StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To output the Power Set,there are three ways in "14.5 Generating Subsets", The Alogrithm Design Manual,and I have tried all of them with only array,loop and functions. But there will be no code.Here are short paragraphs about them:</p> <blockquote> <p>1.<strong>Lexicographic order</strong> – Lexicographic order means sorted order, and is often the most natural way to generate combinatorial objects. The eight subsets of {1, 2, 3} in lexicographic order are {} , {1}, {1, 2}, {1, 2, 3}, {1, 3}, {2}, {2, 3}, and {3}. But it is surprisingly difficult to generate subsets in lexicographic order. <strong>Unless you have a compelling reason to do so, don’t bother.</strong></p> <p>2.<strong>Gray Code</strong> – A particularly interesting and useful subset sequence is the minimum change order, wherein adjacent subsets differ by the insertion or deletion of exactly one element. Such an ordering, called a Gray code. Generating subsets in Gray code order can be very fast, because there is a nice recursive construction. Construct a Gray code of n − 1 elements G<SUB>n−1</SUB> Reverse a > second copy of G<SUB>n−1</SUB> and add n to each subset in this copy. Then concatenate them together to create G<SUB>n</SUB> . <strong>Further, since only one element changes between subsets, exhaustive search algorithms built on Gray codes can be quite efficient.</strong></p> <p>3.<strong>Binary counting</strong>– <strong>The simplest approach</strong> to subset-generation problems is based on the observation that any subset S' is defined by the items of that S are in S'. We can represent S' by a binary string ofn bits, where bit i is 1iffthe ith element of S is in S'. This defines a bijection between the 2<SUP>n</SUP> binary strings of length n,and the 2<SUP>n</SUP> subsets of n items. For n = 3, binary counting generates subsets in the following order: {} , {3}, {2}, {2,3}, {1}, {1,3}, {1,2}, {1,2,3}. This binary representation is the key to solving all subset generation problems. To generate all subsets in order, simply count from 0 to 2<SUP>n-1</SUP>. For each integer, successively mask off each of the bits and compose a subset of exactly the items corresponding to 1 bits. To generate the next or previous subset, increment or decrement the integer by one.Unranking a subset is ex-actly the masking procedure, while ranking constructs a binary number with 1’s corresponding to items in S and then converts this binary number to an integer.</p> </blockquote> <p>if you want an easy one, just Binary Counting is enough, it can be recurrence implement such as backtracking or a specific one.If you have done it and want more challenge,you can code a Gray Code one. You can learn how to generate Gray Code on its wiki page <a href="http://en.wikipedia.org/wiki/Gray_code#Genetic_algorithms">here</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload