『6枚のカードの並べ方を求めて！』「入れ替えの極み」コード解説

CodeIQ

はじめに

CodeIQで『6枚のカードの並べ方を求めて！』という問題が出題されました。

問題の内容を大雑把に言うと、

  • 0, 1, 2, 3, 4, 5 の 6 文字の順列 720 通りを漏れなく重複なく（順序は不問）出力する Java プログラムを作る。
  • 縛りとして、 ideone.com のテンプレートの main() メソッド内「// your code goes here」の部分のみを書き換えて作る。別メソッドやメンバ変数は使用禁止。匿名クラス等も使用禁止。テンプレートで import されているクラスは利用してよい。
  • “面白いロジックや「その手があったか！」なロジック”に対してバッジが付与される。

といったものです。

ideone.com のテンプレートは、次の通りです。

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	}
}

解説記事

出題者のチョコレートバー様による解説記事です。

https://codeiq.jp/magazine/2014/05/10469/

「入れ替えの極み」コード

解説記事の中で、私（tails）が提出したコードは「特殊な解き方」の「入れ替えの極み」として紹介され、バッジを頂きました。

String s="012345\n";
for(int i=1;i<=720;++i){
  System.out.print(s);
  int j=i,k=2;
  while(j%k==0) j/=k++;
  s = new StringBuffer(s.substring(0,k)).reverse() + s.substring(k);
}

解説記事の通り、先頭の k 文字を順序逆転させて出力することを繰り返すだけです。「シンプル」と評されているように、紹介されているコードの中では最も短いものとなっています。しかし、これで順列が漏れなく重複なく列挙されることは、一見しただけでは明らかではありません。そこで、なぜこのロジックで順列が列挙されるのか、そもそもどのようにしてこのロジックに至ったのか、説明したいと思います。

「入れ替えの極み」に至る道

順列を列挙するプログラムの実装としては、再帰を用いるのが最も素直です。しかし、この問題では、コードを main() メソッド内に収めなければならないため、関数の再帰呼出しは困難です。 main() メソッド自体を再帰呼出しするのは一応可能ですが、無理にそうせずとも、ループで実装できるのであれば、そのほうがシンプルです。そこで、ループで、文字列 "012345" の文字を順次入れ替えながら出力すること目指してみます。

作戦は、次の通りです。文字列 s の先頭の k 文字だけを入れ替えながら k! 通りを列挙する「手順(k)」を考えます。「手順(6)」が、最終的に作りたいコードです。そして「手順(1)」は 1 通りの列挙なので、単純に文字列 s を出力する処理です。

この「手順(k)」を、再帰のような（あるいは数学的帰納法のような）考え方で構成してみます。つまり、「手順(k-1)」を利用して「手順(k)」を作るのです。どうすればいいでしょうか？

「手順(k)」で列挙する文字列は k! 通りです。「手順(k-1)」で列挙するのは (k-1)! 通りですから、「手順(k)」は「手順(k-1)」の実行を k!/(k-1)! = k 回含むことになります。さらに、漏れなく重複なく列挙するためには、「手順(k-1)」を実行するときに、文字列 s の k 文字目以降の部分が毎回異なるようにしなければなりません。そのためには、「手順(k)」では、先頭の k 文字のそれぞれを1度ずつ k 文字目に入れ替えた状態で「手順(k-1)」を実行する必要があります。

具体的なイメージとして、例えば s="012345", k=3 の場合、次のような感じです。

手順(3) = {

   s の3文字目が "2" になるように入れ替え（s="012345"）
   手順(2)を実行
      → "012345", "102345" が出力される

   s の3文字目が "1" になるように入れ替え（s="201345"）
   手順(2)を実行
      → "201345", "021345" が出力される

   s の3文字目が "0" になるように入れ替え（s="120345"）
   手順(2)を実行
      → "120345", "210345" が出力される
}

もちろん、「手順(3)」が開始するときの s は "012345" になっているとは限りません。「手順(4)」で s の先頭4文字をいろいろ入れ替えつつ「手順(3)」を実行しますし、そもそもその「手順(4)」も s="012345" で開始するとは限らないからです。

さて、そうすると、「手順(k)」で s の先頭の k 文字のそれぞれを1度ずつ k 文字目に入れ替える処理は、具体的にどういう処理にすればいいのでしょうか？ いろいろなやり方が考えられますが、なるべくシンプルな方法を採用したいですね。

ここで、「手順(k-1)」を実行する前と後で s が変化しないと仮定してみましょう。この場合には、先頭の k 文字をローテートさせれば、 k 文字目を順番に入れ替えていくことが簡単に実現します。しかも、ローテートを k 回行った結果は、元の文字列に戻りますから、「手順(k)」でも実行の前後で s が変化しないことになります。

ローテートには右ローテートと左ローテートがあり、どちらでも良いのですが、ここでは右ローテートを採用してみます。つまり、 s の元々の k 番目の文字を先頭に移動し、元々の 1 ～ k-1 番目の文字を 2 ～ k 番目にずらす処理です。

先頭3文字の右ローテートの例

012345
  ↓
201345
  ↓
120345
  ↓
012345 … 元に戻った

さて、これで、「手順(k)」の具体的な構成ができました。

手順(k) = {
   k = 1 の場合、 s を出力する。
   k > 1 の場合、以下を k 回繰り返す。
      手順(k-1)を実行
      s の先頭 k 文字を右ローテート
}

これをJavaでループを用いて書くと、次のようになります。なお、このコードは、問題の有効な解答になっています（バッジがもらえるかどうかは判りませんが）。

String s="012345";
for(int i=1;i<=720;++i){
  System.out.println(s);
  if(i%(1)==0) s = s.substring(1,2) + s.substring(0,1) + s.substring(2);
  if(i%(1*2)==0) s = s.substring(2,3) + s.substring(0,2) + s.substring(3);
  if(i%(1*2*3)==0) s = s.substring(3,4) + s.substring(0,3) + s.substring(4);
  if(i%(1*2*3*4)==0) s = s.substring(4,5) + s.substring(0,4) + s.substring(5);
  if(i%(1*2*3*4*5)==0) s = s.substring(5,6) + s.substring(0,5) + s.substring(6);
}

このコードで例えば if(i%(1*2*3*4)==0) で始まる行は、「手順(5)」において5回実行される、「手順(4)」を呼出した後で s をローテートする処理のことで、ループ 4! 回ごとに 1 回実行されるべき処理です。

さて、これで解答のコードが作れましたが、ここからロジックは変えずに少しだけ変形を施したものが、前出の「入れ替えの極み」コードです。ロジックが同じなので、当然、出力順も同じです。ここから少しだけの変形で、本当にあのような reverse() 一発のコードになるのでしょうか？

上のコードをよく見てみましょう。 substring() を使って書かれているので多少わかりにくいですが、各行は、 s の先頭 k 文字の右ローテートです。ここで、if の条件式から明らかなように、6文字のローテートの直前には必ず5文字のローテートが行われます。その5文字のローテートの直前は必ず4文字のローテートです。つまり、 k 文字のローテートが行われる場合には、必ず 2 ～ k 文字のローテートが順に行われることになります。さて、2 ～ k 文字のローテートが順に行われると、どのような結果になるでしょうか…？ そうです！ 先頭の k 文字の順序が逆転するのです！

そこで、上のコードは、次のように変形することができます。もちろん、このコードも有効な解答です。

String s="012345";
for(int i=1;i<=720;++i){
  System.out.println(s);
  if(i%(1*2*3*4*5)==0) s = new StringBuffer(s.substring(0,6)).reverse() + s.substring(6);
  else if(i%(1*2*3*4)==0) s = new StringBuffer(s.substring(0,5)).reverse() + s.substring(5);
  else if(i%(1*2*3)==0) s = new StringBuffer(s.substring(0,4)).reverse() + s.substring(4);
  else if(i%(1*2)==0) s = new StringBuffer(s.substring(0,3)).reverse() + s.substring(3);
  else if(i%(1)==0) s = new StringBuffer(s.substring(0,2)).reverse() + s.substring(2);
}

条件分岐している所をパラメータ化して、「入れ替えの極み」コードの完成です。

String s="012345\n";
for(int i=1;i<=720;++i){
  System.out.print(s);
  int j=i,k=2;
  while(j%k==0) j/=k++;
  s = new StringBuffer(s.substring(0,k)).reverse() + s.substring(k);
}

めでたし、めでたし！

なお、パラメータ化により、 i = 720 の場合に k = 7 となり、本来存在しない「手順(7)」相当の処理が行われてしまいます。このとき、6文字しかない文字列の7文字目をアクセスしようとしてエラーになります。そこで、最初に s="012345\n" と改行コードを入れて7文字にすることによって、エラーを回避しています。これに伴い、 println(s) も print(s) に変更しています。

別の解法：コードをプログラムで生成

じつは、 main() の中だけで完結させるという縛り条件を読んだときに真っ先に思い付いた解法は、「別のプログラムで println() を720個作って並べる」というものでした。これなら再帰でも何でも自由にできますし、そもそも慣れない Java で書く必要さえありません。しかし、それはあんまりなので、思いとどまりました。

おわりに ～ さらなる極みを目指して

「入れ替えの極み」コードに対して出題者様から頂いたフィードバック（爆速で驚きました）に、このようなことが書かれていました。

入れ替え法は一般には２値入れ替えを使うのですが

締め切り後に出題者様に聞いてみたところ、要するに、2文字を入れ替えながら再帰していく（再帰から戻ったら文字も元に戻す）ような、考えてみればごく普通の処理のことでした。

しかし、当時ふと疑問に思ったのは、わざわざ reverse() などせずに、2文字を入れ替えて出力することを720回繰り返すだけの簡潔な方法があるのだろうか？ ということです。別の言い方をすれば、出力順で隣り合う2つの文字列のハミング距離がいずれも2になるような方法があるだろうか？ ということです。

「簡潔な」という条件を除けば、そのような方法が存在すること自体は明らかです。上の「入れ替えの極み」コードの説明で先頭 k 文字のローテートをしていた所を、 k 番目の文字と x (<k) 番目の文字を入れ替えるように変更すればいいからです（あと、各「手順(k)」における最後の1回の入れ替え処理を省く必要があります）。しかし、 x を適切に選ぶことは、さほど簡潔にはできないようです。というのも、このやり方だと、「手順(k-1)」の実行の前後で s が変化してしまうからです。