アルゴリズムです！四つの数字の順列

こんにちは！

学校のJavaの例題で、四つの重複しないマークの順列を全て書き出す
メソッドを作るっていう問題が出ました！

ネットを見ながらで、何とか再起を使って吐き出すのは組めたんですけど、
先生に見せたら、『まだ再起は教えていない』って言われて、合っているのに
NGを食いました＞＜

どうやら、for文の入れ子と配列の要素の入れ替えだけでできるらしいんですが、
どうやって書けばいいのかが解りません…。

パターンの数を出すのは解るんです。4*3*2ですしね。でも、再起を
使っている例をとっても、どうしてこのソースですべての順列が出せるのか、
その仕組みが解りません。

ソースだけじゃなくて、どうして全部の順列が出せるのか、その仕組みも併せて
教えてください!!

中身は、こんな感じです。

// 順列を出す配列
private int[] arr={0,1,2,3};

private void permutation(int n)
{
if (n < 4)
{
// n以上4未満
for (int i = n; i < 4; i++)
{
if (n != i)
{
this.swap(n, i);
}

// 再起呼び出し
permutation(n + 1);

if (n != i)
{
this.swap(n, i);
}
}
}
else
{
System.out.println(this.arr[0] + "," + this.arr[1] + "," + this.arr[2] + "," + this.arr[3]);
}
}

private void swap(int a,int b)
{
int c = this.arr[a];
this.arr[a] = this.arr[b];
this.arr[b] = c;
}

何もわからなくてゴメンナサイ。

よろしくお願いします^^

No.4 回答者： tatsu99 回答日時： 2016/07/01 13:00

以下のようにしてください。

------------------------------------------------
// 順列を出す配列
private char[] arr={'A','B','C','D'};

private void permutation(int n)
{
for (int i = 0; i < 4; i++)
{
if (i != 0)
{
this.swap(0,i);
}
for (int j = 1; j < 4; j++)
{
if (j != 1)
{
this.swap(1,j);
}
for (int k = 2; k < 4; k++)
{
if (k != 2)
{
this.swap(2,k);
}
System.out.println(this.arr[0] + "," + this.arr[1] + "," + this.arr[2] + "," + this.arr[3]);
if (k != 2)
{
this.swap(2,k);
}
}
if (j != 1)
{
this.swap(1,j);
}
}
if (i != 0)
{
this.swap(0,i);
}
}
}

private void swap(int a,int b)
{
char c = this.arr[a];
this.arr[a] = this.arr[b];
this.arr[b] = c;
}
---------------------------------------------------------------
これは、再帰を使用しない方法です。
以下、実行結果です。
A,B,C,D
A,B,D,C
A,C,B,D
A,C,D,B
A,D,C,B
A,D,B,C
B,A,C,D
B,A,D,C
B,C,A,D
B,C,D,A
B,D,C,A
B,D,A,C
C,B,A,D
C,B,D,A
C,A,B,D
C,A,D,B
C,D,A,B
C,D,B,A
D,B,C,A
D,B,A,C
D,C,B,A
D,C,A,B
D,A,C,B
D,A,B,C

今回、判り易くするために、A,B,C,Dの文字を使用していますが、0,1,2,3を
使いたいのであれば、
private char[] arr={'A','B','C','D'};　を
private int[] arr={0,1,2,3};　に戻します。
更に void swapメソッド中の
char c = this.arr[a];　を
int c = this.arr[a];　に戻します。
そうすれば、あなたが提示したソースと同じ結果が得られます。

それで、何故、上記の結果が得られるかということですが、以下のようになります。
１．A,B,C,Dの文字を出力するとき、1番目の文字を選ぶ。
これは、for(int i=0;i < 4;i++)のループです。
これは、i=0の場合は、そのままで良いが、以外の場合は、最初の文字とその処理中の文字を入れ変える必要があります。
つまり、Bの文字を処理するときは、A,B,C,DをB,A,C,Dのように置き換えます。
同様に、Cの文字を処理するときは、A,B,C,DをC,B,A,Dのように置き換えます。
同様に、Dの文字を処理するときは、A,B,C,DをD,B,C,Aのように置き換えます。
そして、ループの最後で、置き換えた文字を元に戻しておきます。

２．A,B,C,Dの文字を出力するとき、2番目の文字を選ぶ。
これは、for(int j=0;j < 4;j++)のループです。
これは、j=1の場合は、そのままで良いが、以外の場合は、２番目の文字とその処理中の文字を入れ変える必要があります。
つまり、Cの文字を処理するときは、A,B,C,DをA,C,B,Dのように置き換えます。
同様に、Dの文字を処理するときは、A,B,C,DをA,D,C,Bのように置き換えます。
そして、ループの最後で、置き換えた文字を元に戻しておきます。

３．A,B,C,Dの文字を出力するとき、３番目の文字を選ぶ。
これは、for(int k=2;k < 4;j++)のループです。
これは、k=2の場合は、そのままで良いが、以外の場合は、３番目の文字とその処理中の文字を入れ変える必要があります。
つまり、Dの文字を処理するときは、A,B,C,DをA,B,D,Cのように置き換えます。
そして、ループの最後で、置き換えた文字を元に戻しておきます。

４．ここは、arrの並べ替えた文字を印字する箇所です。
System.out.println（・・・省略・・・）

不明点があれば、補足してください。

この回答へのお礼

ありがとうございます！

少しわかりました！

つまり、一つのループごとにループの初めの数とループしている数を入れ替える
わけですね！
入れ替えというから、二重にループさせてそのiとjを入れ替えるのだとばかり
思っていました！

あと、どうして入れ替えた後で一度戻しているのか、
勿論、一つ一つ指でなぞりながらでもおっていけばその通りには
なるんですけど、なんか戻していたら、一行おきにもとの並び方に
戻ってしまいそうな気がします。
なので、コードはやってることは解るんですけど、『良くバラバラに
順列ができるなぁ』と思ってしまうわけです。

いくらサンプル通りに組んでうまくいっても、『どうしてそうなるのか』が
解らないと気持ち悪いですよね。

ありがとうございました！いただいたコードをもとに、もう一度試してみます！

お礼日時：2016/07/01 17:17

No.3 回答者： siffon9 回答日時： 2016/07/01 11:58

> 解らない人に教えるわけですから、自分が解っているからって

> いい加減な回答はしないでくださいね^^

再帰をご理解いただいているようなのでご理解いただけると判断したのですが
質問者様の理解力を見誤ったようで失礼しました。


閑話休題


要素が数字だと紛らわしいので文字にします。
arr={"A","B","C","D"};

4重ループで得られた数字が、外側のループから順に2,3,1,0だとすると
この要素番号で順にaryから要素を取り出して順に並べます。

arr1[0] = arr[2];
arr1[1] = arr[3];
arr1[2] = arr[1];
arr1[3] = arr[0];

結果としてarr1 = {"C","D","B","A"}になります。
これを4重ループで得られる重複しない組み合わせで実行すれば良いわけです。


これでご理解いただけましたでしょうか？

この回答へのお礼

…多分、私と同じ人もこれを見ただけじゃ解らないと思いますよ。
＞4重ループで得られた数字が、外側のループから順に2,3,1,0だとすると
＞この要素番号で順にaryから要素を取り出して順に並べます。
これだと、実際に『入れ替え』をやっていないし。
ソースにもswapって書いてあるわけですし、自分勝手な解釈で答えられても…
ねぇ？って思います。
siffon9さんは、多分『人に何かを教える』のは苦手なのではないでしょうか。

お礼日時：2016/07/01 16:03

No.2 回答者： siffon9 回答日時： 2016/06/30 15:43

> それだと要素の入れ替えをやってないですよね。

4重ループで得られた数字をarr要素番号にして、その順番でarrの要素を並べかえれば良いのでは？

この回答へのお礼

4重ループってことは、要素番号も四つあることになりますけど、それを
どうやって並び替えるんですか？
そこまで書いてくれないと、何が何だかわかりません^^

解らない人に教えるわけですから、自分が解っているからって
いい加減な回答はしないでくださいね^^

お礼日時：2016/07/01 11:21

No.1 回答者： Tacosan 回答日時： 2016/06/30 15:20

「四つの重複しないマークの順列を全て書き出す」っていうだけなら, 単純に 4重ループを組めば終わりでしょ?

この回答へのお礼

でも、それだと要素の入れ替えをやってないですよね。
もとの配列を入れ替えたりするらしいんですけど…

お礼日時：2016/06/30 15:29