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

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

## 本文概述

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

``````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``````

## 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``````