有重复元素的排列问题

有重复元素的排列问题

时间： 1ms        内存：64M

描述：

设R={ r₁, r₂, ……, r_n }是要进行排列的n个元素。其中元素r₁ ,r₂ ,……,r_n可能相同。试设计一个算法，列出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;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。