ハミング距離とは，等しい文字数をもつ２つの文字列の中で，対応する位置にある異なった文字の個数である．たとえば，

　　１０１１１０１，１００１００１

の排他的論理和をとると

　　００１０１００

となり，ハミング距離は２となる．

　ハミング距離はｎ次元立方体の２つの頂点間のマンハッタン距離に相当するものであるから，２つの多面体，たとえば（０１０１１０）と（１０１００１）の間の自然な距離は，

　　正方格子のマンハッタン距離＋ｋ立方体のマンハッタン距離

で定義される．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】アルゴリズム

［０］ｗの左右を逆転させて，大きい方を改めてｗとおく．これで，左側の０マージンが右側の０マージンより小さくなる．

［１］ｗの最初の１と最後の１の位置を１ｓ，１ｅとし，その間を０に置換する．０がｋ個あるとする．

　　（０，・・，０，１s，０1，・・，０k，１e，０，・・，０）

［２］ｗ＝（０，・・，０，１s，＊，・・，＊，１e，０，・・，０）との排他的論理和をとると，ｋ立方体のマンハッタン距離（ｍ1）が得られる．

［３］次に，正方格子のマンハッタン距離であるが，

　　ｓ←ｓ＋１，ｅ←ｅ−１

とする．

ｋが偶数のとき，（０，・・，０，１，１r，０，・・，０）

ｋが奇数のとき，（０，・・，０，１r，０，０，・・，０）

になるまで繰り返す．

ｋが偶数のとき，ステップ数：ｓ1＝（ｋ−２）／２

ｋが奇数のとき，ステップ数：ｓ1＝（ｋ−１）／２

［４］（１，０，・・・，０）との間のステップ数は，

　　（０，・・，０，１，１r，０，・・，０）→ｓ2＝２ｒ−１

　　（０，・・，０，１r，０，０，・・，０）→ｓ2＝２ｒ−２

［５］正方格子のマンハッタン距離は

　　ｍ2＝ｓ1＋ｓ2

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝