数列並び替え

[しろくま]

C言語で１から順にnまで並んだ数列をn!通りに並び替え、出力させる方法はありますか？

例えばn=3のときは
123
132
213
231
312
321
です。

[usao]

あると思います．
とりあえず実直にループして羅列してみては？

[かずま]

あります。

コード:

#include <stdio.h>

int next(int a[], int n)
{
    int i, j, k, t;
    for (i = n - 1; ; ) {
        j = i--;
        if (a[i] < a[j]) {
            for (k = n; a[i] >= a[--k]; ) ;
            t = a[i], a[i] = a[k], a[k] = t;
            while (j < --n) t = a[j], a[j++] = a[n], a[n] = t;
            return 1;
        }
        if (i == 0) return 0;
    }
}

int main()
{
    int a[] = { 1, 2, 3 }, i, n = 3;
    do {
        for (i = 0; i < n; i++) printf(" %d", a[i]);
        putchar('\n');
    } while (next(a, n));
    return 0;
}

C++ の next_permutation のコードをパクってきました。

[かずま]

C++ の next_permutation のコードをパクってきました。

今度は自分で考えてみました。

コード:

#include <stdio.h>

int a[] = { 1, 2, 3 };
int n = 3;

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

int main(void)
{
    proc(0);
    return 0;
}

[かずま]

もう少し簡単にしてみました。

コード:

#include <stdio.h>

int n = 3, a[16], f[16];

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

int main(void) { proc(0); return 0; }

n は 16まで OK ですが、10 を超えるとちょっとつらいでしょう。
printf(" %d", a + 'A'); なんていうもの面白いかもしれません。

[かずま]

printf(" %d", a + 'A'); なんていうもの面白いかもしれません。

すみません。printf(" %c", a + 'A'); でした。

[みけCAT]

自分が実装したコードを貼っておきます。

コード:

#include <stdio.h>

#define N 3

/* {1,2,3} -> ... -> {3,2,1} */
int next_permutation(int arr[],int n) {
	int target;
	int i;
	int temp;
	int* arr2;
	int n2;
	for(i=n-2;i>=0;i--) {
		if(arr[i]<arr[i+1])break;
	}
	if(i<0)return 0;
	target=i;

	/* inline reverse_arr */
	arr2=arr+target+1;
	n2=n-target-1;
	for(i=0;n2-i-1>i;i++) {
		int t;
		t=arr2[i];
		arr2[i]=arr2[n2-i-1];
		arr2[n2-i-1]=t;
	}

	for(i=target+1;i<n;i++) {
		if(arr[i]>arr[target])break;
	}
	temp=arr[i];
	arr[i]=arr[target];
	arr[target]=temp;
	return 1;
}

int main(void) {
	int sequence[N];
	int i;
	for(i=0;i<N;i++)sequence[i]=i+1;
	do {
		for(i=0;i<N;i++)printf("%d%c",sequence[i],i+1<N?' ':'\n');
	} while(next_permutation(sequence,N));
	return 0;
}