A Gray path on binary partitions

Details A Gray path on binary partitions A Gray path on binary partitions

2009-07-22

arxiv.org/abs/0907.3873v1

Mathematics

Combinatorics

This was released as a draft preprint sometime between April and July 2003, but the authors never revised it into a final vers

Scientific paper

A binary partition of a positive integer $n$ is a partition of $n$ in which each part has size a power of two. In this note we first construct a Gray sequence on the set of binary partitions of $n$. This is an ordering of the set of binary partitions of each $n$ (or of all $n$) such that adjacent partitions differ by one of a small set of elementary transformations; here the allowed transformatios are replacing $2^k+2^k$ by $2^{k+1}$ or vice versa (or addition of a new +1). Next we give a purely local condition for finding the successor of any partition in this sequence; the rule is so simple that successive transitions can be performed in constant time. Finally we show how to compute directly the bijection between $k$ and the $k$th term in the sequence. This answers a question posed by Donald Knuth in section 7.2.1 of The Art of Computer Programming.

Affiliated with

Also associated with

No associations

Rating

A Gray path on binary partitions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Gray path on binary partitions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Gray path on binary partitions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-128539