Recorrer $k$-elemento subgrupos por elementos de conmutación

Question

Me gustaría recorrer el $k$-elemento de subconjuntos de a $\{1,2, \dots, n\}$ en forma natural por elementos de conmutación.

Dos subconjuntos $v,w$ son adyacentes si $|v \cap w| = k-1$ o, equivalentemente, si su diferencia simétrica es $|v \triangle w| = 2$.

Es posible recorrer todos los $k$-elemento subconjuntos de modo que cada uno es adyacente a la última? Este sería un circuito Hamiltoniano en el Johnson Gráfico (véase el Capítulo 7 en este pdf notas)

Answer 1

Esta encuesta papel, "Un estudio de la Combinatoria Gris Códigos", por C. Savage, proporciona varias referencias a su problema en las páginas 13-14. En particular, no es un simple algoritmo para recorrer las $k$-elemento subconjuntos de modo que cada una difiere de la anterior en una sola posición:

Como se observa en [BER76], un código Gray para las combinaciones puede ser extraído de las binario reflejado código Gray para $n$-bit números: eliminar de la binario reflejado código Gray lista de todos los elementos correspondientes a los subconjuntos que no tienen exactamente $k$ elementos. La que sigue es una lista de todas las $k$-subconjuntos en que las sucesivas establece difieren en exactamente un elemento.

[BER76] J. R. Bitner, G. Ehrlich, y E. M. Reingold. "La generación eficiente de los binarios se refleja Código Gray". En Communications of the ACM, 19(9):517-521, 1976. Savage también se refiere a en 1989 en un papel de Wilf que ella dice que contiene varias otras soluciones.

(He encontrado esto por adivinar que esto tendría algo que ver con el Gris de los códigos y, a continuación, hacer la búsqueda de Google para gray code with fix number of bits set. El Salvaje papel fue el primer golpe. Sólo menciono esto en la esperanza de que será útil en el futuro.)