並び替え

[Serdol]

現在C言語で、1～10個の任意の数字の入力を受け付け、そこから順列を生成して出力するプログラムを書いております。
ただし出力に際して順番が決まっています。
例えば、

4 7 9 1 3　と入力(最初の数字は個数を表す)すると、

7, 9, 1, 3
7, 9, 3, 1
7, 1, 3, 9
7, 1, 9, 3
7, 3, 9, 1
7, 3, 1, 9
9, 1, 3, 7
9, 1, 7, 3
9, 3, 7, 1
9, 3, 1, 7
9, 7, 1, 3
9, 7, 3, 1
1, 3, 7, 9
1, 3, 9, 7
1, 7, 9, 3
1, 7, 3, 9
1, 9, 3, 7
1, 9, 7, 3
3, 7, 9, 1
3, 7, 1, 9
3, 9, 1, 7
3, 9, 7, 1
3, 1, 7, 9
3, 1, 9, 7

この順番で出力されなくてはなりません。

しかし、今書いているプログラムだと、
7, 9, 1, 3
9, 7, 1, 3
7, 1, 9, 3
1, 7, 9, 3
1, 9, 7, 3
9, 1, 7, 3
7, 9, 3, 1
9, 7, 3, 1
7, 3, 9, 1
3, 7, 9, 1
3, 9, 7, 1
9, 3, 7, 1
7, 3, 1, 9
3, 7, 1, 9
7, 1, 3, 9
1, 7, 3, 9
1, 3, 7, 9
3, 1, 7, 9
3, 9, 1, 7
9, 3, 1, 7
3, 1, 9, 7
1, 3, 9, 7
1, 9, 3, 7
9, 1, 3, 7

このように出力されてしまいます。どのように変更すればよいでしょうか。
そのプログラムは以下の通りです。

非表示エリア

この非表示エリアを表示するには、登録し、ログインする必要があります。

[かずま]

b[4] = { 0, 1, 2, 3 } の順列を生成し、それを添え字として、
a[4] = { 7, 9, 1, 3 } を表示すればよいのでは？

コード:

#include <stdio.h>   // printf, putchar
#include <stdlib.h>  // malloc, free

int perm(int *b, int *e)
{
    int *p, *q, *r, t;
    if (b + 1 >= e) return 0;
    for (p = e - 1; ; ) {
        r = p;
        if (*--p < *r) {
            for (q = e; *p >= *--q; ) ;
            t = *p, *p = *q, *q = t;
            while (r < --e) t = *e, *e = *r, *r++ = t;
            return 1;
        }
        if (p == b) {
            while (b < --e) t = *e, *e = *b, *b++ = t;
            return 0;
        }
    }
}

int main(void)
{
    int n, i, *a, *b;
    scanf("%d", &n);
    a = malloc(n * sizeof(int));
    b = malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1) return 1;
        b[i] = i;
    }
    do {
        for (int i = 0; i < n; i++)
            if (i == 0) printf("%d", a[b[0]]);
            else printf(", %d", a[b[i]]);
        putchar('\n');
    } while (perm(b, b + n));
    free(b), free(a);
    return 0;
}

[かずま]

元のコードを活かした再帰呼出しバージョンです。

コード:

#include <stdio.h>

int perm[10];

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

void printp(int n)
{
    printf("%d", perm[0]);
    for (int i = 1; i < n; i++)
        printf(", %d", perm[i]);
    printf("\n");
}

void per(int m, int n)
{
    if (m == n)
        printp(n);
    else {
        for (int i = m; i < n; i++) {
            int t = perm[i];
            for (int j = i; j > m; j--) perm[j] = perm[j - 1];
            perm[m] = t;
            per(m + 1, n);
            for (int j = m; j < i; j++) perm[j] = perm[j + 1];
            perm[i] = t;
        }
    }
}

int main(void)
{
    int i, n;
    if (scanf("%d", &n) != 1 || n < 1 || n >10) return 1;
    for (i = 0; i < n; i++)
        scanf("%d", &perm[i]);
    per(0, n);
    return 0;
}

[かずま]

元のコードを活かした再帰呼出しバージョンです。

swap は不要でした。元のコードの swap を rotate にし、
別関数とはせずに for文の中に展開しています。

コード:

#include <stdio.h>

int perm[10];

void printp(int n)
{
    printf("%d", perm[0]);
    for (int i = 1; i < n; i++)
        printf(", %d", perm[i]);
    printf("\n");
}

void per(int m, int n)
{
    if (m == n)
        printp(n);
    else {
        per(m + 1, n);
        for (int i = m; ++i < n; ) {
            int t = perm[i];
            for (int j = i; j > m; j--) perm[j] = perm[j - 1];
            perm[m] = t;
            per(m + 1, n);
            for (int j = m; j < i; j++) perm[j] = perm[j + 1];
            perm[i] = t;
        }
    }
}

int main(void)
{
    int i, n;
    if (scanf("%d", &n) != 1 || n < 1 || n >10) return 1;
    for (i = 0; i < n; i++)
        scanf("%d", &perm[i]);
    per(0, n);
    return 0;
}

[Serdol]

再帰呼び出しを用いたたかずまさんのがとても参考になりました。ありがとうございました。

[かずま]

再帰呼び出しを用いたたかずまさんのがとても参考になりました。ありがとうございました。

質問で一番大切なものであるソースプログラムを非表示にするのは、
なぜですか？
理解に苦します。