本文概述
- C ++
- Java
- Python3
- C#
- C ++
例子:
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#
//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.
推荐阅读
- JavaScript中var和let之间有什么区别()
- 竞争编程的按位技巧详细指南
- 如何在Unix或Linux中使用管道()
- Java编程面试常见问题分享和解析S2
- 用于数据分析的Violin Plot用法详解
- ==和is运算符在Python中的区别
- jQuery post()方法用法示例介绍
- 8085程序将灰度数字转换为二进制
- 算法题(Knight巡回问题的Warnsdorff算法实现)