与えられた順列の距離から一番最短距離のみ表示する

[matu]

かなり今焦っています。
学校から与えられた課題で、ある店が６１店舗（店舗番号は１から６１）ありその店から自分で４店舗ランダムに選び、その４店舗の順列（２４通り）の距離を求め一番最短距離の順列と距離のみを出力するよう課題が
でました。今のところ、順列と距離は求めるプログラムは組めたのですが最短距離の順列と距離を選択し出力するところがどうやっていかわかりません。ご教授ください。いまできているところまでのコードを載せます。
下のコードでは４店舗は店舗番号（８，７，１３，２４）です。コードの中の６１店舗のそれぞれの距離間
d[MAX+1][MAX+1]の配列の中身は文字数の関係で省略させていただきます。
[/pre]
#include <stdio.h>
#define MAX 61
#define N 4
int v[N+1]={0,8,7,13,24};
int p[N + 1];
void perm(int);
int main(void)
{
int i;
for (i=1;i<=N;i++)
p = i;
perm(1);
return 0;
}
void perm(int i)
{
int j, t,sum,min;
min=100000;
sum=0;
if (i < N)
{
for (j = i; j <= N; j++) {
t = p=v; p=v = p[j]=v[j]; p[j]=v[j] = t;
perm(i + 1);
t = p=v; p=v = p[j]=v[j]; p[j]=v[j] = t;
}
}

else {
int d[MAX+1][MAX+1]={
};
/*p[j]とv[j]の交換*/
for(j=1;j<=N;j++)
{
p[j]=v[j];
}
/*距離(sum)をだしている*/
for(j=1;j<=N;j++)
{
printf("%d ",v[j]);
sum +=d[v[j]][v[j+1]];
}
printf("%d",sum);
printf("\n");


}
}

[matu]

すいません字下げするの忘れてしまいました

#include <stdio.h>
#define MAX 61
#define N   4
int v[N+1]={0,8,7,13,24};
int p[N + 1];
void perm(int);
int main(void)
{
    int i;
    for (i=1;i<=N;i++) 
		p = i;
        perm(1);
		return 0;
}
 void perm(int i)
 {
	 int j, t,sum,min;
	 min=100000;
	 sum=0;
	 if (i < N)
	 {
        for (j = i; j <= N; j++) {
            t = p=v;  p=v = p[j]=v[j];  p[j]=v[j] = t;
            perm(i + 1);
            t = p=v;  p=v = p[j]=v[j];  p[j]=v[j] = t;
		}
	 }
	 
    else {
int d[MAX+1][MAX+1]={
};
/*p[j]とv[j]の交換*/
for(j=1;j<=N;j++) 
	 {
     p[j]=v[j];  
     }
/*距離(sum)をだしている*/
for(j=1;j<=N;j++)
	{
	printf("%d ",v[j]);
	sum +=d[v[j]][v[j+1]];
    }
	printf("%d",sum);
	printf("\n");
	

	}
	}

[box]

せめて、こんな風に字下げできないものでしょうか。
元のコードは読みづらいことこの上ありません。

#include <stdio.h>

#define MAX 61
#define N   4

int v[N+1]={0,8,7,13,24};
int p[N + 1];

void perm(int);

int main(void)
{
	int i;
	
	for (i=1;i<=N;i++)
		p = i;
	perm(1);
	return 0;
}

void perm(int i)
{
	int j, t,sum,min;
	min=100000;
	sum=0;
	
	if (i < N) {
		for (j = i; j <= N; j++) {
			t = p=v;  p=v = p[j]=v[j];  p[j]=v[j] = t;
			perm(i + 1);
			t = p=v;  p=v = p[j]=v[j];  p[j]=v[j] = t;
		}
	}
	else {
		int d[MAX+1][MAX+1]={
		};
		
		/*p[j]とv[j]の交換*/
		for(j=1;j<=N;j++) {
			p[j]=v[j];
		}
		
		/*距離(sum)をだしている*/
		for(j=1;j<=N;j++) {
			printf("%d ",v[j]);
			sum +=d[v[j]][v[j+1]];
		}
		printf("%d",sum);
		printf("\n");
	}
}

[lbfuvab]

最短の順列とは何でしょうか？
また距離に関しては、最短距離がいくつもあった場合にも依りますが、

1.距離を配列aで保存

2.最小値を格納する変数minを用意しminに*aを代入

3.以下の4～5を必要回数繰り返す。

4.aをインクリメントする

5.*aとminを比べて*aが小さければminに*aを代入

で良いと思いますよ。

[matu]

すいません。次から気をつけます。

[matu]

lbfuvab さん、boxさん返信ありがとうございます。
最短の順列とは最短距離になる順列も一緒に出力したいのです。

1の部分
#define M 24

int a[M];
int k;
a[k]=sum;

２の部分はポインタを使うのですか？

[non]

>d[MAX+1][MAX+1]の配列の中身は文字数の関係で省略
たぶん、各店舗間の距離が入っているのだと思いますが、
現在地から、最初の店までの距離または最後の店から現在地までの距離は、
必要ないのでしょうか？

/*距離(sum)をだしている*/
		for(j=1;j<=N;j++) {
			printf("%d ",v[j]);
			sum +=d[v[j]][v[j+1]];
		}

j=Nのとき　v[j+1]ってのは何？

[matu]

non さん返信ありがとうございます。d[MAX+1][MAX+1]には各店舗間の距離が入っています。
実際はある出発地点を出発し最後はそこに戻ってくるというようにしたいんのですが、今はそのプログラム
がわからないので４店舗間を回る最短距離とその順列を求めたいのです。
j=Nの時のd[v[j]][v[j+1]]のv[j+1]というのは３店舗目と４店舗目の距離です

[matu]

すいません、まちがえました

/*距離(sum)をだしている*/
		for(j=1;j<=N;j++) {
			printf("%d ",v[j]);
			sum +=d[v[j]][v[j+1]];

のforループは()中はfor(j=1;j<N;j++){
間違えました。すいません

}

[non]

> 実際はある出発地点を出発し最後はそこに戻ってくるというようにしたいんのですが、今はそのプログラム
> がわからないので４店舗間を回る最短距離とその順列を求めたいのです。

了解です。

> j=Nの時のd[v[j]][v[j+1]]のv[j+1]というのは３店舗目と４店舗目の距離です


>#define N 4
>int v[N+1]={0,8,7,13,24};
と宣言されていますから、j=Nのときv[4+1]すなわちv[5]になり、配列の範囲外です。

>２の部分はポインタを使うのですか？
ポインタでなくてもいいです。
min=a[0]　のように配列でもOK

ただ、プログラムを読むと、すべて、permという１つの関数でやろうとしていますが、分けた方が
わかりやすいと思います。再帰呼び出しを使ったプログラムが書けるのですから、その心配はいらない
のかもしれませんけど・・・って、元になる再帰呼び出し部分は提供されたものなんでしょうか？

[matu]

返信ありがとうございます。
そうなんです。permという1つの関数でやっているので、分けたいのですが、
順列生成部分の再帰を使ったところは提供されたのものなので分け方がわかりません。
実際にはどうやってやればいいのでしょうか

[non]

配列pはまったく役に立っていないと思いますが、これは何の使用目的がありますか？

[non]

必要なさそうなものを省いて、わかりやすくしたつもりです。
配列dはグローバルにしました。おそらくファイルで提供されるだろうから、再帰呼び出しの中で
宣言しない方がいいと思います。
配列passに２４通りの道順を入れることにしました。
距離の合計と最小を求める部分は書いていません。

#include <stdio.h>

#define MAX 61
#define N   4
#define nPr 24
int v[N+1]={0,8,7,13,24}; 
int d[MAX+1][MAX+1]={0}; //データ略
int pass[nP[/url][N+1];

void perm(int);
void wayPass(void);

int main(void)
{
	int i;
	perm(1);
	/* この後、配列passの合計を求め、最小値を求める*/
	return 0;
}
void wayPass(void)
{
	static int no=0;
	int i;
	for(i=1;i<=N;i++)
		pass[no]=v;
	no++;
}
void perm(int i)
{
	int j, t;

	if (i < N) {
		for (j = i; j <= N; j++) {
			t = v;  v =v[j];  v[j] = t ;
			perm(i + 1);
			t = v;  v =v[j];  v[j] = t;
		}
	}
	else 
		wayPass();
}

[matu]

配列Ｐは意味ありませんでした。
配列passに２４通りの道順はどうやって入れるのですか？

[lbfuvab]

分けて考えましょう。

①重複の無い4つの乱数の生成
②24通りの順列とそれぞれの距離の生成
③最短距離の判定(前に私がレスした奴です)
④出力

どれが出来てどれが出来ないのですか？

[matu]

質問が下手ですいません、
どこのコードの部分に

②24通りの順列とそれぞれの距離の生成 
               
　　　　　　 /*距離(sum)をだしている*/
		for(j=1;j<=N;j++) {
			printf("%d ",v[j]);
			sum +=d[v[j]][v[j+1]];
		}
		printf("%d",sum);
		printf("\n");

さらに③④

pass[nP[/url][N]は以下のようになっていると思います。そのうえで
              pass[nP[/url][N]={8,7,13,24,sum},
                           {8,13,7,24,sum},
                                    .
                                    .
                                    .
                            {          sum}};
　　　　　　最小値を求めるコード
　　　　　　　　　　int min,s,u,j;
                     for(u=0;u<nPr-1;u++){
                         min=pass[[/url][N];
                         s=u;
                         for(j=0;j<=23;j++){
                               if(min>pass[j][N]){
                                   min=pass[j][N];
                                   s=j;
                               }
                           }
                      t=pass[[/url][N];pass[[/url][N]=pass;pass=pass=t;
                        }
　　　上のコードを最小値の判定の仕方。最小値の時の道順と最小値のみを出力の仕方がわかりません

[matu]

すいません字下げとコードまちがえてました。

pass[nP[/url][N]は以下のようになっていると思います。そのうえで 
　　　　pass[nP[/url][N]={8,7,13,24,sum}
　　　　　　　　　　 {8,13,7,24,sum} 
　　　　　　　　　        　. 
　　　　　　　　　　        . 
　　　　　　　　　　        . 
　　　　　　　       {          sum}}; 
　　　　　　最小値を求めるコード 
　　　　　　　　　　int min,s,u,j; 

                    for(u=0;u<nPr-1;u++){ 
                        min=pass[[/url][N]; 
                        s=u; 
                        for(j=u;j<=23;j++){ 
                            if(min>pass[j][N]){ 
                               min=pass[j][N]; 
                               s=j; 
                            } 
                        } 
                     t=pass[[/url][N];pass[[/url][N]=pass;pass=pass=t; 
                   }

[non]

pass[nP[/url][N]には、まだ合計は入れてませんし、入れるための配列も用意していません。
０列目はmatuさんの、ほかの配列同様、未使用です。
ですから、合計を入れるなら、0列目を使って、={sum,8,7,13,24}のようにすればいいかもしれません。
すると②の部分は次のような関数になります。

void wayPass(void)
{
	static int no=0;
	int i;
	for(i=1;i<=N;i++)
		pass[no]=v;
	pass[no][0]=0;
	for(i=1;i<N;i++)
		pass[no][0]+=d[v][v[i+1]];
	no++;
}

③で、
>t=pass[[/url][N];pass[[/url][N]=pass;pass=pass=t;
は、何をやりたいのかわかりませんが？

[lbfuvab]

えーと
配列Passはint型の二次元配列ですよね？
とするとpass[[/url][N]=pass;とかpass=pass=t;はまずいと思うのですが…

とりあえず適当な0～23の数をaとすると
pass[a][0]～pass[a][3]は順番、pass[a][4]は距離の合計ですよね？

後、乱暴な話

#define INPUT_PERM(pass,a,b,c,d)                                #
do{                                                             #
    pass[0 ][0]=a;pass[0 ][1]=b;pass[0 ][2]=c;pass[0 ][3]=d;    #
    pass[1 ][0]=a;pass[1 ][1]=b;pass[1 ][2]=d;pass[1 ][3]=c;    #
    pass[2 ][0]=a;pass[2 ][1]=c;pass[2 ][2]=b;pass[2 ][3]=d;    #
    pass[3 ][0]=a;pass[3 ][1]=c;pass[3 ][2]=d;pass[3 ][3]=b;    #
    pass[4 ][0]=a;pass[4 ][1]=d;pass[4 ][2]=b;pass[4 ][3]=c;    #
    pass[5 ][0]=a;pass[5 ][1]=d;pass[5 ][2]=c;pass[5 ][3]=b;    #
    pass[6 ][0]=b;pass[6 ][1]=a;pass[6 ][2]=c;pass[6 ][3]=d;    #
    pass[7 ][0]=b;pass[7 ][1]=a;pass[7 ][2]=d;pass[7 ][3]=c;    #
    pass[8 ][0]=b;pass[8 ][1]=c;pass[8 ][2]=a;pass[8 ][3]=d;    #
    pass[9 ][0]=b;pass[9 ][1]=c;pass[9 ][2]=d;pass[9 ][3]=a;    #
    pass[10][0]=b;pass[10][1]=d;pass[10][2]=a;pass[10][3]=c;    #
    pass[11][0]=b;pass[11][1]=d;pass[11][2]=c;pass[11][3]=a;    #
    pass[12][0]=c;pass[12][1]=a;pass[12][2]=b;pass[12][3]=d;    #
    pass[13][0]=c;pass[13][1]=a;pass[13][2]=d;pass[13][3]=b;    #
    pass[14][0]=c;pass[14][1]=b;pass[14][2]=a;pass[14][3]=d;    #
    pass[15][0]=c;pass[15][1]=b;pass[15][2]=d;pass[15][3]=a;    #
    pass[16][0]=c;pass[16][1]=d;pass[16][2]=a;pass[16][3]=b;    #
    pass[17][0]=c;pass[17][1]=d;pass[17][2]=b;pass[17][3]=a;    #
    pass[18][0]=d;pass[18][1]=a;pass[18][2]=b;pass[18][3]=c;    #
    pass[19][0]=d;pass[19][1]=a;pass[19][2]=c;pass[19][3]=b;    #
    pass[20][0]=d;pass[20][1]=b;pass[20][2]=a;pass[20][3]=c;    #
    pass[21][0]=d;pass[21][1]=b;pass[21][2]=c;pass[21][3]=a;    #
    pass[22][0]=d;pass[22][1]=c;pass[22][2]=a;pass[22][3]=b;    #
    pass[23][0]=d;pass[23][1]=c;pass[23][2]=b;pass[23][3]=a;    #
}while(0)

こういうのもありですね。

[non]

それは、ちょっと乱暴すぎるのでは。。。(^o^)

[matu]

返信ありがとうございます。

void wayPass(void)
{
	static int no=0;
	int i;
	for(i=1;i<=N;i++)
		pass[no]=v;
	pass[no][0]=0;
	for(i=1;i<N;i++)
		pass[no][0]+=d[v][v[i+1]];
	no++;
}

上のコードでpass[no][0]が道順の距離の総和になるのですよね！
③の部分は考えた結果先ほどのは間違えで私は

for(j=0;j<=23;j++){
                                 if(min>pass[j][0]){
                                    min=pass[j][0]
                                   }
                                }
                              printf("%d",min);

だと思うのですが・・・

[box]

> だと思うのですが・・・

思ったら、人に聞くよりも前に、すぐやってみるべし。

[lbfuvab]

えっpass[a][0]が距離の総和なのですか？
ならば

#define INPUT_PERM(pass,a,b,c,d)                                #
do{                                                             #
    pass[0 ][1]=a;pass[0 ][2]=b;pass[0 ][3]=c;pass[0 ][4]=d;    #
    pass[1 ][1]=a;pass[1 ][2]=b;pass[1 ][3]=d;pass[1 ][4]=c;    #
    pass[2 ][1]=a;pass[2 ][2]=c;pass[2 ][3]=b;pass[2 ][4]=d;    #
    pass[3 ][1]=a;pass[3 ][2]=c;pass[3 ][3]=d;pass[3 ][4]=b;    #
    pass[4 ][1]=a;pass[4 ][2]=d;pass[4 ][3]=b;pass[4 ][4]=c;    #
    pass[5 ][1]=a;pass[5 ][2]=d;pass[5 ][3]=c;pass[5 ][4]=b;    #
    pass[6 ][1]=b;pass[6 ][2]=a;pass[6 ][3]=c;pass[6 ][4]=d;    #
    pass[7 ][1]=b;pass[7 ][2]=a;pass[7 ][3]=d;pass[7 ][4]=c;    #
    pass[8 ][1]=b;pass[8 ][2]=c;pass[8 ][3]=a;pass[8 ][4]=d;    #
    pass[9 ][1]=b;pass[9 ][2]=c;pass[9 ][3]=d;pass[9 ][4]=a;    #
    pass[10][1]=b;pass[10][2]=d;pass[10][3]=a;pass[10][4]=c;    #
    pass[11][1]=b;pass[11][2]=d;pass[11][3]=c;pass[11][4]=a;    #
    pass[12][1]=c;pass[12][2]=a;pass[12][3]=b;pass[12][4]=d;    #
    pass[13][1]=c;pass[13][2]=a;pass[13][3]=d;pass[13][4]=b;    #
    pass[14][1]=c;pass[14][2]=b;pass[14][3]=a;pass[14][4]=d;    #
    pass[15][1]=c;pass[15][2]=b;pass[15][3]=d;pass[15][4]=a;    #
    pass[16][1]=c;pass[16][2]=d;pass[16][3]=a;pass[16][4]=b;    #
    pass[17][1]=c;pass[17][2]=d;pass[17][3]=b;pass[17][4]=a;    #
    pass[18][1]=d;pass[18][2]=a;pass[18][3]=b;pass[18][4]=c;    #
    pass[19][1]=d;pass[19][2]=a;pass[19][3]=c;pass[19][4]=b;    #
    pass[20][1]=d;pass[20][2]=b;pass[20][3]=a;pass[20][4]=c;    #
    pass[21][1]=d;pass[21][2]=b;pass[21][3]=c;pass[21][4]=a;    #
    pass[22][1]=d;pass[22][2]=c;pass[22][3]=a;pass[22][4]=b;    #
    pass[23][1]=d;pass[23][2]=c;pass[23][3]=b;pass[23][4]=a;    #
}while(0)

ですね、失礼しました。。。

[matu]

lbfuvab box さん返信ありがとうございます。今は学校にいないのでできません明日すぐにやってみます。
あと本当に申し訳なのですがlbfuvab のコードですが、今の段階では４店舗ですが、今後は店舗を１０店舗にしてやりたいと思っているので・・・・
お答えいただいたのに本当に申し訳ありません。

[box]

> ある店が６１店舗（店舗番号は１から６１）ありその店から自分で４店舗ランダムに選び、その４店舗の順列（２４通り）の距離を求め一番最短距離の順列と距離のみを出力

今さら何を？ということかもしれませんが、
問題空間を少し狭めて考えてみてはいかがでしょうか。
６～７店舗くらいから３店舗を選び、その３店舗の順列（６とおり）の距離を求め…
という具合に。
狭い空間でじゅうぶんデバッグできたら、本来の問題空間に戻してやればよいと思います。
プログラムのロジックは問題空間の広さとは関係ないはずですので。

[non]

>今の段階では４店舗ですが、今後は店舗を１０店舗にしてやりたいと

#define N 4
#define nPr 24
が、
#define N 10
#define nPr 3628800
になるだけだと思いますが。
ただ、passの配列がそんなにでかくなるのなら、配列に入れなくて直接minだけ求めた方がいいかも。
3628800×11×4バイト/1024/1024=152.27メガバイト

[matu]

最終的にはそうします！
でも今の段階では、まず、４店舗チャレンジさせてください。
今nonさんのを参考にさせていただいて、最小値（min）のみはだすことができました。
次はその時の道順も出したいのですが...わかりません。今のコードは以下のとおりです。

#include <stdio.h>

#define MAX 61
#define N   4
#define nPr 24
int v[N+1]={0,8,7,13,24}; 
int d[MAX+1][MAX+1]={省略}};
int pass[nP[/url][N+1];
void perm(int);
int min;
void wayPass(void);

int main(void)
{
	int i,j;
	perm(1);
	min=10000;
    for(j=0;j<=23;j++){
		if(min>pass[j][0]){
			min=pass[j][0];
		}
	}
	printf("%d",min);
	printf("\n");
    return 0;
}
void wayPass(void)
{
	static int no=0;
	int i;
	for(i=1;i<=N;i++)
		pass[no]=v;
	pass[no][0]=0;
	for(i=1;i<=N;i++){
		pass[no][0]+=d[v][v[i+1]];
	}
	no++;
}


void perm(int i)
{
	int j, t;

	if (i < N) {
		for (j = i; j <= N; j++) {
			t = v;  v =v[j];  v[j] = t ;
			perm(i + 1);
			t = v;  v =v[j];  v[j] = t;
		}
	}
	else 
		wayPass();
}

[non]

２つの関数を作ってみました。
違いがわかりますか？

int minPerm(void)
{
	int min,j;
	min=pass[0][0]; // 1個目を仮の最小値とする
	for(j=1;j<nPr;j++){
		if(min>pass[j][0])
			min=pass[j][0];
	}
	return min;
}
int minPerm2(void)
{
	int min,j;
	min=0; 
	for(j=1;j<nPr;j++){
		if(pass[min][0]>pass[j][0])
			min=j;
	}
	return min;
}
int main(void)
{
	int i,j;
	perm(1);
	printf("%d\n",minPerm());
	printf("%d\n",pass[minPerm2()][0]);
	return 0;
}

[matu]

minPermが距離を求めている関数で
minPerm2が道順を求めている関数だと思います。

[non]

>minPerm2が道順を求めている関数だと思います。

距離が最小となる配列の添え字番号（Index）を求めています。
では、あとは表示する関数を作れるでしょう。

[matu]

返信ありがとうございます！
やったみます。