Cfrgtkky

I'm seeking to implement a function $phi(n,k,i)$ of integers $n,k,i$ where $$1 leq k < n\1 leq i leq N\N = {n choose k}$$ that returns all possible $n$-element binary vectors containing $k$ $1$'s, in sequence, with $i$ specifying the index of the element to return. Additionally, the elements (words) of the sequence must be ordered in such a way that every word differs "as much as possible" from all prior words in terms of Hamming distance.

That is, letting the words of the sequence be $w_1, w_2, ldots, w_N$ with $$w_i = phi(n,k,i)$$ and $d(w_1,w_2)$ be the Hamming distance between $w_1$ and $w_2$, I'd like to maximize a function $$J = sum _{i = 2}^{N} D(i)$$ over the order of the words in the sequence, where $D(i)$ is a rough measure of the distance of the $i$'th word from all its predecessors, such as $$D(i) = sum_{j=1}^{i-1} d(w_i,w_j)$$ or perhaps a fancier weighted-by-recency version such as $$D(i) = sum_{j=1}^{i-1} d(w_i,w_j); r^{i-1-j}$$ for $0 < r < 1$.

I don't want to define "rough measure" more rigorously than this since any $D$ that yields values positively correlating to either of the above is also fine--the stronger the correlation, the better.

In a sense, I'm looking for the "opposite" of a binary Gray code (wherein successive words are designed to resemble their nearest predecessors as much as possible).

The motivation is to generate the sequence in a deterministic way so that when $phi$ is queried to return the first $p$ words of the sequence, with $p$ typically being $ll N$, the set of words is always diverse. In actuality, the words represent bit masks for the $k$-element subsets of an $n$-element set. Like creating $p$ dishes where $k$ ingredients are selected for each dish from a common pool of $n$, such that the diversity in combinations of ingredients is as high as possible even if $p$ is small.

Finally, while I know this problem can be brute-forced by evaluating $J$ for each one of the $2^N$ possible word orderings, $N$ will typically be $> 1000$, ruling this out as a practical option. An algorithm for implementing $phi$ with $O(N^2)$--or ideally $O(N log N)$, $O(N)$, or better--time and memory requirements is ultimately what I'm looking for.

It seems to me that with all the mathematical and computer science research going on out there, somebody must have come up with some ideas on this.

The algorithm linked to in the comments takes the $n-$ bit standard Gray code, appends a 0 to the left and then uses complementation to every other pattern in order to obtain maximal change in consecutive words. This would seem to address your requirements.

Donald Knuth's Pre-Fascicle 2A, available here discusses a number of different gray code algorithms and introduces the idea of a delta sequence which can be used for efficient generation of the next Gray codeword.