c语言实现全排列
2022-04-12 本文已影响0人
一路向后
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