有重复元素的排列问题
时间: 1ms 内存:64M
描述:
设R={ r1, r2, ……, rn }是要进行排列的n个元素。其中元素r1 ,r2 ,……,rn可能相同。试设计一个算法,列出R的所有不同排列。
给定n以及待排列的n个元素。计算出这n个元素的所有不同排列。
输入:
输入数据的的第1行是元素个数n,1≤n≤500。接下来的1行是待排列的n个元素。
输出:
将计算出的n个元素的所有不同排列输出,每种排列占1行,最后1行中的数是排列总数。
示例输入:
4
aacc
示例输出:
aacc
acac
acca
caac
caca
ccaa
6
提示:
参考答案(内存最优[752]):
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
int num = 0;
int contains(char list[], int k, int i) {
for (int j = k; j < i; j++) {
if (list[i] == list[j])
return 1;
}
return 0;
}
void Swap(char *a, char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}
void Perm(char list[], int k, int m)
{
if (k == m)
{
for (int i = 0; i <= m; i++)
printf("%c",list[i]);
num++;
printf("\n");
}
else
{
for (int i = k; i <= m; i++)
{
if (!contains(list, k, i))
{
Swap(&list[k], &list[i]);
Perm(list, k+1, m);
Swap(&list[k], &list[i]);
}
}
}
}
int main()
{
int n;
char *list;
scanf("%d",&n);
list = (char *)malloc(sizeof(char)*n);
scanf("%s", list);
Perm(list, 0, n-1);
printf("%d\n",num);
return 0;
}
参考答案(时间最优[212]):
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
int num = 0;
int contains(char list[], int k, int i) {
for (int j = k; j < i; j++) {
if (list[i] == list[j])
return 1;
}
return 0;
}
void Swap(char *a, char *b)
{
char temp = *a;
*a = *b;
*b = temp;
}
void Perm(char list[], int k, int m)
{
if (k == m)
{
for (int i = 0; i <= m; i++)
printf("%c",list[i]);
num++;
printf("\n");
}
else
{
for (int i = k; i <= m; i++)
{
if (!contains(list, k, i))
{
Swap(&list[k], &list[i]);
Perm(list, k+1, m);
Swap(&list[k], &list[i]);
}
}
}
}
int main()
{
int n;
char *list;
scanf("%d",&n);
list = (char *)malloc(sizeof(char)*n);
scanf("%s", list);
Perm(list, 0, n-1);
printf("%d\n",num);
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。