de Bruijn列

同義語：de Bruijn 列de Bruijn系列de Bruijn sequence

概要

前提知識: 有向グラフ, Euler閉路, BEST定理

$0$ と $1$ を円周上に $00010111$ と並べ、どこからでも時計回りに連続する 3 文字を読むと、$000,001,010,101,011,111,110,100$ が得られる。長さ $3$ の $0,1$ の語 $8$ 個が、ちょうど 1 回ずつ現れている。このように、$k$ 種類の文字からなる長さ $n$ のすべての語を、巡回的に読んだ連続する $n$ 文字としてちょうど 1 回ずつ含む列を de Bruijn 列（de Bruijn sequence）という。
de Bruijn 列は、語を頂点や辺とする有向グラフ（de Bruijn グラフ）の Euler 閉路や Hamilton 閉路と一対一に対応する。Hamilton 閉路の有無は一般のグラフでは判定が難しいが、de Bruijn グラフでは Euler 閉路の問題に言い換えられるので、どの $k\ge2$、$n\ge1$ についても de Bruijn 列が存在する。この記事では、de Bruijn 列とグラフの対応、存在の証明、個数の公式 $(k!)^{k^{n-1}}/k^n$（BEST定理による）、1 文字ずつ貪欲に付け足していく構成とその正しさの証明、Lyndon 語を並べる構成を述べる。

定義

以下、$k\ge2$、$n\ge1$ を整数とし、$\Sigma:=\{0,1,\dots,k-1\}$ を文字の集合とする。$\Sigma$ の文字を $m$ 個並べたものを長さ $m$ の語といい、その全体を $\Sigma^m$ と書く（$\Sigma^0$ は空の語 $1$ つだけからなる）。$a\in\Sigma$ を $m$ 個並べた語を $a^m$ と書く。

de Bruijn 列と巡回 de Bruijn 列

$\Sigma$ の文字を $k^n$ 個並べた列 $s=(s_1,\dots,s_{k^n})$ で、添字を $k^n$ を法として読んだ連続する $n$ 文字
$$ s_js_{j+1}\cdots s_{j+n-1}\qquad(1\le j\le k^n) $$
がすべて相異なるものを、位数 $n$ の $k$ 文字の de Bruijn 列 という。巡回的なずらし $(s_j,\dots,s_{k^n},s_1,\dots,s_{j-1})$ で移り合う de Bruijn 列を同じものとみなした類を 巡回 de Bruijn 列 という。

この定義は BEST定理の記事の節「de Bruijn 列の個数」と同じである。長さ $n$ の語は $k^n$ 個あり、連続する $n$ 文字も $k^n$ 個あるので、de Bruijn 列にはどの語もちょうど 1 回ずつ現れる。巡回的なずらしもまた de Bruijn 列である。

小さい de Bruijn 列

$n=1$ では、$\Sigma$ の文字を 1 回ずつ並べた列（$k!$ 個）が de Bruijn 列である。
$k=2$、$n=2$：$0011$。連続する 2 文字は巡回的に $00,01,11,10$ である。
$k=2$、$n=3$：$00010111$ と $00011101$。後者の連続する 3 文字は $000,001,011,111,110,101,010,100$ である。
$k=3$、$n=2$：$001021122$。連続する 2 文字は $00,01,10,02,21,11,12,22,20$ である。

列を端で切って直線的に読む形もよく使われる。

すべての語を含む最短の文字列

長さ $L$ の語 $u=u_1\cdots u_L$ が、長さ $n$ のすべての語を連続する $n$ 文字 $u_i\cdots u_{i+n-1}$（$1\le i\le L-n+1$）として含むなら $L\ge k^n+n-1$ である。$L=k^n+n-1$ となる $u$ は、de Bruijn 列 $t$ の後ろに $t$ の最初の $n-1$ 文字を付けた語 $t\,t_1\cdots t_{n-1}$ にちょうど一致する。

$u$ の連続する $n$ 文字は $L-n+1$ 個なので、$L-n+1\ge k^n$ である。$t$ が de Bruijn 列なら、$t\,t_1\cdots t_{n-1}$ の連続する $n$ 文字は $t$ を巡回的に読んだ連続する $n$ 文字そのものなので、すべての語を含み、長さは $k^n+n-1$ である。
逆に $L=k^n+n-1$ とすると、連続する $n$ 文字はすべて相異なる。後で定義する de Bruijn グラフ $B(k,n)$（def-dbs-graph）でいえば、$u$ は頂点 $u_1\cdots u_{n-1}$ から出発してすべての辺をちょうど 1 回ずつ通る歩道 $u_1\cdots u_n,\ u_2\cdots u_{n+1},\ \dots$ である。$n=1$ なら主張は明らかなので $n\ge2$ とする。出発点 $x:=u_1\cdots u_{n-1}$ と終点 $y:=u_{L-n+2}\cdots u_L$ が異なれば、$x$ から出る辺の本数は $x$ に入る辺の本数より $1$ 多く使われるが、すべての辺を使うので出次数と入次数がともに $k$ であることに反する。よって $x=y$ であり、$t:=u_1\cdots u_{k^n}$ とおくと $u=t\,t_1\cdots t_{n-1}$ で、$t$ を巡回的に読んだ連続する $n$ 文字は $u$ の連続する $n$ 文字に等しいから、$t$ は de Bruijn 列である。$\square$

たとえば $k=2$、$n=3$ では、$0001011100$ が長さ $10=2^3+2$ の最短の語である。最後に打った $n$ 桁だけを照合する錠では、$k^n$ 個の番号を 1 つずつ打つ（$nk^n$ 回の打鍵）代わりに、この形の語を打てば $k^n+n-1$ 回の打鍵でどの番号も 1 回ずつ試せる。

de Bruijn グラフとの対応

de Bruijn グラフ

$B(k,n)$ を、頂点の集合を $\Sigma^{n-1}$、辺の集合を $\Sigma^n$ とし、辺 $a_1a_2\cdots a_n$ の始点を $a_1\cdots a_{n-1}$、終点を $a_2\cdots a_n$ とした多重有向グラフ（ループを許す）と定める。

これは BEST定理の記事の定義「de Bruijn グラフ」と同じものである。頂点 $x=a_1\cdots a_{n-1}$ から出る辺は末尾に文字 $c$ を足した $xc$（$k$ 本）で、その終点は $x$ の先頭を落として $c$ を足した語である。頂点に入る辺は先頭に文字を足したもの（$k$ 本）なので、$B(k,n)$ は各頂点で出次数と入次数がともに $k$ である。$n=1$ では空の語 1 頂点に $k$ 本のループが付いたグラフである。
de Bruijn グラフ B(2,3)。頂点は長さ 2 の語 00, 01, 10, 11、辺は長さ 3 の語で、辺 abc は ab から bc へ向かう。000 と 111 はループ
$B(2,3)$ では、たとえば辺 $011$ は $01$ から $11$ への辺である。辺を $110,100,000,001,010,101,011,111$ の順にたどると $11$ から出て $11$ に戻る Euler 閉路になり、各辺の最後の文字を並べると冒頭の $00010111$ が得られる（thm-dbs-existence）。

強連結性

$n\ge2$ とする。$B(k,n)$ の任意の頂点 $x$ から任意の頂点 $y=b_1\cdots b_{n-1}$ へ、長さ $n-1$ の有向の歩道がある。

$x$ から始めて、末尾に $b_1,b_2,\dots,b_{n-1}$ を順に足す辺をたどればよい。1 歩ごとに先頭の 1 文字が落ちるので、$n-1$ 歩の後の頂点は $b_1\cdots b_{n-1}=y$ である（歩道がこれただ 1 つであることは BEST定理の記事の補題「長さ $n-1$ の歩道」）。$\square$

Euler 閉路による存在

$B(k,n)$ のすべての辺をちょうど 1 回ずつ通る閉じた有向の歩道を、辺の列 $(e_1,\dots,e_{k^n})$（$e_j$ の終点が $e_{j+1}$ の始点、$e_{k^n}$ の終点が $e_1$ の始点）として書き、$e_j$ の最後の文字を $s_j$ とする。このとき $s=(s_1,\dots,s_{k^n})$ は de Bruijn 列である。とくに、すべての $k\ge2$、$n\ge1$ について位数 $n$ の $k$ 文字の de Bruijn 列が存在する。

添字を $N:=k^n$ を法として読む。$e_{j-1}$ の終点は $e_j$ の始点なので、$e_{j-1}$ の第 $2$〜$n$ 文字は $e_j$ の第 $1$〜$n-1$ 文字に等しい。これを $n-1$ 回くり返すと、$e_j$ の第 $q$ 文字は $e_{j-n+q}$ の最後の文字 $s_{j-n+q}$ に等しく、$e_j=s_{j-n+1}\cdots s_j$ である。$e_1,\dots,e_N$ は長さ $n$ の語を 1 回ずつ並べたものなので、$s$ の連続する $n$ 文字は相異なり、$s$ は de Bruijn 列である。
存在：$n=1$ では例の 1 による。$n\ge2$ では、$B(k,n)$ は各頂点で出次数と入次数が等しく、lem-dbs-strong により向きを無視して連結なので、Euler閉路の記事の命題「有向 Euler 閉路の条件」により、すべての辺を 1 回ずつ通る閉じた有向の小道をもつ。それに前半を当てればよい。$\square$

逆に de Bruijn 列 $s$ から $e_j:=s_{j-n+1}\cdots s_j$ とおけばこの形の閉じた歩道が得られ、巡回 de Bruijn 列と $B(k,n)$ の Euler 閉路（始めの辺のずらしを同一視したもの）は一対一に対応する（BEST定理の記事の命題「de Bruijn 列と Euler 閉路」）。

Hamilton 閉路による見方

有向グラフで、頂点をちょうど 1 回ずつ並べた列 $(v_1,\dots,v_M)$（$M$ は頂点の個数）で、各 $v_j$ から $v_{j+1}$ へ、および $v_M$ から $v_1$ へ辺があるものを、有向 Hamilton 閉路 という（$M=1$ ならループが 1 本あればよい）。

有向 Hamilton 閉路との対応

位数 $n$ の de Bruijn 列 $s$ に対し、$w_j:=s_js_{j+1}\cdots s_{j+n-1}$（添字は $k^n$ を法とする）とおくと、$(w_1,\dots,w_{k^n})$ は $B(k,n+1)$ の有向 Hamilton 閉路である。逆に $B(k,n+1)$ の有向 Hamilton 閉路 $(v_1,\dots,v_{k^n})$ から、$v_j$ の最初の文字を $s_j$ とすると de Bruijn 列が得られ、2 つの対応は互いに逆である。

$B(k,n+1)$ の頂点は長さ $n$ の語であり、$w_1,\dots,w_{k^n}$ はそれを 1 回ずつ並べたものである。$w_j$ から $w_{j+1}$ へは、長さ $n+1$ の語 $s_j\cdots s_{j+n}$ が辺になっている（始点 $s_j\cdots s_{j+n-1}$、終点 $s_{j+1}\cdots s_{j+n}$）。逆に有向 Hamilton 閉路では、$v_j$ から $v_{j+1}$ への辺があるので $v_j$ の第 $2$〜$n$ 文字は $v_{j+1}$ の第 $1$〜$n-1$ 文字に等しく、くり返すと $v_j=s_j\cdots s_{j+n-1}$ となる。$v_j$ は相異なる $k^n$ 個の語なので $s$ は de Bruijn 列である。2 つの構成は明らかに互いに逆である。$\square$

2 つの見方は線グラフでつながる。有向グラフ $D$ の有向線グラフ $\vec L(D)$ を、頂点の集合を $D$ の辺の集合とし、$D$ の辺の組 $(e,f)$ で $e$ の終点が $f$ の始点であるものごとに $e$ から $f$ への辺を 1 本置いた有向グラフと定める。$D$ のすべての辺を 1 回ずつ通る閉じた歩道 $(e_1,\dots,e_m)$ は、定義により $\vec L(D)$ の有向 Hamilton 閉路そのものである。$B(k,n)$ の辺 $e=a_1\cdots a_n$ と $f$ について、$e$ の終点が $f$ の始点であるのは $f=a_2\cdots a_{n+1}$ の形のときで、その組は語 $a_1\cdots a_{n+1}$ と一対一に対応する。よって
$$ \vec L\bigl(B(k,n)\bigr)\cong B(k,n+1) $$
であり、thm-dbs-existence と prop-dbs-hamilton は同じ対応を辺の側と頂点の側から見たものである。無向の単純グラフでの類似は線グラフの記事の命題「Euler 閉路から Hamilton 閉路へ」である。

個数

de Bruijn 列の個数の公式

位数 $n$ の $k$ 文字の巡回 de Bruijn 列は $(k!)^{k^{n-1}}/k^n$ 個あり、de Bruijn 列（ずらしを区別する）は $(k!)^{k^{n-1}}$ 個ある。

これは BEST定理の記事の定理「de Bruijn 列の個数」である。$B(k,n)$ の Euler 閉路を、Euler 閉路の個数と根に向かう有向全域木の個数を結ぶ BEST定理で数え、有向全域木の個数を隣接行列の固有値から求める（$B(k,n)$ の隣接行列 $A$ は $A^{n-1}$ がすべての成分 $1$ の行列になる）。

$(k,n)$	巡回 de Bruijn 列の個数	例
$(2,1)$	$1$	$01$
$(2,2)$	$1$	$0011$
$(2,3)$	$2$	$00010111$、$00011101$
$(2,4)$	$16$	$0000100110101111$ など
$(2,5)$	$2048$
$(3,2)$	$24$	$001021122$ など
$(3,3)$	$373248$
$(4,2)$	$20736$	$0010203112132233$ など

$k=2$ では巡回 de Bruijn 列は $2^{2^{n-1}-n}$ 個で、$n$ とともに急速に増える。

構成

存在の証明は Euler 閉路の存在に頼っている。具体的な de Bruijn 列は、1 文字ずつ貪欲に付け足していくだけで作れる。

貪欲法

小さい文字を優先する貪欲法

$w:=(k-1)^{n-1}$ とし、語 $s:=w$ から始めて、次の操作をくり返す。

文字 $c\in\Sigma$ で、$sc$ の最後の $n$ 文字が $s$ の連続する $n$ 文字としてまだ現れていないものがあれば、そのうち最小の $c$ を $s$ の末尾に付ける。
そのような $c$ がなければ止まる。

$s$ の長さは 1 回の操作で $1$ ずつ増え、そのたびに連続する $n$ 文字が新しく 1 つ現れる。連続する $n$ 文字は相異なるまま保たれるので、操作は $k^n$ 回以内で止まる。

貪欲法の正しさ

貪欲法が止まったときの語を $s=s_1\cdots s_L$ とする。このとき $L=k^n+n-1$ であり、長さ $n$ のすべての語が $s$ の連続する $n$ 文字としてちょうど 1 回ずつ現れ、$s$ の最後の $n-1$ 文字は $w=(k-1)^{n-1}$ である。とくに、$s$ から最初の $n-1$ 文字 $w$ を除いた長さ $k^n$ の列 $t:=s_n\cdots s_L$ は de Bruijn 列である。

$n=1$ では $w$ は空の語で、貪欲法は $0,1,\dots,k-1$ を順に付けて止まるので主張は明らかである。$n\ge2$ とし、de Bruijn グラフ $B(k,n)$ で考える。$s$ の連続する $n$ 文字 $s_{j-n+1}\cdots s_j$（$j\ge n$）は $B(k,n)$ の辺で、その始点は 1 つ前の辺の終点である。よって $s$ の作られ方は、頂点 $w$ から出発して同じ辺を 2 度通らない有向の歩道を 1 辺ずつ延ばしていく手続きである。いま居る頂点を $x$（$s$ の最後の $n-1$ 文字）とすると、文字 $c$ を付けられるのは辺 $xc$ がまだ使われていないときで、貪欲法は $x$ から出る未使用の辺のうち最後の文字が最小のものを通る。止まるのは、$x$ から出る辺がすべて使われたときである。
(a) 止まるのは $w$ である。 歩道が $w$ 以外の頂点 $x$ に居るとき、$x$ に入った回数は $x$ から出た回数より $1$ 多い（出発点が $w$ だから）。入った回数は入次数 $k$ 以下なので、出た回数は $k-1$ 以下であり、$x$ から出る未使用の辺が残っている。よって歩道は $w$ 以外では止まらない。したがって $s$ の最後の $n-1$ 文字は $w$ である。
(b) すべての辺を使う。 歩道は $w$ から出て $w$ で止まるので、どの頂点でも入った回数と出た回数は等しい。また $w$ から出る辺はすべて使われている。未使用の辺が残ったとし、未使用の辺が出ている頂点の集合を $U$ とすると、$w\notin U$ である。
$u=u_1\cdots u_{n-1}\in U$ とする。辺 $u(k-1)$ は未使用である。実際、それが使われたなら、それを選んだ時点で $u$ から出る未使用の辺は最後の文字が $k-1$ のものしかなかったことになり（貪欲法は最小の文字を選ぶ）、その時点で $u$ から出る辺はすべて使われ、$u\notin U$ となる。辺 $u(k-1)$ の終点を $u':=u_2\cdots u_{n-1}(k-1)$ とする。$u'$ に入る辺のうち $u(k-1)$ が未使用なので、$u'$ に入った回数は $k$ 未満であり、出た回数も $k$ 未満だから $u'\in U$ である。
こうして $u\in U$ から始めて「先頭を落として $k-1$ を足す」ことを $n-1$ 回くり返すと、すべて $U$ の中にとどまり、最後に $(k-1)^{n-1}=w$ に着く。これは $w\notin U$ に反する。よってすべての辺が使われる。
(a)(b) により、$s$ の連続する $n$ 文字は長さ $n$ の語をちょうど 1 回ずつ並べたもので、$L-n+1=k^n$ である。$t$ の長さは $k^n\ge n-1$ なので、$s$ の最後の $n-1$ 文字 $w$ は $t$ の最後の $n-1$ 文字でもある。したがって $t$ を巡回的に読んだ連続する $n$ 文字は、$t$ の最後の $n-1$ 文字を $t$ の前に付けた語 $w\,t=s$ の連続する $n$ 文字に等しく、$t$ は de Bruijn 列である。$\square$

証明の (b) は、BEST定理の証明で「各頂点を最後に出る辺」が根に向かう有向全域木になることと同じ考え方である。貪欲法では、$w$ 以外の各頂点を最後に出る辺は $u(k-1)$ で、これらは $w$ に向かう有向全域木をなす。

$k=2$、$n=3$ の貪欲法

$w=11$ から始める。付ける文字と、新しく現れる連続する 3 文字は次のとおりである。

語 $s$	付けた文字	新しい 3 文字	理由
$11$			初めの語
$110$	$0$	$110$
$1100$	$0$	$100$
$11000$	$0$	$000$
$110001$	$1$	$001$	$000$ は使用済み
$1100010$	$0$	$010$
$11000101$	$1$	$101$	$100$ は使用済み
$110001011$	$1$	$011$	$010$ は使用済み
$1100010111$	$1$	$111$	$110$ は使用済み

次は $110$ も $111$ も使用済みなので止まる。最初の $11$ を除くと $00010111$ である。$k=3$、$n=2$ では、$2$ から始めて $2001021122$ で止まり、$001021122$ を得る。

Lyndon 語の連結

貪欲法の出力は、語を辞書式に並べる組合せ論的な規則でも書ける。長さの等しい語は、最初に異なる文字の大小で比べる（辞書式順序）。

ネックレスと Lyndon 語

長さ $n$ の語 $a=a_1\cdots a_n$ が、そのすべての巡回的なずらし $a_j\cdots a_na_1\cdots a_{j-1}$ のうち辞書式で最小であるとき、$a$ を（長さ $n$ の）ネックレスという。$a$ の巡回的なずらしで $a$ に等しくなる最小のずらし幅 $d\ge1$ を $a$ の周期といい、長さ $d$ の接頭辞 $a_1\cdots a_d$ を $a$ の非周期的な接頭辞という。周期が長さに等しいネックレスを Lyndon 語 という。

周期 $d$ は $n$ を割り、$a$ は非周期的な接頭辞を $n/d$ 回くり返した語である。ネックレスの巡回的なずらしは相異なるものがちょうど $d$ 個あるので、長さ $n$ の語は、ネックレスごとの類（$d$ 個ずつ）に分かれる。長さ $n$ のネックレスの非周期的な接頭辞は、長さが $n$ を割る Lyndon 語であり、逆に長さが $n$ を割る Lyndon 語をくり返して長さ $n$ にした語はネックレスである（SWW16 p. 3）。

Fredricksen–Kessler–Maiorana の定理

長さ $n$ のネックレスを辞書式の昇順に並べ、それぞれの非周期的な接頭辞をこの順に連結した列は、位数 $n$ の $k$ 文字の de Bruijn 列である。さらにこの列は、thm-dbs-greedy の $t$ に一致し、長さ $k^n$ の語として辞書式で最小の de Bruijn 列である。

定理の所在

この記事では証明しない（SWW16 §1.1、pp. 2–3、Theorem 1、p. 4。そこでは文字を $1,\dots,k$ とし、長さ $n$ のすべての語の集合に Theorem 1 を当てる）。列の長さが $k^n$ になることは、各ネックレスの類が周期と同じ個数の語からなることから分かる。

ネックレスの連結

$k=2$、$n=3$：ネックレスは $000,001,011,111$ で、非周期的な接頭辞は $0,001,011,1$ である。連結すると $0\cdot001\cdot011\cdot1=00010111$ で、ex-dbs-greedy-run と一致する。
$k=2$、$n=4$：ネックレス $0000,0001,0011,0101,0111,1111$ の非周期的な接頭辞 $0,0001,0011,01,0111,1$ を連結して $0000100110101111$ を得る。
$k=3$、$n=2$：$0\cdot01\cdot02\cdot1\cdot12\cdot2=001021122$。

反例

外す条件・替える条件	反例	成り立たなくなること
連続する $n$ 文字を巡回的に読む	$00010111$ を直線的に読む	すべての語が現れること（$110$ と $100$ が現れない）
貪欲法を $w=(k-1)^{n-1}$ から始める	$k=3$、$n=2$ で $0$ から始める	貪欲法の出力が de Bruijn 列を与えること（$001020$ で止まり、$11,12,21,22$ が現れない）
ネックレスを辞書式の昇順に並べる	$k=2$、$n=3$ で $0,011,001,1$ の順に連結する	連結が de Bruijn 列であること（$00110011$ では $001$ が 2 回現れる）
非周期的な接頭辞（長さが $n$ を割る Lyndon 語）を使う	$k=2$、$n=3$ で長さ $3$ 以下の Lyndon 語 $0,001,01,011,1$ をすべて連結する	長さが $k^n$ であること（長さ $10$ になる）

1 行目は prop-dbs-shortest のとおり、直線的に読むなら最初の $n-1$ 文字を後ろに付け足す必要がある。2 行目では、歩道の出発点の頂点が $0$ になり、貪欲法は $0$ に戻って $0$ から出る辺を使い切ったところで止まる。thm-dbs-greedy の証明の (b) で使った「各頂点から辺 $u(k-1)$ をたどると出発点に着く」が成り立たない（頂点 $2$ では $u(k-1)=22$ がループで、出発点 $0$ に着かない）。

応用

位置の検出：円周を $k^n$ 個の区画に分け、de Bruijn 列の文字で順に塗ると、連続する $n$ 区画の文字を読むだけで、そこが円周のどの位置かが一意に分かる（定義から直ちに従う）。
最短の総当たり：prop-dbs-shortest により、$n$ 桁の暗証番号をすべて試すのに必要な打鍵の最小回数は $k^n+n-1$ で、de Bruijn 列から作った語がそれを実現する。
ネットワークやゲノム解析：de Bruijn 列と de Bruijn グラフは、オーバーレイネットワークの動的な接続、ゲノム解析、計算機の語の中の $1$ の位置の索引づけなどに使われている（SWW16 §1.3、p. 5 の例示）。

補足

名前と歴史：$k=2$ の個数 $2^{2^{n-1}-n}$ は de Bruijn（1946）が示し、一般の $k$ の公式は van Aardenne-Ehrenfest と de Bruijn（1951）による。$k=2$ の公式は Flye Sainte-Marie（1894）がすでに示していた。貪欲法は Martin（1934）、ネックレスによる構成は Fredricksen と Kessler（$k=2$）、Fredricksen と Maiorana（一般の $k$）による（以上 SWW16 §1.1、p. 2）。
貪欲法の向き：文字の役割を入れ替えた「大きい文字を優先し $0^{n-1}$ から始める」貪欲法も同じ証明で正しい（$c\mapsto k-1-c$ と置き換える）。$k=2$ では「$0^{n-1}$ から始めて付けられるなら $1$ を付ける」という規則になり、$n=3$ では $11101000$（$00011101$ の巡回的なずらし）を与える。
一般化：長さ $n$ の語の部分集合 $S$ について、$S$ の元をちょうど 1 回ずつ連続する $n$ 文字として含む巡回列を、$S$ の普遍巡回列（universal cycle）という。$S$ が巡回的なずらしで閉じ、ほかにも条件を満たすとき、貪欲法とネックレスの連結がともに辞書式で最小の普遍巡回列を与える（SWW16 Theorem 1、p. 4）。