第29章

ジョンソン–トロッターのアルゴリズム

（やさしい版） Pearls of Functional Algorithm Design（関数プログラミングによるアルゴリズム設計の真珠）

どんな問題？

「順列を1つずつ出す」問題

たとえば "abcd" という文字列があったとき、その並び替え（順列）は全部で 4! = 24 通りあります。この 24 個を、1つの並びから次の並びに移るときに「隣り合う2文字を1回だけ入れ替える」だけで済むように順に出したい、というのが今回のテーマです。

ポイント ふつうに全順列を出す方法（辞書順など）は、次の並びに移るときに複数の場所を書き換える必要があります。ジョンソン–トロッター（Johnson–Trotter）のアルゴリズムは、常に「隣同士のスワップ1回」だけで次の順列にたどり着けるという、とても嬉しい性質を持ちます。

この章のゴール

この章では、そのアルゴリズムの「ループレス版」を作ります。ループレスとは、大ざっぱに言うと「次の順列を出す1ステップが定数時間で終わる」ような書き方のことです。

使う道具は、前章で作った一般化された牛耕（boustrophedon）積 boxall です。

再帰でまず定式化する

アイデア：「x を左右に走らせる」

長さ n のリストに対する遷移列を、長さ n−1 のリストに対する遷移列から再帰的に組み立てます。リストの各位置に 0 から n−1 の番号をつけ、リスト全体を xs ++ [x]（最後の要素が x）と書きます。

「遷移 i」は、「位置 i と位置 i−1 の要素を入れ替える」という意味です。

  1. 下向きの走行：遷移列 [n−1, n−2, ..., 1] を適用すると、x が末尾から先頭まで一段ずつ移動し、順列は [x] ++ xs になります。
  2. 次に、xs の順列を作る遷移列を [j1, j2, ...] とし、その最初の遷移 j1+1 を適用します。xs が x の1つ右にずれているので、番号を1つずらす必要があるのです。
  3. 上向きの走行：遷移列 [1, 2, ..., n−1] で x を再び末尾まで戻します。結果は ys ++ [x]（ここで ys は xs に遷移 j1 を適用した結果）となります。
  4. あとは、x の下向き走行と上向き走行を、xs の遷移列と交互に織り込んでいくだけです。
具体例 "abcd" にまず [3, 2, 1] を適用 → "abdc", "adbc", "dabc"（x="d" が先頭に来ました）。
次に [3, 1, 2, 3] を適用 → "dacb", "adcb", "acdb", "acbd"（x="d" が末尾に戻りました）。
こうして 24 通りの順列を、隣接スワップだけで巡っていきます。

コードにする

この手続きは、前章の牛耕積 (□) を使うと、とても素直にコードになります。

jcode :: Int → [Int] jcode 1 = [] jcode n = (bumpBy 1 (jcode (n−1))) □ [n−1, n−2 .. 1]
Dart // jcode n : 長さ n の順列を巡る遷移コード列 // (bumpBy 1 (jcode (n-1))) □ [n-1, n-2, ..., 1] List<int> jcode(int n) { if (n <= 1) return <int>[]; final List<int> downRun = List<int>.generate(n - 1, (int i) => n - 1 - i); // [n-1, ..., 1] return boxProduct(bumpBy(1, jcode(n - 1)), downRun); }

ここで bumpBy k は、リストの偶数位置（0番目、2番目、…）にある要素だけに k を足す関数です。

bumpBy k [] = [] bumpBy k [a] = [a + k] bumpBy k (a : b : as) = (a + k) : b : bumpBy k as
Dart // bumpBy k xs : xs の偶数位置（0,2,4,...）にある要素だけに k を足す List<int> bumpBy(int k, List<int> xs) { final List<int> ys = List<int>.of(xs); for (int i = 0; i < ys.length; i += 2) { ys[i] += k; } return ys; } // 牛耕積 (□) : jcode で使う 2 引数版（前章 boxall の簡易版） // xs □ ys = ys ++ [x_0] ++ reverse(ys) ++ [x_1] ++ ys ++ [x_2] ++ ... List<int> boxProduct(List<int> xs, List<int> ys) { final List<int> out = <int>[...ys]; bool flip = true; for (final int x in xs) { out.add(x); out.addAll(flip ? ys.reversed : ys); flip = !flip; } return out; }

私たちの仕事は、この jcode をループレスにすることです。

方針

boxall に帰着させる

ざっくりした計画はこうです。

そのためには、jcode を少し一般化した関数 code を考えます。

code (k, n) = bumpBy k (jcode n)
Dart // code (k, n) = bumpBy k (jcode n) （一般化された jcode） List<int> code(int k, int n) => bumpBy(k, jcode(n));

明らかに jcode n = code (0, n) です。n が奇数のとき、次のように順に書き換えていきます。

code (k, n) = {定義} bumpBy k (jcode n) = {jcode の定義} bumpBy k (bumpBy 1 (jcode (n−1)) □ [n−1, n−2 .. 1]) = {下で示す主張} bumpBy (k+1) (jcode (n−1)) □ bumpBy k [n−1, n−2 .. 1] = {code の定義と bumpDn} code (k+1, n−1) □ bumpDn (k, n)

ここで bumpDn（「バンプ・ダウン」）は次のように定義します。

bumpDn (k, n) = bumpBy k [n−1, n−2 .. 1] (29.1)
Dart // bumpDn (k, n) = bumpBy k [n-1, n-2, ..., 1] List<int> bumpDnList(int k, int n) { final List<int> xs = List<int>.generate(n - 1, (int i) => n - 1 - i); // [n-1, ..., 1] return bumpBy(k, xs); }

使った主張

途中で使ったのは、こんな主張です。

bumpBy k (xs □ ys) = if even (length ys) then bumpBy k xs □ bumpBy k ys else xs □ bumpBy k ys

これは □ の定義と、次の bumpBy の性質から証明できます（詳細は演習）。

bumpBy k (xs ++ [y] ++ ys) = if even (length xs) then bumpBy k xs ++ bumpBy k ([y] ++ ys) else bumpBy k xs ++ [y] ++ bumpBy k ys

code の一般形

n が偶数のときも同様に計算でき、まとめると次のような code の定義が得られます。

code (k, 1) = [] code (k, n) = code (k', n−1) □ bumpDn (k, n) where k' = if odd n then k+1 else 1
Dart // code (k, n) の再帰版（□ = boxProduct） List<int> codeRec(int k, int n) { if (n <= 1) return <int>[]; final int kPrime = n.isOdd ? k + 1 : 1; return boxProduct(codeRec(kPrime, n - 1), bumpDnList(k, n)); }

たとえば、□ は結合的なので、次のようにきれいに展開できます。

code (0, 4) = bumpDn (2, 2) □ bumpDn (1, 3) □ bumpDn (0, 4)

boxall = foldr (□) [ ] を思い出すと、code は次のように書き直せます。

code = boxall · map bumpDn · pairs
Dart // code = boxall · map bumpDn · pairs // pairs (k, n) の各 (k, n) に bumpDn を適用し、□ で全部たたみ込む List<int> codeViaBoxall(int k, int n) { final List<(int, int)> ps = pairs(k, n); final List<List<int>> blocks = ps.map(((int, int) kn) => bumpDnList(kn.$1, kn.$2)).toList(); return boxall(blocks); } // boxall = foldr (□) [] （2 引数版 boxProduct の一般化） List<int> boxall(List<List<int>> xss) { List<int> acc = <int>[]; for (final List<int> xs in xss.reversed) { acc = boxProduct(xs, acc); } return acc; }

ここで pairs は、上の展開に現れる (k, n) の対の列を作る関数です。

pairs :: (Int, Int) → [(Int, Int)] pairs (k, 1) = [] pairs (k, n) = pairs (k', n−1) ++ [(k, n)] where k' = if odd n then k+1 else 1
Dart // pairs (k, n) : 素朴な再帰版（Θ(n^2)） // Dart 3 のレコード型 (int, int) を使う List<(int, int)> pairs(int k, int n) { if (n <= 1) return <(int, int)>[]; final int kPrime = n.isOdd ? k + 1 : 1; return <(int, int)>[...pairs(kPrime, n - 1), (k, n)]; }

pairs を線形時間に

pairs (k, n) はそのままだと Θ(n2) 時間かかりますが、蓄積パラメータ（アキュムレータ）を使うと Θ(n) に落ちます。

addpair (k, n) ps = pairs (k, n) ++ ps
Dart // addpair (k, n) ps = pairs (k, n) ++ ps （仕様） List<(int, int)> addpairSpec(int k, int n, List<(int, int)> ps) => <(int, int)>[...pairs(k, n), ...ps];

これを直接定義すると次のようになります。

pairs (k, n) = addpair (k, n) [] addpair (k, 1) ps = ps addpair (k, n) ps = addpair (k', n−1) ((k, n) : ps) where k' = if odd n then k+1 else 1
Dart // pairs の線形時間実装（アキュムレータ ps を使う） List<(int, int)> pairsLinear(int k, int n) => addpair(k, n, <(int, int)>[]); List<(int, int)> addpair(int k, int n, List<(int, int)> ps) { // 末尾再帰をループに展開 while (n > 1) { ps = <(int, int)>[(k, n), ...ps]; k = n.isOdd ? k + 1 : 1; n = n - 1; } return ps; }

以上より、jcode は次のように書けます。

jcode = boxall · map bumpDn · pairs where pairs n = addpair (0, n) []
Dart // jcode = boxall · map bumpDn · pairs （まだループレスではない中間版） List<int> jcodeViaBoxall(int n) { final List<(int, int)> ps = addpair(0, n, <(int, int)>[]); final List<List<int>> blocks = ps.map(((int, int) kn) => bumpDnList(kn.$1, kn.$2)).toList(); return boxall(blocks); }
ちょっと待って 「boxall はループレスにできる」と分かっているので、これでループレスな jcode ができた——と思いたくなります。ところが実は、まだ完成ではありません。次の節で理由が明らかになります。

本物のループレス化

プロローグが遅い

問題は、プロローグ（前処理）に入っている map bumpDn (pairs n) の部分です。これは Θ(n2) ステップかかります。ループレスの規則では、プロローグは Θ(n) ステップまでしか許されません。

ということで、本当にやりたいのは boxall · map bumpDn をまとめてループレスにすることです。まずは bumpDn だけをループレスにしてみましょう。

bumpDn をループレスにする

状態として四つ組 (j, k, m, n) を持ちます。

bumpDn = unfoldr stepDn · prologDn prologDn (k, n) = (k, k, n−1, 1) stepDn (j, k, m, n) = if m < n then Nothing else Just (m + j, (k−j, k, m−1, n))
Dart // 四つ組の状態 (j, k, m, n) ※方向 i は次で導入する typedef DnState = (int j, int k, int m, int n); // bumpDn = unfoldr stepDn · prologDn DnState prologDn4(int k, int n) => (k, k, n - 1, 1); // unfoldr stepDn : Dart の sync* generator で表現 Iterable<int> bumpDnLoopless(int k, int n) sync* { DnState s = prologDn4(k, n); while (true) { final (int j, int kk, int m, int nn) = s; if (m < nn) return; // stepDn の Nothing yield m + j; s = (kk - j, kk, m - 1, nn); } }

同じように、reverse · bumpDn（逆順に出す版）もループレスにできます。

reverse · bumpDn = unfoldr stepUp · prologUp prologUp (k, n) = (if even n then k else 0, k, 1, n−1) stepUp (j, k, m, n) = if m > n then Nothing else Just (m + j, (k−j, k, m+1, n))
Dart // reverse · bumpDn = unfoldr stepUp · prologUp DnState prologUp4(int k, int n) => (n.isEven ? k : 0, k, 1, n - 1); Iterable<int> reverseBumpDnLoopless(int k, int n) sync* { DnState s = prologUp4(k, n); while (true) { final (int j, int kk, int m, int nn) = s; if (m > nn) return; // stepUp の Nothing yield m + j; s = (kk - j, kk, m + 1, nn); } }

2つの step を1つに統合

stepDn と stepUp は、方向を表す成分 i（−1 なら下向き、+1 なら上向き）を加えれば、一つの bump という関数にまとめられます（step という名前は後で別に使うので取っておきます）。

bumpDn = unfoldr bump · prologDn reverse · bumpDn = unfoldr bump · prologUp
bump (i, j, k, m, n) = if i ∗ (n−m) < 0 then Nothing else Just (m + j, (i, k−j, k, m+i, n)) prologDn (k, n) = (−1, k, k, n−1, 1) prologUp (k, n) = (1, if even n then k else 0, k, 1, n−1)
Dart // 五つ組の状態 (i, j, k, m, n) : i = ±1 が方向 typedef BumpState = (int i, int j, int k, int m, int n); // bump : Nothing を返すか、次の遷移値と次の状態を返す // sealed class + パターンマッチで Maybe を表現 sealed class BumpResult {} class BumpDone extends BumpResult {} class BumpStep extends BumpResult { final int value; final BumpState next; BumpStep(this.value, this.next); } BumpResult bump(BumpState s) { final (int i, int j, int k, int m, int n) = s; if (i * (n - m) < 0) return BumpDone(); return BumpStep(m + j, (i, k - j, k, m + i, n)); } BumpState prologDn(int k, int n) => (-1, k, k, n - 1, 1); BumpState prologUp(int k, int n) => (1, n.isEven ? k : 0, k, 1, n - 1); // unfoldr bump : 状態から遷移コード列を遅延に取り出す Iterable<int> unfoldBump(BumpState start) sync* { BumpState s = start; while (true) { switch (bump(s)) { case BumpDone(): return; case BumpStep(:final int value, :final BumpState next): yield value; s = next; } } }

boxall のループレス定義を思い出す

前章では、boxall のループレス定義が次の形をしていました。

prolog = wrapQueue · fst · foldr op (empty, empty)

そこで使う op と mix はこうでした。

op xs (ys, sy) = if even (length xs) then (mix xs (ys, sy), mix (reverse xs) (sy, ys)) else (mix xs (ys, sy), mix (reverse xs) (ys, sy)) mix [] (ys, sy) = ys mix (x : xs) (ys, sy) = insert ys (Node x (mix xs (sy, ys)))
Dart // 前章の boxall ループレス版で使う op / mix（イーガー版） // 森 (Forest) = Queue<Rose> ； ここでは List<RoseEager> で代用 class RoseEager { final int value; final ForestEager children; RoseEager(this.value, this.children); } typedef ForestEager = List<RoseEager>; // op xs (ys, sy) : リスト xs を薔薇木として mix で織り込む (ForestEager, ForestEager) op(List<int> xs, (ForestEager, ForestEager) ysy) { final (ForestEager ys, ForestEager sy) = ysy; final ForestEager rxs = xs.reversed.toList(); if (xs.length.isEven) { return (mixEager(xs, (ys, sy)), mixEager(rxs, (sy, ys))); } else { return (mixEager(xs, (ys, sy)), mixEager(rxs, (ys, sy))); } } ForestEager mixEager(List<int> xs, (ForestEager, ForestEager) ysy) { if (xs.isEmpty) return ysy.$1; final int x = xs.first; final List<int> rest = xs.sublist(1); final ForestEager sub = mixEager(rest, (ysy.$2, ysy.$1)); // insert ys node : キュー末尾に追加 return <RoseEager>[...ysy.$1, RoseEager(x, sub)]; }

また step は次のようでした。

step [] = Nothing step (zs : zss) = Just (x, consQueue xs (consQueue ys zss)) where (Node x xs, ys) = remove zs consQueue :: Queue a → [Queue a] → [Queue a] consQueue xs xss = if isempty xs then xss else xs : xss wrapQueue :: Queue a → [Queue a] wrapQueue xs = consQueue xs []
Dart // step : 森の列を1歩進める（前章の boxall step のイーガー版） (int, List<ForestEager>)? stepEager(List<ForestEager> zss) { if (zss.isEmpty) return null; final ForestEager zs = zss.first; final List<ForestEager> rest = zss.sublist(1); // remove zs : キュー先頭 (Node x xs) を取り出し、残り ys を返す final RoseEager head = zs.first; final ForestEager ys = zs.sublist(1); return (head.value, consQueue(head.children, consQueue(ys, rest))); } List<ForestEager> consQueue(ForestEager xs, List<ForestEager> xss) => xs.isEmpty ? xss : <ForestEager>[xs, ...xss]; List<ForestEager> wrapQueue(ForestEager xs) => consQueue(xs, <ForestEager>[]);

fold-map 融合で1つにまとめる

順に書き換えていきます。

jcode = {boxall を用いた jcode の定義} boxall · map bumpDn · pairs = {boxall のループレス定義} unfoldr step · wrapQueue · fst · foldr op (empty, empty) · map bumpDn · pairs = {fold-map 融合} unfoldr step · wrapQueue · fst · foldr op' (empty, empty) · pairs

ここで新しい op' は

op' (k, n) (ys, sy) = op (bumpDn (k, n)) (ys, sy)
Dart // op' (k, n) (ys, sy) = op (bumpDn (k, n)) (ys, sy) （仕様レベル） (ForestEager, ForestEager) opPrimeSpec( int k, int n, (ForestEager, ForestEager) ysy, ) => op(bumpDnList(k, n), ysy);

と定義されます。展開して、n が奇数のときに bumpDn (k, n) の長さが偶数であることや prologDn, prologUp の定義を使うと、次を得ます。

op' (k, n) (ys, sy) = if odd n then (mix (unfoldr bump (−1, k, k, n−1, 1)) (ys, sy), mix (unfoldr bump (1, 0, k, 1, n−1)) (sy, ys)) else (mix (unfoldr bump (−1, k, k, n−1, 1)) (ys, sy), mix (unfoldr bump (1, k, k, 1, n−1)) (sy, ys))
Dart // op' を bump / unfoldr で直接展開したイーガー版 (ForestEager, ForestEager) opPrimeEager( int k, int n, (ForestEager, ForestEager) ysy, ) { final (ForestEager ys, ForestEager sy) = ysy; final List<int> dn = unfoldBump((-1, k, k, n - 1, 1)).toList(); if (n.isOdd) { final List<int> up = unfoldBump((1, 0, k, 1, n - 1)).toList(); return (mixEager(dn, (ys, sy)), mixEager(up, (sy, ys))); } else { final List<int> up = unfoldBump((1, k, k, 1, n - 1)).toList(); return (mixEager(dn, (ys, sy)), mixEager(up, (sy, ys))); } }

評価を遅延させる

しかしこれでも、op' (k, n) 自体が Θ(n) ステップなので、foldr op' は結局二乗時間になってしまいます。

アイデア unfoldr bump を op' の中で走らせずに、その仕事を後回し（遅延評価）にして、改造版の step にやらせる。要するに、mix の第1引数の評価を後回しにするのです。

そのために、遅延した評価を表す新しいデータ型を用意します。

type Forest a = Queue (Rose a) data Rose a = Node a (Forest a, Forest a)
Dart // 遅延評価版の新しい薔薇木 : 子が「森の対」になっている class Rose<A> { final A value; final (Forest<A>, Forest<A>) children; Rose(this.value, this.children); } // Forest<A> = Queue<Rose<A>> ； ここでは List で代用 typedef Forest<A> = List<Rose<A>>;

新しい薔薇木（rose tree）は、子として単一の森ではなく「森の対」を持つ点が違います。

新しい step と mix

type State = (Int, Int, Int, Int, Int) type Pair a = (a, a) step :: [Forest (Int, State)] → Maybe (Int, [Forest (Int, State)]) step [] = Nothing step (zs : zss) = Just (x, consQueue (mix q (sy, ys)) (consQueue zs' zss)) where (Node (x, q) (ys, sy), zs') = remove zs
Dart // State = 五つ組 ； Pair<A> = (A, A) typedef State = BumpState; // (int i, int j, int k, int m, int n) typedef Pair<A> = (A, A); // Node は (Int, State) を値に持つ Rose ； 森の要素も対 (ys, sy) typedef LForest = Forest<(int, State)>; typedef LRose = Rose<(int, State)>; // step : 森の列を1歩進める（遅延版） (int, List<LForest>)? step(List<LForest> zss) { if (zss.isEmpty) return null; final LForest zs = zss.first; final List<LForest> rest = zss.sublist(1); // remove zs : キュー先頭 Node (x, q) (ys, sy) と残り zs' を返す final LRose head = zs.first; final LForest zsPrime = zs.sublist(1); final (int x, State q) = head.value; final (LForest ys, LForest sy) = head.children; return (x, consQueueL(mix(q, (sy, ys)), consQueueL(zsPrime, rest))); } List<LForest> consQueueL(LForest xs, List<LForest> xss) => xs.isEmpty ? xss : <LForest>[xs, ...xss]; List<LForest> wrapQueueL(LForest xs) => consQueueL(xs, <LForest>[]);

mix はこう書き換えます。

mix :: State → Pair (Forest (Int, State)) → Forest (Int, State) mix (i, j, k, m, n) (ys, sy) = if i ∗ (n−m) < 0 then ys else insert ys (Node (m+j, (i, k−j, k, m+i, n)) (ys, sy))
Dart // mix : 遅延版。1 要素だけ Node を作って森 ys の末尾に append する LForest mix(State s, (LForest, LForest) ysy) { final (int i, int j, int k, int m, int n) = s; final (LForest ys, LForest sy) = ysy; if (i * (n - m) < 0) return ys; // 打ち止め final State next = (i, k - j, k, m + i, n); return <LRose>[...ys, LRose((m + j, next), (ys, sy))]; }

こうすると、step は次の遷移 x をひとつ生成して、状態 q（五つ組）を mix に渡します。mix はそこから次の遷移（あれば）と新しい状態を計算します。

最終形

jcode = unfoldr step · wrapQueue · fst · foldr op' (empty, empty) · pairs
Dart // jcode の最終形 : プロローグ Θ(n) + 各ステップ Θ(1) のループレス Iterable<int> jcodeLoopless(int n) sync* { // pairs n を線形時間で組み立てる final List<(int, int)> ps = addpair(0, n, <(int, int)>[]); // foldr op' (empty, empty) : 右から順に op' を畳み込む (LForest, LForest) acc = (<LRose>[], <LRose>[]); for (final (int, int) kn in ps.reversed) { acc = opPrime(kn.$1, kn.$2, acc); } // wrapQueue · fst List<LForest> zss = wrapQueueL(acc.$1); // unfoldr step while (true) { final (int, List<LForest>)? r = step(zss); if (r == null) return; yield r.$1; zss = r.$2; } }

op' は次のように書き直します。

op' :: (Int, Int) → Pair (Forest (Int, State)) → Pair (Forest (Int, State)) op' (k, n) (ys, sy) = if odd n then (mix (−1, k, k, n−1, 1) (ys, sy), mix (1, 0, k, 1, n−1) (sy, ys)) else (mix (−1, k, k, n−1, 1) (ys, sy), mix (1, k, k, 1, n−1) (sy, ys))
Dart // op' : 最終形。mix の第 1 引数を「状態」だけにして評価を遅延化 (LForest, LForest) opPrime(int k, int n, (LForest, LForest) ysy) { final (LForest ys, LForest sy) = ysy; final State dn = (-1, k, k, n - 1, 1); final State up = (1, n.isOdd ? 0 : k, k, 1, n - 1); return (mix(dn, (ys, sy)), mix(up, (sy, ys))); }

詳細は演習に譲りますが、これで長いプロローグ

prolog = wrapQueue · fst · foldr op' (empty, empty) · pairs

は n に対して Θ(n) ステップで済み、step は定数時間で動きます。

まとめ（本物のループレス） ようやく、jcode に対する純度 24 金の本物のループレス・プログラムができました。プロローグ Θ(n)、各ステップ Θ(1) の性能です。
Dart // 章全体の動作確認 : "abcd" の全 24 順列を隣接スワップで列挙する Iterable<List<T>> permutations<T>(List<T> xs) sync* { final List<T> cur = List<T>.of(xs); yield List<T>.of(cur); for (final int i in jcodeLoopless(cur.length)) { // 遷移 i : 位置 i と 位置 i-1 を入れ替える（順列だけ in-place） final T tmp = cur[i]; cur[i] = cur[i - 1]; cur[i - 1] = tmp; yield List<T>.of(cur); } } void main() { final List<String> seed = <String>['a', 'b', 'c', 'd']; for (final List<String> p in permutations<String>(seed)) { print(p.join()); } // 出力（最初の数個）: // abcd // abdc // adbc // dabc // dacb // adcb // acdb // acbd // ... 合計 24 通り // 素朴な再帰版と一致することも確認できる assert(jcode(4).join(',') == jcodeLoopless(4).toList().join(',')); }

結びの言葉

もし「プロローグは線形時間で」という細かい要件がなければ、実は次の定義に到達した時点で計算をやめてもよかったのです。

jcode = boxall · map bumpDn · pairs

この定義が本当に示しているのは、いろいろな組合せパターンを生成するときに、一般化された牛耕積 boxall がとても役に立つということです。次章（最終章）でもさらに活躍します。

歴史メモ ジョンソン–トロッター法は Johnson (1963) と Trotter (1962) が独立に発表しました。前章で触れた Ehrlich (1973) は「ループレス・アルゴリズム」という概念を導入した論文で、そこでは主にジョンソン–トロッター法のループレス実装を扱っていました。

参考文献

Ehrlich, G. (1973). Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. Journal of the ACM 20, 500–13.

Johnson, S. M. (1963). Generation of permutations by adjacent transpositions. Mathematics of Computation 17, 282–5.

Trotter, A. F. (1962). Perm (Algorithm 115). Communications of the ACM 5, 434–5.