C言語再帰アルゴリズム

再帰プログラミングの勉強中です。以下のコードは
123
132
213
231
321
312
のように正しく順列を生成するのですが、私の脳内解釈では最後の2つ
321
312
になることがわかりません。312 が2度表示されてしまいます。解釈のどこがおかしいのでしょうか？

#include <stdio.h>

#define N 3 //perm(N-1) で順列が表示される。

int p[N];

void perm(int);

void main(void)
{
　　for (int i = 0;i < N;i++)　　//初期設定
　　　　p[i] = i+1;
　　perm(0);
}

void swap(int *a, int *b)
{
　　int tmp;
　　tmp = *a;　　*a = *b;　　*b = tmp;
}

void perm(int i)
{
　　int j;
　　printf("perm(%d) →　p[%d] = %d\n",i , i, p[i]); //for debug
　　
　　if (i < N-1)
　　{
　　　　for (j = i;j < N; j++) //Loop
　　　　{
　　　　　　swap(&p[i],&p[j]); // swap1
　　　　　　perm(i+1);　　　　 // 再帰呼び出し
　　　　　　swap(&p[i],&p[j]); // swap2（元に戻す）
　　　　}
　　}
　　else //(i == N-1)
　　{
　　　　for (j = 0;j < N;j++)
　　　　　　printf("%d",p[j]);
　　　　printf("\n");
　　}
}

私の脳内解釈(長文ですみません)
(0)p[0]=1, p[1]=2, p[2]=3 初期値
(1)main() で perm(0) を呼び、その Loop において i=j=0 で Swap1 を実行する。p[] に変化なし。
(2)perm(1) を呼び、その Loop において i=j=1 で Swap1 を実行する。p[] に変化なし。
p[0]=1, p[1]=2, p[2]=3 （123）
の状態で perm(2) を呼ぶ。
(3)perm(2) では必ず B-Loop が実行され、123 が表示される。
(4)(2)の perm(1) に戻り i=j=1 で Swap2 を実行する。最初の Loop だから p[] に変化なし。
　次の Loop で i=1、j=2 となるから Swap1 を実行する。
p[0]=1, p[1]=3, p[2]=2 （132）
となるので perm(i+1)=perm(2) をんで132 が表示される。
(5)(4)の perm(1) に戻り Swap2 を実行する。i=1、j=2 なので、
p[0]=1, p[1]=2, p[2]=3 （123）
となるが、次の Loop で j>2 となるので Loop を抜けて(1)の perm(0) に戻る。よって(2)に続いて123 が表示されることはない。
(6)(1)の perm(0) で Swap2 を実行する。i=j=0 だから p[] に変化なし。
　次の Loop で i=0、j=1 となるから、Swap1 を実行する。
p[0]=2, p[1]=1, p[2]=3 （213）
として perm(i+1)=perm(1) を呼ぶ。
(7)perm(1) で Swap1 を実行する。最初の Loop は i=j=1 だから p[] に変化なし。
　そのまま perm(i+1)=perm(2) を呼ぶと 213 が表示される。
(8)(7)の perm(1) に戻り Swap2 を実行する。i=j=1 だから p[] に変化なし。
　次の Loop で i=1、j=2 なので、Swap1 を実行する。
p[0]=2, p[1]=3, p[2]=1 （231）
となるから perm(i+1)=perm(2) を呼ぶと 231 が表示される。
(9)perm(1) に戻り i=1、j=2 で Swap2 を実行する。
p[0]=2, p[1]=1, p[2]=3 （213）
となるが、次の Loop で j>2 なので Loop を抜けて(6)の perm(0) に戻る。したがって 213 が表示されることはない。
(10)(6)の perm(0) で Swap2 を実行する。i=0、j=1 だから
p[0]=1, p[1]=2, p[2]=3 （123）
　次の Loop で i=0、j=2 となる。Swap1 を実行すると
p[0]=3, p[1]=2, p[2]=1 （321）
となるから perm(i+1)=perm(1) を呼ぶ。
(11)perm(1) で Swap1 を実行する。最初の Loop は i=j=1 だから p[] に変化なし。
　次の Loop で i=1、j=2 となる。Swap1 を実行すると
p[0]=3, p[1]=1, p[2]=2 （312）
そのまま perm(i+1)=perm(2)を呼ぶと312が表示される。
(12)(11)の perm(1) に戻り Swap2 を実行する。i=1、j=2 だから
p[0]=3, p[1]=2, p[2]=1 （321）
　次の Loop で i=1、j=2 なので、Swap1 を実行する。
p[0]=2, p[1]=3, p[2]=1 （312）
　perm(i+1)=perm(2) を呼ぶと312 が表示される。
(13)(12)の perm(1) に戻る。次の Loop で j>3 なので Loop を抜けて(10)まで戻り、(1)の perm(0) で Swap2 を実行する。i=1、j=2 だから
p[0]=3, p[1]=2, p[2]=1 （321）
となるが、次の Loop では j>3 となり、Loop を抜けて main() に戻るので 321 は表示されない。

No.2 ベストアンサー 回答者： Ogre7077 回答日時： 2021/12/22 01:19

ご質問の(11)には i=j=1 で perm(2) を呼ぶ処理が抜けています。

他にも怪しい記述がちらほらと。

デバッグで i,j,p の中身を表示させれば、処理を理解しやすくなります。
(デバッグ表示例)
perm(0): i=0, j=0, p=[1,2,3] ← perm(1) を呼ぶ
perm(1): i=1, j=1, p=[1,2,3] ← perm(2) を呼び 123 表示
perm(1): i=1, j=2, p=[1,3,2] ← perm(2) を呼び 132 表示
perm(1): i=1, j=3, p=[1,2,3] ← Loop 終了
perm(0): i=0, j=1, p=[2,1,3] ← perm(1) を呼ぶ
perm(1): i=1, j=1, p=[2,1,3] ← perm(2) を呼び 213 表示
perm(1): i=1, j=2, p=[2,3,1] ← perm(2) を呼び 231 表示
perm(1): i=1, j=3, p=[2,1,3] ← Loop 終了
perm(0): i=0, j=2, p=[3,2,1] ← perm(1) を呼ぶ
perm(1): i=1, j=1, p=[3,2,1] ← perm(2) を呼び 321 表示
perm(1): i=1, j=2, p=[3,1,2] ← perm(2) を呼び 312 表示
perm(1): i=1, j=3, p=[3,2,1] ← Loop 終了
perm(0): i=0, j=3, p=[1,2,3] ← Loop 終了

この回答へのお礼

ありがとうございました。拙い脳内解釈を読んでいただき感謝いたします。

お礼日時：2021/12/22 07:35

No.1 回答者： Tacosan 回答日時： 2021/12/22 00:43

(11) はおかしな気がする.

「最初の Loop は i=j=1 だから p[] に変化なし。」って, それで終わり? ループ内で再帰呼び出ししてるのはどこに行った?

この回答へのお礼

ありがとうございました。拙い脳内解釈を読んでいただき感謝いたします。

お礼日時：2021/12/22 07:33