English
资源说明：Efficiently Enumerating the Subsets of a Set
The solution was found by using `dot` to draw a directed graph of all possible
one-bit transitions from the starting state 0000 and backtracking from impossible
situations until a solution was found. The optimal path is highlighted in
red. It is not known whether this solution is
unique or whether any solutions exist for *n* > 4. An automated method for
constructing `dot` or `neato` source code should be developed.
Update 20140115.1225:
---------------------
Added Eric Burnett as co-author on the paper. I have to finish my thesis before
I can finish this paper.
Update 20140604.1658:
---------------------
`minimised_snowflake_order_4.dot` can be compiled to
[PDF](https://github.com/jloughry/subset/blob/master/minimised_snowflake_order_4.pdf?raw=true)
with the command line:
````
$ neato -Goverlap=scale -T pdf minimised_snowflake_order_4.dot -o minimised_snowflake_order_4.pdf
````
It is not known whether the path shown for order-4 is unique, but it is optimal. "Optimal"
in this context means that all state transitions involve setting or resetting a single bit
("flipping a bit") and all *n*-bit states are enumerated before any (*n*+2)-bit states
are enumerated. "Strictly optimal" would have all *n*-bit states enumerated before any
(*n*+1)-bit states are enumerated, but that can't be done by flipping a bit for *n* > 1.
Efficiently Enumerating the Subsets of a Set ============================================ The [paper](https://github.com/jloughry/subset/blob/master/loughry2000.pdf) is PDF only until I find the LaTeX source code. This is the [letter](https://github.com/jloughry/subset/blob/master/letter_to_prof_knuth.pdf) I gave to Don Knuth in Oxford. Update 20121203.2048: --------------------- I found the solution to the Grey-code like banker's sequence for *n* = 4. In decimal it is 0, 1, 3, 2, 6, 4, 12, 8, 10, 11, 9, 13, 5, 7, 15, 14. In binary, the sequence is 0000, 0001, 0011, 0010, 0110, 0100, 1100, 1000, 1010, 1011, 1001, 1101, 0101, 0111, 1111, 1110.
| Binary | Dec (Hex) | Bits Set | Index |
|---|---|---|---|
| 0000 | 0 (0) | 0 | |
| 0001 | 1 (1) | * | 1 |
| 0011 | 3 (3) | ** | 2 |
| 0010 | 2 (2) | * | 3 |
| 0110 | 6 (6) | ** | 4 |
| 0100 | 4 (4) | * | 5 |
| 1100 | 12 (C) | ** | 6 |
| 1000 | 8 (8) | * | 7 |
| 1010 | 10 (A) | ** | 8 |
| 1011 | 11 (B) | *** | 9 |
| 1001 | 9 (9) | ** | A |
| 1101 | 13 (D) | *** | B |
| 0101 | 5 (5) | ** | C |
| 0111 | 7 (7) | *** | D |
| 1111 | 15 (F) | **** | E |
| 1110 | 14 (E) | *** | F |
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
