順列の列挙の方法

質問

順列の列挙の方法といっても辞書式順序のやつではありません。別の制約です。
グレイコードというのをご存知でしょうか。例えばビット列のグレイコードは次のようになります。

0:000
1:001
2:011
3:010
4:110
5:111
6:101
7:100

これがどんな制約を満たしているかと言うと、

1、となりのビット列に変換するには1ビット反転すれば良い。
2、すべてのビット列がちょうど1回現れる。

この2つです。グレイコードの正確な定義はさておき、とりあえず今はこれと言うことにします。

この順序でビット列を列挙する関数をC言語で書くと次のような感じになります。
f(int n)
{
if(n==-1)return;
f(n-1);
第nビットを反転；
出力；
f(n-1);
}

さて順列の話ですが、次のような制約を満たす順序で順列を列挙するアルゴリズムは
どんな感じになるのでしょうか。

1、となりの順列に変換するには1回スワップ(2つの要素を入れ換える)すれば良い。
2、すべての順列がちょうど1回現れる。

この条件を満たすような順列の列はたくさんあると思いますが、
できるだけ法則性のあるやつ、というかプログラムに書きやすいやつを
お願いします。

ビット列のアルゴリズムをちょこっと変えれば出来るかなーと思っていたのですが
数学的センスが無いせいか、苦戦しています。数学的センスのある方、ぜひご教示ねがいます。

回答No.7

stomachman · ベストアンサー

巡回セールスマン問題では、任意の２つのノード間を移動して良い。（数学では「完全グラフ」と言います。）ですから、「最短経路」という条件が無ければ、とにかくこれまで通っていないノードをどれでも良いから通り、最後に出発点に戻ればハミルトン閉路になります。アホみたいに簡単。

ご質問の問題では、ノード間で移動できるものが限られている。これが制約なので、全然性質の違う問題です。

さて、回答。

文字数をnとします。n=2とn=3の時はちょっと例外的な扱いになります。
●n=2:ab
abの２文字からなる場合を考えましょう。互換は{1,2}しかありません。そして
ab{1,2}=ba, ba{1,2}=ab
で元に戻るループができます。これがハミルトン閉路。これを略して
ab{1,2}ba{1,2}ab
あるいはさらに手抜きして
{1,2}{1,2}
と書くことにします。
互換を{}の集合の記号で書くのは
{x,y}={y,x}
だからです。{}内に入れる数の順序は関係ない。またx=yであってはならない。だから要素を２個含む集合として表すとちょうど良い、というだけのことです。原則として{x,y}はx＜yとなるように書くことにしましょう。
さて、ハミルトン閉路
{1,2}{1,2}
において、出発点がabであってもbaであっても、いやそれどころかazであっても同じ事です。これは重要な点です。
●n=3:abc
abcの３文字からなる場合。この互換は{1,2}, {1,3}, {2,3}があります。ここで、
同じ互換pを二つ並べるとn≧3では必ず失敗する。p={1,2}なら
ppつまり{1,2}{1,2}
で閉路ができてしまい、全部の順列を網羅しません。
さて、同じ互換を続けて繰り返さない、というルールさえ守れば、どれでも良いというわけじゃありませんよ。閉路として、最後に元に戻ることを要求する。するとハミルトン閉路は
(1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
(2) {1,2}{2,3}{1,2}{2,3}{1,2}{2,3}
(3) {1,2}{2,3}{1,3}{1,2}{2,3}{1,3}
(4) {1,3}{2,3}{1,2}{1,3}{2,3}{1,2}
(5) {1,3}{2,3}{1,3}{2,3}{1,3}{2,3}
(6) {1,3}{1,2}{1,3}{1,2}{1,3}{1,2}
(7) {2,3}{1,2}{2,3}{1,2}{2,3}{1,2}
(8) {2,3}{1,3}{1,2}{2,3}{1,3}{1,2}
(9) {2,3}{1,2}{1,3}{2,3}{1,2}{1,3}
とこれだけあります。
しかしよく見ると、
(3)と(4)は逆順になっているだけ。つまり逆回り。
(1)と(6), (5)と(8), (3)と(9)と(5)はループの出発点がずれているだけ。
こういうものは同じ閉路と考えて構わないでしょう。だから、本質的に違うのは
(1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
(2) {1,2}{2,3}{1,2}{2,3}{1,2}{2,3}
(3) {1,2}{2,3}{1,3}{1,2}{2,3}{1,3}
(5) {1,3}{2,3}{1,3}{2,3}{1,3}{2,3}
この４つだけです。
この中で、３種類の互換が全部出てくるのは(3)だけです。
後で説明する理由により、可能な互換が全部出てくるのは望ましい性質なんです。
一方で、(1)(2)(5)は{1,2}が交互に現れてますね。つまり、３文字目を変えないで{1,2}の互換をやる。そして、３文字目を変更する。この繰り返しをやっている。たとえば、
(1) abc{1,2}bac{1,3}cab{1,2}acb{1,3}bca{1,2}cba{1,3}abc
という訳です。３文字目がcの場合をまず尽くし、次にbの場合、次にaの場合、という風になっている。これもまた、大変結構な性質である。で、この後で出てくる理屈によれば、(1)を採用するのが話が綺麗になります。（いや、(1)～(9)のどれを使っても、勿論構わないし、それなりにやりようはあるんですがね。）
でも、
(3-1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
これに決めちゃいます。

●n=4:abcd
まともに数え上げると大変な数のハミルトン閉路が存在します。しかし、
4文字目がdの場合の順列(3!通り)をまず尽くし、次に４文字目がcの場合、....という風にやることにします。
しかも次の形に決めてしまう。
(4-1) [1,2]{3,4}[1,3]{3,4}[1,3]{2,4}[1,3]{1,4}
　さて、ここで新しい記号[x,y]を導入しました。これは何かと言いますと、今n=4を検討している訳ですけど、「n=3のハミルトン閉路を一カ所切ったもの」をここに嵌め込む、ということを示している。どういうことかと言いますと、[1,2]というのはn=3におけるハミルトン閉路
(3-1) {1,2}{1,3}{1,2}{1,3}{1,2}{1,3}
のうち、{1,2}を一つ切り取ってひもを作れ、という命令を意味しているんです。この場合、３つある{1,2}のどれでも良いですから除いて、ループを「ひも」に変換しますと3!-1の長さの互換の列
[1,2]＝{1,3}{1,2}{1,3}{1,2}{1,3}
ができる。これを嵌め込むんです。同様に[1,3]というのは
[1,3]={1,2}{1,3}{1,2}{1,3}{1,2}
を嵌め込むことを示しています。本当に嵌め込んでみると
(4-1) {1,3}{1,2}{1,3}{1,2}{1,3}{3,4}{1,2}{1,3}{1,2}{1,3}{1,2}{3,4}{1,2}{1,3}{1,2}{1,3}{1,2}{2,4}{1,2}{1,3}{1,2}{1,3}{1,2}{1,4}
ということになります。[]の記法によって、長さn!の互換の列を2n個の記号で表現できるのでとても便利なのです。
(4-1)がハミルトン閉路になっていることはご自分で確かめて戴くとして、ここで重要なのは
「[1,2]や[1,3]の部分では4文字目は変化しない。」ということ。ですから、
(4-1) [1,2]{3,4}[1,3]{3,4}[1,3]{2,4}[1,3]{1,4}
の最初の[1,2]では4文字目がdに固定、次の[1,3]では４文字目がcに固定。次の[1,3]では４文字目がbに固定、最後の[1,3]では４文字目がaに固定されています。このようにして、当初の方針が実現されている。さらに、
・(4-1)の閉路には{x,4}の形の互換の可能な3通りが（{1,4}, {2,4}, {3,4}）全部現れている。
これが重要なポイントになります。
●n=5:abcde
これも5文字目がeの場合の順列(3!通り)をまず尽くし、次に....という風にやります。いろんなハミルトン閉路のうちから、
(5-1) [1,2]{4,5}[3,4]{4,5}[1,3]{3,5}[1,3]{2,5}[1,3]{1,5}
に限ってしまいましょう。[]で表されるひもとしては、
[1,2], [3,4],[1,3]
が使われています。（これらはn=4におけるハミルトン閉路から作るひも（4!-1個の互換からなる）であって、n=3でのひもじゃないですからご注意下さい。）これらのひも[x,y]は常に作れます。なぜなら{x,y}が(4-1)には必ず含まれていますから、その部分でチョン切ってひもを作ることができます。
さて実は、[x,4]という形のひもを使うときにxに何を持ってきてもn=4におけるハミルトン閉路に含まれているようにするために、n=4の場合に「・(4-1)の閉路には{x,4}の形の互換の可能な3通りが（{1,4}, {2,4}, {3,4}）全部現れている。」という性質を要求したんです。
こうやって作ったn=5のハミルトン閉路もまた、
・(5-1)の閉路には{x,5}の形の互換の可能な4通りが全部現れている。
という性質を満たしています。
●n≧4
たとえばn=8ではどうでしょう。
(8-1) [1,2]{7,8}[6,7]{7,8}[5,6]{6,8}[4,5]{5,8}[3,4]{4,8}[1,3]{3,8}[1,3]{2,8}[1,3]{1,8}
これがハミルトン閉路のひとつです。（[]はn=7におけるひもを表しています。）もう規則性はお分かりでしょう。
[1,2]{7,8}　：[1,2] 　　{n-1,n} ... 最初はこれに決まり。
[6,7]{7,8}　：[n-2,n-1] {n-1,n}　... {n-1,n}がもう一回出てきます。ここからは規則的。
[5,6]{6,8}　：[n-3,n-2] {n-2,n}
[4,5]{5,8}　：[n-4,n-3] {n-3,n}
[3,4]{4,8}　：[n-5,n-4] {n-4,n}
[1,3]{3,8}　：[1,3] {3,n} .... ここから[ ]の方が変則的になります。
[1,3]{2,8}　：[1,3] {2,n}
[1,3]{1,8}　：[1,3] {1,n}
ここで、[2,3]は一度も必要とされてません。ですから、n=3のときに{2,3}を含まないハミルトン閉路を採用しちゃっても構わなかった訳です。
・(8-1)の閉路には{x,8}の形の互換の可能な7通りが全部現れている。
という性質もちゃんと満たしています。

n=10でやってみると、
[1,2]{9,10}[8,9]{9,10}[7,8]{8,10}[6,7]{7,10}[5,6]{6,10}[4,5]{5,10}[3,4]{4,10}[1,3]{3,10}[1,3]{2,10}[1,3]{1,10}
これも同じ規則でできていることがわかりますね。どのように順列が変化していくかというと、
abcdefghij
[1,2]bacdefghij
{9,10}bacdefghji
[8,9]bacdefgjhi
{9,10}bacdefgjih
[7,8]bacdefjgih
{8,10}bacdefjhig
[6,7]bacdejfhig
{7,10}bacdejghif
[5,6]bacdjeghif
{6,10}bacdjfghie
[4,5]bacjdfghie
{5,10}bacjefghid
[3,4]bajcefghid
{4,10}bajdefghic
[1,3]jabdefghic
{3,10}jacdefghib
[1,3]cajdefghib
{2,10}cbjdefghia
[1,3]jbcdefghia
{1,10}abcdefghij
こうなります。
勿論、出発点がabcdefghijでなくても、任意の順列から出発して構わない訳です。

以上、
・互換だけによって、
・探索（trial and errorによる後戻り）なしに、
・n文字からなる順列を全部ちょうど１回づつ発生させ、
・しかも最後に元に戻ってくる
というハミルトン閉路生成システムが一つ構成できました。（無論、他にも解はいろいろあり得ます。）

これをどうプログラムするか、についてはお任せいたしましょう。

お礼

回答ありがとうございます。

はじめて回答を見たときはあまりの量の多さにビックリ仰天してしまいました。
しかし読んでみると具体例を用いた手とり足とりの詳しい解説で,苦もなく
(ホントはちょっと苦労しました)読めました。
プログラムの方も何とか書けそうです。

>さて、ここで新しい記号[x,y]を導入しました。これは何かと言いますと、
>今n=4を検討している訳ですけど、「n=3のハミルトン閉路を一カ所切った
>もの」をここに嵌め込む、ということを示している。

最初はエッずいぶんトリッキーなことをするなあと、思ったのですが
読んでいく内に,いやいやこれは結構自然な記号の導入なのかもと思ったり。
いろいろ感心させられました。

数学的センスのある方、御教示おねがいします。といって質問したわけですが、
僕が期待していた以上のセンスの持ち主の目に止まったようで,有難いです。

親切な回答ありがとうございました。

回答No.6

stomachman

既に答を得ているんですが、説明をまとめる時間がとれません。もうちょっと待ってね。プログラムを書いた方が早いかも知れないけど、それじゃ考え方や面白みが伝わらない。

　なお、巡回セールスマン問題は、「最短経路を求めよ」という条件があるからNP完全になるんであって、単にハミルトン閉路を求めるのはそんなに難しい問題じゃありません。

回答No.5

stomachman

スワップというのは数学では「互換」と言います。
並べ方全部をノードにし、互換で移れるノード同士を線で結ぶと複雑なグラフが出来ます。（３文字なら６角形を描いて、あと、対角線３本を加えた形になります。）このグラフ上で、全部のノードを１度づつ通るループ（「ハミルトン閉路」と言います）をさがせ、という問題です。列の文字数が多いほど自由度が高く、ハミルトン閉路が沢山存在します。

アルゴリズムがかんたんであること、という条件付きですが、この最後の条件はちょっと堪忍して。なるべくシステマティックな方法を考察中ですんで、もうちょっと開けといて下さい。

お礼

回答ありがとうございます。
ハミルトン閉路ですか。巡回セールスマン問題に出て来るやつですね。
NP完全問題でとても難しいらしい,ということは知ってます。

回答No.4

noname#16572

再び、やってきました。まずおわびです。私Cが全く読めないんでグレイコードの列挙が問題に既に書いてあることすら気がつきませんでした。
で、問題を次の様に書きかえました。

『nヶの異なる「文字」を並べたものを順序を含めて「順列」とする。「順列」内の任意の２文字を置換して得られる「順列」を「隣接している」とする。問題は、ある「順列」から出発して「隣接する順列」を並べていき、全ての順列を一回だけ使用した「順列」列を作れ。ただし、最後の「順列」は最初の「順列」と「隣接」していなければならない。』

でよろしいでしょうか？用語は適当に定義しました。
私は今はちょっと答えが思いつかないです。線形代数からしてすっかり忘れているし。予想では最後の条件が難しいような気がします。
どなたかフォローお願いします。

回答No.3

noname#16572

更に追加です。
問題を取り違えたのかな？てっきりグレイコード自身を生成するのだと思ってました。
条件１の1回スワップを満たす場合、3ビットの例でいうと111からスタートしたらどこにも行かないですよね。で、２のすべての順列が現れると言うのはちと無理な気がします。私、どこかで誤解していますか？

お礼

回答ありがとうございます。
始めに辞書式順序ではない、と言ってしまったので誤解を招き易かったかも
しれません。並べるもの自体はいわゆる順列なんですがその並べ方が辞書式
ではなくグレイコードに似ていると言うことなんです。

補足

僕が言いたかった順列とは a,b,cを並べて出来る列を作れ、といわれたら
abc
acb
bac
bca
cab
cba
と言う、例のアレです。
例えば3文字の場合
0:abc (5のabを入れ換えた)
1:acb (0のbcを入れ換えた)
2:bca (1のabを入れ換えた)
3:cba (2のbcを入れ換えた)
4:cab (3のabを入れ換えた)
5:bac (4のbcを入れ換えた)
とすれば条件にあいます。
アレッ、今書いてて気づいたんですがずいぶん綺麗に行きますね。
うーん,イメージの湧かない一般的な問題を考えるときはまず分かりやすい具体例で、
というのは数学テクニックの基本ですよね。そんなこともうっかり忘れてました。
僕ももうちょっと頑張ってみます。

回答No.2

noname#16572

#1修正です。
3bitの列は
111,110,100,101/001,000,010,011で5番目が間違ってました。
従って4bitの方も違っていて、
1111,1110,1100,1101/1001,1000,1010,1011//
0011,0010,0000,0001/0101,0100,0110,0111
です。
今度はあっていると思います。(多分）
一般のn bitへの拡張も同様に考えれば可能です。生成ルールからハミング距離=1は満たされているはずです。
（プログラムしやすいかは良くわからないです）
もうちょっとちゃんと書けと言うのは今はご勘弁を。。。。

回答No.1

noname#16572

nビットのコードなら2^n個を生成しなければなりませんね。
1ビットの場合を考えます。
1,0ですね。これを2ビットに拡大するため、1ビットの列を反転したものを考えます。1,0,0,1です。これに先頭から2つずつに切って1,1,0,0を付加します。
11,10,00,01がえられます。
3ビットに拡大する場合も同様に2ビットの列を正順,逆順に並べます。
11,10,00,01,01,00,10.11になります。これに頭から半分ずつ1,0を付加すれば
111,110,100,101,010,000,010,011となってうまく行きます。
アルゴリズムをうまく口で説明できないのですが、4ビットの場合下から3ビット
を正順、逆順にならべると
1111,1110,1100,1101,1010,1000,1010,1011,
0111,01110,0100,0101,0110,0000,0010,0011
でうまくいってそうです。
参考になりましたでしょうか？