全排列 Print all distinct permutations of a given string with duplicates

http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html
http://*.com/questions/9148543/program-to-print-permutations-of-given-elements
http://www.cnblogs.com/guxuanqing/p/5904092.html
非常感谢作者！
// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>
 
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
http://blog.csdn.net/xiazdong/article/details/7986015
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s
", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));//for循环将begin~end中的每个数放到begin位置中去
          permute(a, l+1, r);//假设begin位置确定，那么对begin+1~end中的数继续递归
          swap((a+l), (a+i)); //backtrack //换过去后再还原
       }
   }
}
 
/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}
 
 
Algorithm Paradigm: Backtracking

Time Complexity: O(n*n!)  Note that there are n! permutations and it requires O(n) time to print a a permutation.Note : The above solution prints duplicate 
permutations if there are repeating characters in input string. Please 
see below link for a solution that prints only distinct permutations 
even if there are duplicates in input.
 
// Program to print all permutations of a string in sorted order.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* Following function is needed for library function qsort(). */
int compare(const void *a, const void * b)
{
    return ( *(char *)a - *(char *)b );
}
 
// A utility function two swap two characters a and b
void swap(char* a, char* b)
{
    char t = *a;
    *a = *b;
    *b = t;
}
 
// This function finds the index of the smallest character
// which is greater than 'first' and is present in str[l..h]
int findCeil(char str[], char first, int l, int h)
{
    // initialize index of ceiling element
    int ceilIndex = l;
 
    // Now iterate through rest of the elements and find
    // the smallest character greater than 'first'
    for (int i = l+1; i <= h; i++)
        if (str[i] > first && str[i] < str[ceilIndex])
            ceilIndex = i;
 
    return ceilIndex;
}
 
// Print all permutations of str in sorted order
void sortedPermutations(char str[])
{
    // Get size of string
    int size = strlen(str);
 
    // Sort the string in increasing order
    qsort(str, size, sizeof( str[0] ), compare);
 
    // Print permutations one by one
    bool isFinished = false;
    while (!isFinished)
    {
        // print this permutation
        static int x = 1;
        printf("%d  %s 
", x++, str);
 
        // Find the rightmost character which is smaller than its next
        // character. Let us call it 'first char'
        int i;
        for (i = size - 2; i >= 0; --i)
            if (str[i] < str[i+1])
                break;
 
        // If there is no such chracter, all are sorted in decreasing order,
        // means we just printed the last permutation and we are done.
        if (i == -1)
            isFinished = true;
        else
        {
            // Find the ceil of 'first char' in right of first character.
            // Ceil of a character is the smallest character greater than it
            int ceilIndex = findCeil(str, str[i], i + 1, size - 1);
 
            // Swap first and second characters
            swap(&str[i], &str[ceilIndex]);
 
            // Sort the string on right of 'first char'
            qsort(str + i + 1, size - i - 1, sizeof(str[0]), compare);
        }
    }
}
 
// Driver program to test above function
int main()
{
    char str[] = "ACBC";
    sortedPermutations( str );
    return 0;
}
 
针对含有重复串的更精简的方法：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main ()
{
    char str[] = "ABA";
    int len = strlen (str);
    void permute (char *, int, int);
    permute (str, 0, len - 1);
    return 0;
}
void permute (char *A, int l, int r)
{
    void swap (char *, int, int);
    int i;
    if (l == r)                    // Only 1 char left, print the permutation
    {
        printf ("%s
", A);
    }
    else
    {
        for (i = l; i <= r; i++)
        {
            if (i == l)
                permute (A, l + 1, r);
            else if (A[l] == A[i])
            {
                continue;
            }
            else
            {
                swap (A, l, i);
                permute (A, l + 1, r);
                swap (A, l, i);
            }
        }
    }
}
void swap (char *A, int l, int i)
{
    int tmp = A[l];
    A[l] = A[i];
    A[i] = tmp;
}
全排列 Print all distinct permutations of a given string with duplicates

相关推荐
