C言語 質問変更削除

Question

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Comments

[jimbe]

「順列 c言語」等で検索してみてください。

> 4重のループによって解こうとしている

4 重ループありきで作っているのでしょうか。
どうすれば出来るのかのイメージがあればそれでコードを書けるはずですが、「4 つの要素を変化させるから 4 重ループ」…というだけであれば、根本から考え直した方が良いかと思います。

Answer 1

最初の都市が固定なら、

#include <stdio.h>

void gen(int a[], int n, int i)
{
	if (i < n)
		for (int j = i; j < n; j++) {
			int t = a[i]; a[i] = a[j], a[j] = t;
			gen(a, n, i+1);
			t = a[i], a[i] = a[j], a[j] = t;
		}
	else {
		for (i = 0; i < n; i++) printf(" %d", a[i]);
		putchar('\n');
	}
}

int main(void)
{
	int a[] = { 1, 2, 3, 4, 5 };
	gen(a, 5, 1);
}

実行結果

 1 2 3 4 5
 1 2 3 5 4
 1 2 4 3 5
 1 2 4 5 3
 1 2 5 4 3
 1 2 5 3 4
 1 3 2 4 5
 1 3 2 5 4
 1 3 4 2 5
 1 3 4 5 2
 1 3 5 4 2
 1 3 5 2 4
 1 4 3 2 5
 1 4 3 5 2
 1 4 2 3 5
 1 4 2 5 3
 1 4 5 2 3
 1 4 5 3 2
 1 5 3 4 2
 1 5 3 2 4
 1 5 4 3 2
 1 5 4 2 3
 1 5 2 4 3
 1 5 2 3 4

Comments

[Cass-_.4567]

ありがとうございました。

[Cass-_.4567]

すみません。for文で
for (int j = i; j < n; j++) {
int t = a[i]; a[i] = a[j], a[j] = t;
gen(a, n, i+1);
t = a[i], a[i] = a[j], a[j] = t;
}
がどのように動いているのかを教えていただけますか？

Answer 2

順列の数え方そのままな感じのサンプルです。

#include <stdio.h>

void output(char *buf, int size) {
  buf[size] = '\0';
  printf("%s\n", buf);
}

void permutation(char *s, int n, char *buf, int idx) {
  if(n <= 0) {
    output(buf, idx);
    return;
  }
  char w[n-1];
  for(int i=0; i<n; i++) {
    buf[idx] = s[i];
    for(int j=0, k=0; j<n; j++) if(j != i) w[k++] = s[j]; //s[i]を除いた残り
    permutation(w, n-1, buf, idx+1);
  }
}

#define N 3

int main(void){
  char stock[N];
  char buf[N+1];//+1は表示時'\0'用

  for(int i=0; i<N; i++) stock[i] = 'a'+i;

  permutation(stock, N, buf, 0);
}

abc
acb
bac
bca
cab
cba

Comments

[Cass-_.4567]

ありがとうございました。変数をNに拡張したときのmain関数の書き方として非常に参考になりました。