问：查找字符串的所有排列的程序。

17 Mar 2025 | 4 分钟阅读

要解决这个问题，我们需要理解回溯的概念。

根据回溯算法

将一个字符固定在第一个位置，并将其余的字符与第一个字符进行交换。例如，在 ABC 中，在第一次迭代中，通过分别交换 A 与 A、B 和 C，形成了三个字符串：ABC、BAC 和 CBA。
对剩余的字符重复步骤 1，例如固定第二个字符 B，依此类推。
现在再次交换以返回到之前的位置。例如，从 ABC 开始，我们通过再次固定 B 来形成 ABC，然后我们回溯到之前的位置，并将 B 与 C 交换。所以，现在我们得到了 ABC 和 ACB。
对 BAC 和 CBA 重复这些步骤，以获得所有排列。

Program to find all the permutations of a string

算法

定义一个字符串。
固定一个字符并交换剩余的字符。
为剩余的字符调用 generatePermutation()。
回溯并再次交换字符。

解决方案

Python

#Function for generating different permutations of the string
def generatePermutation(string,start,end):
    current = 0;
    #Prints the permutations
    if(start == end-1):
        print(string);
    else: 
        for current in range(start,end):

       #Swapping the string by fixing a character
            x = list(string);
            temp = x[start];
            x[start] = x[current];
            x[current] = temp;

      #Recursively calling function generatePermutation() for rest of the characters

            generatePermutation("".join(x),start+1,end);
            #Swapping the string by fixing a character
            temp = x[start];
            x[start] = x[current];
            x[current] = temp;

str = "ABC"
n = len(str);
print("All the permutations of the string are: ");
generatePermutation(str,0,n);

输出

All the permutations of the string are: 
ABC
ACB
BAC
BCA
CBA
CAB

C

#include<stdio.h>
#include<string.h>
//Declaring generatePermutation()
void generatePermutation(char * , int , int );

int main()
{
  char str[] = "ABC";
  int n =strlen(str);
  printf("All the permutations of the string are: \n");
  generatePermutation(str,0,n);
}

//Function for generating different permutation of the string.
void generatePermutation(char *str,const int start, int end)
{
  char temp;
  int i,j;
  for(i = start; i < end-1; ++i){
  for(j = i+1; j < end; ++j)
  {
   //Swapping the string by fixing a character
    temp = str[i];
  str[i] = str[j];
    str[j] = temp;
    //Recursively calling function generatePermutation() for rest of the characters
  generatePermutation(str , i+1 ,end);
    //Backtracking and swapping the characters again
    temp = str[i];
    str[i] = str[j];
    str[j] = temp;
  }
  }
  //Print the permutations
  printf("%s\n",str);
}

输出

All the permutations of the string are: 
ABC
ACB
BAC
BCA
CBA
CAB

JAVA

public class PermuteString {
    //Function for swapping the characters at position I with character at position j
    public static String swapString(String a, int i, int j) {
        char[] b =a.toCharArray();
        char ch;
        ch = b[i];
        b[i] = b[j];
        b[j] = ch;
        return String.valueOf(b);
    }
    
    public static void main(String[] args)
    {
        String str = "ABC";
        int len = str.length();
        System.out.println("All the permutations of the string are: ");
        generatePermutation(str, 0, len);
    }
    
    //Function for generating different permutations of the string
    public static void generatePermutation(String str, int start, int end)
    {
        //Prints the permutations
        if (start == end-1)
            System.out.println(str);
        else
        {
            for (int i = start; i < end; i++)
            {
                //Swapping the string by fixing a character
                str = swapString(str,start,i);
                //Recursively calling function generatePermutation() for rest of the characters 
                generatePermutation(str,start+1,end);
                //Backtracking and swapping the characters again.
                str = swapString(str,start,i);
            }
        }
    }
}

输出

All the permutations of the string are: 
ABC
ACB
BAC
BCA
CBA
CAB

C#

using System;                    
public class Program
{
    //Function for swapping the characters at position I with character at position j
    public static String swapString(String a, int i, int j) {
        char[] b =a.ToCharArray();
        char ch;
        ch = b[i];
        b[i] = b[j];
        b[j] = ch;
        //Converting characters from array into single string
        return string.Join("",b);
    }
    
    public static void Main()
    {
        String str = "ABC";
        int len = str.Length;
        Console.WriteLine("All the permutations of the string are: ");
        generatePermutation(str, 0, len);
        
    }

    //Function for generating different permutations of the string
    public static void generatePermutation(String str, int start, int end)
    {
        //Prints the permutations
        if (start == end-1)
            Console.WriteLine(str);
        else
        {
            for (int i = start; i < end; i++)
            {
                //Swapping the string by fixing a character
                str = swapString(str,start,i);
                //Recursively calling function generatePermutation() for rest of the characters 
                generatePermutation(str,start+1,end);
                //Backtracking and swapping the characters again.
                str = swapString(str,start,i);
            }
        }
    }
}

输出

All the permutations of the string are: 
ABC
ACB
BAC
BCA
CBA
CAB

PHP

<!DOCTYPE html> 
<html> 
<body> 
<?php 

  //Function for generating different permutations of the string
function generatePermutation($string,$start,$end){
  if($start == $end-1){
    echo "$string <br>";
  }
  else{
    for($i = $start; $i < $end; $i++){
      //Swapping the string by fixing a character
      $temp = $string[$start];
      $string[$start] = $string[$i];
      $string[$i] = $temp;
     //Recursively calling function generatePermutation() for rest of the characters
      generatePermutation($string,$start+1,$end);
      //Backtracking and swapping the characters again.
      $temp = $string[$start];
      $string[$start] = $string[$i];
      $string[$i] = $temp;
    }
  }
}
$str = "ABC";
$n = strlen($str);
echo "All the permutations of the string are: <br>";
generatePermutation($str,0,$n);
?> 
</body> 
</html> 

输出

All the permutations of the string are: 
ABC
ACB
BAC
BCA
CBA
CAB

下一个主题程序列表

问：查找字符串的所有排列的程序。

算法

解决方案

Python

C

JAVA

C#

PHP

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

程序

问：查找字符串的所有排列的程序。

算法

解决方案

Python

C

JAVA

C#

PHP

相关帖子

计算圆锥体积的程序

右旋数组元素的程序

打印给定数字的排列 (nPr) 的程序

查找字符串中重复单词的程序

确定给定字符串是否为回文串的程序

计算直角三角形面积的程序

查找字符串反转的程序

检查迪沙里数（Disarium number）的程序

从单链表中查找最大值和最小值节点的程序

确定给定矩阵是否为单位矩阵的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器