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

2021年4月13日09:37:16 发表评论 699 次浏览

本文概述

打印具有重复项的字符串的所有不同排列。

例子：

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 swap

i = 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#

//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.

输出如下

aabc
aacb
abac
abca
acba
acab
baac
baca
bcaa
caba
caab
cbaa
Total distinct permutations = 12

时间复杂度：如果我们将字符串的长度设为N, 那么我的代码的复杂度将为O(N log N)进行排序, 而O(N * N！)进行置换。总时间复杂度为O(N log N + N * N！), 实际上仅是O(N * N！)。

本文作者：ekta1994.

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: