算法设计（字符串的不同排列|S2）

本文概述

C ++
Java
Python3
C#
C ++

【算法设计（字符串的不同排列|S2）】打印具有重复项的字符串的所有不同排列。
例子：

Input : ABCA Output : AABC AACB ABAC ABCA ACBA ACAB BAAC BACA BCAA CABA CAAB CBAA

已经讨论了打印所有不同排列的算法这里。在这里, 我们将讨论另一种方法。首先回想一下我们如何打印输入字符串中没有任何重复的排列。被给这里。现在以字符串" ABAC"为例。假设生成置换时, 假设我们的索引为0, 将其与之后的所有元素交换。当我们达到i = 2时, 我们看到在字符串s [index…i-1]中, 存在一个等于s [i]的索引。因此, 交换它会产生重复的排列。因此, 我们不会交换它。下面将对其进行更好的解释。
插图：让我们用下面的例子来理解。

i = 0 1 2 3 A B A C index = 0, s[0] = A Start swapping s[index] with s[i] following it: i = index + 1 = 1 Since s[index] != s[i], swap and recur.i = 2, s[index] == s[i], don't swapi = 3, s[index] != s[i], swap and recur.

下面的代码执行相同的操作。
C ++

//C++ program to distinct permutations of the string #include < bits/stdc++.h> using namespace std; //Returns true if str[curr] does not matches with any of the //characters after str[start] bool shouldSwap( char str[], int start, int curr) { for ( int i = start; i < curr; i++) if (str[i] == str[curr]) return 0; return 1; } //Prints all distinct permutations in str[0..n-1] void findPermutations( char str[], int index, int n) { if (index> = n) { cout < < str < < endl; return ; } for ( int i = index; i < n; i++) { //Proceed further for str[i] only if it //doesn't match with any of the characters //after str[index] bool check = shouldSwap(str, index, i); if (check) { swap(str[index], str[i]); findPermutations(str, index + 1, n); swap(str[index], str[i]); } } } //Driver code int main() { char str[] = "ABCA" ; int n = strlen (str); findPermutations(str, 0, n); return 0; }

Java

//Java program to distinct permutations of the string public class GFG { //Returns true if str[curr] does not matches with any of the //characters after str[start] static boolean shouldSwap( char str[], int start, int curr) { for ( int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false ; } } return true ; } //Prints all distinct permutations in str[0..n-1] static void findPermutations( char str[], int index, int n) { if (index> = n) { System.out.println(str); return ; } for ( int i = index; i < n; i++) { //Proceed further for str[i] only if it //doesn't match with any of the characters //after str[index] boolean check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1 , n); swap(str, index, i); } } } static void swap( char [] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; } //Driver code public static void main(String[] args) { char str[] = { 'A' , 'B' , 'C' , 'A' }; int n = str.length; findPermutations(str, 0 , n); } }

Python3

# Python3 program to distinct # permutations of the string # Returns true if str[curr] does not # matches with any of the characters # after str[start] def shouldSwap(string, start, curr): for i in range (start, curr): if string[i] = = string[curr]: return 0 return 1 # Prints all distinct permutations # in str[0..n-1] def findPermutations(string, index, n): if index> = n: print (''.join(string)) return for i in range (index, n): # Proceed further for str[i] only # if it doesn't match with any of # the characters after str[index] check = shouldSwap(string, index, i) if check: string[index], string[i] = string[i], string[index] findPermutations(string, index + 1 , n) string[index], string[i] = string[i], string[index] # Driver code if __name__ = = "__main__" : string = list ( "ABCA" ) n = len (string) findPermutations(string, 0 , n)# This code is contributed by Rituraj Jain

//C# program to distinct permutations //of the string using System; class GFG { //Returns true if str[curr] does //not matches with any of the //characters after str[start] static bool shouldSwap( char []str, int start, int curr) { for ( int i = start; i < curr; i++) { if (str[i] == str[curr]) { return false ; } } return true ; } //Prints all distinct permutations //in str[0..n-1] static void findPermutations( char []str, int index, int n) { if (index> = n) { Console.WriteLine(str); return ; } for ( int i = index; i < n; i++) { //Proceed further for str[i] only //if it doesn't match with any of //the characters after str[index] bool check = shouldSwap(str, index, i); if (check) { swap(str, index, i); findPermutations(str, index + 1, n); swap(str, index, i); } } } static void swap( char [] str, int i, int j) { char c = str[i]; str[i] = str[j]; str[j] = c; } //Driver code public static void Main() { char []str = { 'A' , 'B' , 'C' , 'A' }; int n = str.Length; findPermutations(str, 0, n); } } //This code is contributed //by 29AjayKumar

输出如下

ABCA ABAC ACBA ACAB AACB AABC BACA BAAC BCAA CBAA CABA CAAB

更好的方法：
生成所有不同的字符串只是使用一些if条件。上面的技术在递归内部使用了一个额外的循环, 这会导致大量的时间复杂性成本。相反, 我们可以通过很少的预处理来改进它。我们首先对给定的字符串进行排序, 然后应用以下代码。
以下是上述想法的实现：
C ++

//C++ program to print all the permutation //of the given string. #include < algorithm> #include < iostream> #include < string> using namespace std; //count of total permutations int total = 0; void permute( int i, string s) { //base case if (i == (s.length() - 1)) { cout < < s < < endl; total++; return ; }char prev = '*' ; //loop from j = 1 to length of string for ( int j = i; j < s.length(); j++) { string temp = s; if (j> i & & temp[i] == temp[j]) continue ; if (prev != '*' & & prev == s[j]) { continue ; }//swap the elements swap(temp[i], temp[j]); prev = s[j]; //recursion call permute(i + 1, temp); } } //Driver code int main() { string s = "abca" ; //sort sort(s.begin(), s.end()); //Function call permute(0, s); cout < < "Total distinct permutations = " < < total < < endl; return 0; } //This code is contributed by risingStark.

输出如下