C语言怎么实现有重复元素的全排列？

C语言如何实现有重复元素的全排列?~

在递归里面用交换的方式获取全排列，从第一个开始，不断与后面数交换，当然递归时不要忘记在后面写个换回来的语句。只要加个交换条件就可以了，在不相等时交换，相等时不交换。
当前阶段，在编程领域中，C语言的运用非常之多，它兼顾了高级语言和汇编语言的优点，相较于其它编程语言具有较大优势。计算机系统设计以及应用程序编写是C语言应用的两大领域。同时，C语言的普适较强，在许多计算机操作系统中都能够得到适用，且效率显著。
C语言拥有经过了漫长发展历史的完整的理论体系，在编程语言中具有举足轻重的地位。



特有特点
C语言是普适性最强的一种计算机程序编辑语言，它不仅可以发挥出高级编程语言的功用，还具有汇编语言的优点，因此相对于其它编程语言，它具有自己独特的特点。具体体现为以下三个方面：
其一，广泛性。C语言的运算范围的大小直接决定了其优劣性。C语言中包含了34种运算符，因此运算范围要超出许多其它语言，此外其运算结果的表达形式也十分丰富。此外，C语言包含了字符型、指针型等多种数据结构形式，因此，更为庞大的数据结构运算它也可以应付。
其二，简洁性。9类控制语句和32个关键字是C语言所具有的基础特性，使得其在计算机应用程序编写中具有广泛的适用性，不仅可以适用广大编程人员的操作，提高其工作效率，同时还能够支持高级编程，避免了语言切换的繁琐。
其三，结构完善。C语言是一种结构化语言，它可以通过组建模块单位的形式实现模块化的应用程序，在系统描述方面具有显著优势，同时这一特性也使得它能够适应多种不同的编程要求，且执行效率高。

#include
#include
#include
#define TRUE 1
#define FALSE 0
// 字符串最大长度
#define MAX_STRING_LENGTH 50
// 全排列顺序。TRUE:按字母序升序；FALSE:按字母序降序。
#define PERMUTATION_ASSCENDING_ORDER TRUE
// qsort 函数使用的比较函数
int compare(const void *a, const void *b)
{
return PERMUTATION_ASSCENDING_ORDER
? *((char*)a) - *((char*)b)
: *((char*)b) - *((char*)a);
}
/*
无重复全排序。
参数：
str 要进行无重复全排序的字符串。
字符串内字符必须已经排序过（升序或降序都可以）

isUsed 如果 isUsed[i] = TRUE 表示 str[i] 已经加入当前排列中

p 当前排列中已经存在的字符数

buffer 当前的排列。
buffer[0]~buffer[p-1] 是 str 中已经加入排列的字符。

返回：
无重复全排序的总数。
*/
int Perm(char str[],int isUsed[],int p ,char buffer[])
{
int len=strlen(str),i,j,total=0;

if(p == len)
{// 输出一个全排列
printf("%s
",buffer);
return 1;
}

for(i=0;i<len;i++)
{
if(!isUsed[i])
{
// 查询当前字符的后面，是否已经有和当前字符相同的字母加入了全排序中。
for(j=i+1;j<len;j++)
if(str[i]==str[j] && isUsed[j])
break;

if(j == len)
{ // 当前字符的后面，没有和当前字符相同的字母加入了全排序中。
// 当前字符可以加入全排序

isUsed[i] = TRUE;
buffer[p] = str[i];
total += Perm(str,isUsed,p+1,buffer);
isUsed[i] = FALSE;
}
}
}
return total;
}

int main(int argc, char *argv[])
{
char str[MAX_STRING_LENGTH]="aacc";
char buffer[MAX_STRING_LENGTH]={0};
int isUsed[MAX_STRING_LENGTH]={0};

while(scanf("%s",str)!=EOF)
{
// 先按字母序排序
qsort(str,strlen(str),sizeof(str[0]),compare);
// 全排列
printf("Total %d

",Perm(str,isUsed,0,buffer));
}
return 0;
}

整体思路就是利用回溯的思想，也可认为是深度优先搜索

从字符串第一位idx=0开始，每次递归都从s[idx]之后选择一个字符与s[idx]交换

因为可能有重复字符，可使用哈希数组标记当前循环每个字符是否被选择

因为字符范围不超过ASCII码，所以使用128空间的数组足够用来标记了

选择好当前字符s[i]并与s[idx]交换之后，递归调用继续排列下一位s[idx+1]

注意这里要进行回溯，即不选s[i]而选择之后的某个字符交换到s[idx]

所以要将之前的s[i]与s[idx]交换过来，恢复原状，才能循环判断下一个选择

具体代码截图如下：

运行结果如下：

结果正确，望采纳~

附源码：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAXN 1000000 // 排列总数可能很多

int num = 0; // 记录排列总数

char *res[MAXN] = {NULL}; // 指针数组保存排列结果

void swap(char *x, char *y) { // 交换两个字符变量的内容

    char ch = *x;

    *x = *y;

    *y = ch;

}

void perm(char *s, int n, int idx) { // 回溯产生字符串全排列

    if (idx == n) { // 已排列到字符串结尾

        res[num] = (char *)malloc(sizeof(char) * (n + 1));

        //printf("%s
", s); // 输出当前排列

        strcpy(res[num], s); // 保存当前排列

        num++; // 排列总数加1

        return;

    }

    int i, hash[128] = {0}; // 哈希数组，标记每个字符是否被选择

    for (i = idx; i < n; i++) {

        if (hash[s[i]] == 1)

            continue; // 跳过已被标记过的重复字符

        hash[s[i]] = 1; // 选过的话在数组中标记为1

        swap(&s[idx], &s[i]); // 选择s[i]交换到s[idx]

        perm(s, n, idx + 1); // 递归，继续s[idx+1]的选择

        swap(&s[idx], &s[i]); // 回溯，当前不选择s[i]，而选择其他字符

    }

}

int main() {

    int n, i;

    scanf("%d", &n);

    char *s = (char *)malloc(sizeof(char) * (n + 1));

    scanf("%s", s);

    perm(s, n, 0);

    printf("一共有%d种排列:
", num); // 输出排列总数

    for (i = 0; i < num; i++) { // 输出所有排列

        printf("%s
", res[i]);

        free(res[i]); // 释放内存空间

    }

    free(s);

    return 0;

}

---

攸县19733521139： 用C语言解决具有重复项的数组全排列问题 - ？
宇文洪知甘： 那还是排列问题,把比较的条件设置成>= 或是

攸县19733521139： 如何用C语言实现有重复的字符排列组合? - ？
宇文洪知甘： 可自行百度＂排列组合＂.对于你举的例子,因为不存在重复字符,共有A(4,4) = 256种结果.如果输入字符中有重复项,需要加入判断重复并剔除的功能.可定义一个2维数组,每次排列完后对数组内的重复项进行删除.

攸县19733521139： c语言 重复字符全排列 - ？
宇文洪知甘： 给程序加点注释,让别人也稍微明白一下 呵呵,你确定自己的程序在思想上之类的没有错误么? 在perm后面的for中调用circle_*的函数的时候,你传入的l总是会比i大的 这样一来在函数中m接收l,i接收i 然后再circle_*中的for循环的判断条件是i-m应该是不会执行吧至于你说的那个功能我也不是很清楚 呵呵,能帮的就只有这些了

攸县19733521139： 全排列用C语言实现 - ？
宇文洪知甘： 给,已经编译运行确认: #include<stdio.h> #include<string.h> char a[20]; int lenth; long count=0; void main() {void move(int,int); int i,j=0; printf(＂input:＂);gets(a); lenth=strlen(a); for(i=0;i<lenth;i++) move(j,i);//move a[i] to the front of a[j]; printf(＂\...

攸县19733521139： 如何用C语言编写1234的全排列 - ？
宇文洪知甘： #include <stdio.h> void main() {int i=0,j=0,k=0,l=0,count=0;for(i=1;i<=4;i++){for(j=1;j<=4;j++)if(j!=i)for(k=1;k<=4;k++)if(k!=i&&k!=j)for(l=1;l<=4;l++)if(l!=i&&l!=j&&l!=k){ count++;printf(＂\n\t第%2d个 %d %d %d %d＂,count,i,j,k,l);}}putchar('\n'); }

攸县19733521139： 用c语言实现 ABCDE按照全排列输出所有结果 - ？
宇文洪知甘： #include <stdio.h> #include <stdlib.h> void main() {char i,j,k,m,n;for(i='A';i<='E';i++)for(j='A';j<='E';j++)for(k='A';k<='E';k++)for(m='A';m<='E';m++)for(n='A';n<='E';n++)if(i!=j&&i!=k&&i!=m&&i!=n&&j!=k&&j!=m&&j!=n&&k!=m&&k!=n&&m!=n)...

攸县19733521139： C语言实现非递归全排列 - ？
宇文洪知甘： 这个函数你可以这样理解,要对一个长度为n的数组全排列,用位置来考虑,首先将所有元素放入第一个位置,实现了第一个位置的全排列,然后对于每一个剩下的n-1个位置再进行全排列.直到最后没有位置了 全排列结束.

攸县19733521139： c语言中怎样把n个数排列 得到所有排列情况 - ？
宇文洪知甘： #includeinline void Swap(char& a, char& b) {// 交换a和b char temp = a; a = b; b = temp; } void Perm(char list[], int k, int m) { //生成list [k:m ]的所有排列方式 int i; if (k == m) {//输出一个排列方式 for (i = 0; i putchar(list[i]); putchar('\n'); } else // list[k:m ]有...

攸县19733521139： C语言编程序:要求任给一个一维数组,其中重复的元素只保留一个,然后把互不重复的按照升序排列! - ？
宇文洪知甘： 改了一下顺序,先排列,后删除重复的元素# include <stdio.h> void sort(int a[],int n); int del(int a[],int n); main() { int a[1000],i,n; printf(＂How many numbers:＂); scanf(＂%d＂,&n); printf(＂input %d numbers:\n＂,n); for(i=0;i<n;i++) scanf(＂%d＂,&a...

攸县19733521139： C语言!!!构建全排列!!!速求!!!要有错排的!!!代码好了有追加分!!! - ？
宇文洪知甘： vc下编译通过 赋运行图 地址:#includechar a; int b[2] = ,x=0; char c[999]; void sr() { do { a = getchar(); if(a>='0' && a { b[0]++; c[x] = a; x++; } else if((a>='a' && a='A' && a b[1]++; } while(a != 10); } void pl() { int i,j,k; for(i=0; i for(j=i; j { if(c[i] { k = c[j]; c[j] ...