First, let's solve a simpler problem.
De Bruijn sequences involve a sliding window, which contains every possibility exactly once as it slides around the circular sequence.
But here we do not care about the order of elements within the window. So instead of a "window" that advances by removing the leftmost element and adding a rightmost element, let's instead consider a "bag" of $n$ unordered elements, that advances by removing any element and replacing it with a new one. We will say an unordered de Bruijn sequence is a sequence of bag-contents that cycles through all possibilities exactly once.
De Bruijn Sequence Unordered De Bruijn Sequence
000 window size n=3 00 bag size n=2
001 alphabet size k=2 10 alphabet size k=3
111 at each step, first element is 12 at each step, exactly
110 removed, others shift to left, 22 one element changes
101 and new element is added to end 02
010 00 = start
000 = start
Let's consider the question:
Is there an unordered de Bruijn sequence for all positive $n$ and $k$?
The answer to this question is yes (when $n \ge 2$ or $k=1$), as we can see by looking at the graph of possible bag states, which is an $(n-1)$-dimensional triangular grid of size $k+1$. The question amounts to asking whether there is a Hamiltonian cycle through this grid.
The existence of a Hamiltonian cycle is easy to see inductively: an $(n-1)$-dimensional pyramid of size $k+1$ can be decomposed into a slightly smaller $(n-1)$-dimensional pyramid of size $k$, plus a face which is a $(n-2)$-dimensional pyramid of size $k+1$. Using (inductively) Hamiltonian cycles through both of these, we mark an edge of the pyramid's cycle where it leaves a corner of the pyramid as $A$, and a similar edge of the face's cycle where it leaves a corner of the face as $B$. Now we extend the pyramid by placing the face next to it so that $A$ and $B$ are parallel and adjacent. This way, we can connect the Hamiltonian cycles to each other, by replace $A$ and $B$ with two edges that connect the cycles into one Hamiltonian cycle of the original pyramid.
The base case for the induction has two parts:
• A pyramid of size 1 in any number of dimensions has just 1 point in it, and its trivial empty cycle works for the inductive step.
• A pyramid of dimension 2 always has a Hamiltonian cycle:
* / \
* / \ / /__
* / \ / __\ / ____\ etc.
* . . / /__ / /____ / /______
* * * . * *_____* *_______* *_________*
Now let's go back and consider the original question, which involved a sliding window. Now, we still need to find a Hamiltonian cycle through the pyramid, but now our moves are constrained by needing to always remove the element that was inserted $n$ steps ago.
When $k=1$, there is a cycle of length 1 regardless of $n$.
When $k=2$ (a one dimensional pyramid, i.e., a segment), there is a path but no cycle when $n>1$.
When $k=3$, there is a cycle for $n=1$ and $n=2$, and a Hamiltonian path (but no cycle) when $n=3$, and not even a path when $n>3$.
To see this, note that when leaving a corner of the triangle, the path must go directly towards the opposite side. For the second corner visited by the path, the path must go all the way to the opposite side, for either direction of travel, which results in topological trouble for visiting the entirety of the triangle.
For $k \ge 4$, the topological trouble goes away, and when $n$ is large, the large number of possible Hamiltonian cycles may make up for the restriction coming from the sliding window, so I would guess there are such Hamiltonian cycles, but I haven't seen any examples yet.