c语言实现全排列

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LIST_MAX_NUM 10

struct list {
    int key;
    struct list *next;
};

struct list *extract(struct list *s, int r)
{
    struct list *p = s;
    int i = 0;

    if(s->key <= r)
    {
        return NULL;
    }

    s->key--;

    s = s->next;

    while(s != NULL)
    {
        if(i == r)
        {
            p->next = s->next;
            s->next = NULL;

            return s;
        }

        p = s;
        s = s->next;

        i++;
    }

    return NULL;
}

void add(struct list *s, int r, struct list *t)
{
    struct list *p = s;
    int i = 0;

    if(s->key < r)
    {
        return;
    }

    p->key++;

    while(p != NULL)
    {
        if(i == r)
        {
            t->next = p->next;
            p->next = t;

            return;
        }

        p = p->next;

        i++;
    }
}

int combine(struct list *s, int n, struct list *p, int m)
{
    struct list *u = s;
    struct list *v = NULL;
    struct list *w = NULL;
    int q = 0;
    int i = 0;

    /*while(u != NULL)
    {
        t[i].key = u->key;
        t[i].next = &t[i+1];

        u = u->next;
        i++;
    }*/

    if(n == 1)
    {
        w = s->next;

        for(i=0; i<s->key; i++)
        {
            p[m].key = w->key;

            add(p, p->key, p+m);

            v = p->next;

            while(v != NULL)
            {
                printf("%d ", v->key);

                v = v->next;
            }

            printf("\n");

            extract(p, p->key-1);

            w = w->next;
        }

        return s->key;
    }

    for(i=0; i<s->key; i++)
    {
        v = extract(s, i);
        p[m].key = v->key;
        add(p, p->key, p+m);

        q += combine(s, n-1, p, m+1);

        add(s, i, v);
        extract(p, p->key-1);
    }

    return q;
}

int main()
{
    struct list s[LIST_MAX_NUM+1];
    struct list t[LIST_MAX_NUM+1];
    int i = 1;

    memset(s, 0x00, sizeof(s));
    memset(t, 0x00, sizeof(t));

    for(i=0; i<10; i++)
    {
        s[i+1].key = i + 1;
        s[i].next = &s[i+1];
    }

    for(i=0; i<10; i++)
    {
        t[i+1].key = 0;
        t[i].next = NULL;
    }

    t[0].key = 0;
    s[0].key = 3;
    s[10].next = NULL;

    combine(s, 3, t, 1);

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1