全排列

经典交换算法---递归版

#include <stdio.h>

void perm(int *, int);
void swap(int *, int *);

int n, tmp;
int *buf;

int main()
{
    if(EOF != scanf("%d", &n))
    {
        buf = (int *)malloc(n * sizeof(int));
        
        for(tmp = 0; tmp < n; tmp++)
        {
            buf[tmp] = tmp + 1;
        }
        
        perm(buf, n);
    }
}

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

void perm(int *data, int len)
{
    int start;
    if(1 == len)
    {
        int tmp;
        for(tmp = 0; tmp < n; tmp++)
        {
            printf("%d ", buf[tmp]);
        }
        printf("\n");
        return;
    }
    
    for(start = 0; start < len; start ++)
    {
        swap(&data[0], &data[start]);
        perm(&data[1], len - 1);
        swap(&data[0], &data[start]);    
    }
}

交换法---非递归实现

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

void output(int *, int);
void swap(int *, int *);

inline void output(int *buf, int len)
{
    int tmp;
    for(tmp = 0; tmp < len; tmp ++)
    {
        printf("%d ", buf[tmp]);
    }
    printf("\n");
}

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

int main()
{
    int *buf, n;
    int *stack;
    int lv;
    if(EOF != scanf("%d", &n))
    {
        buf = (int *)malloc(n * sizeof(int));
        stack = (int *)malloc(n * sizeof(int));
        
        for(lv = 0; lv < n; lv ++)
        {
            buf[lv] = lv + 1;
            stack[lv] = lv;
        }
        
        lv = 0;
        while(1)
        {
            if(lv < 0)
            {
                break;
            }
            
            if(n - 1 == lv)
            {
                output(buf, n);
                lv --;
                if(lv >=0)
                {
                    swap(&buf[lv], &buf[stack[lv]]);
                    stack[lv] ++;
                }
                continue;
            }
            
            if(n == stack[lv])
            {
                stack[lv] = lv;
                lv --;
                if(lv >=0)
                {
                    swap(&buf[lv], &buf[stack[lv]]);
                    stack[lv] ++;
                }
                continue;
            }
            
            swap(&buf[lv], &buf[stack[lv]]);
            lv ++;
        }
    }
}