How Can Recursive Algorithms Generate All Permutations of Strings and Integers?

The arrangement algorithm of the string and integer

In programming interviews, a common challenge is to generate all possible arranges of a given string or integer. This may involve recursive use.

Understand Principles

Recursively include two key steps:

Initial steps: For a single element, arrangement is the element itself.

1. Sub -step: For the element collection, each arrangement combination includes each element, and the surplus element.
Human language example

A single element:

Two elements:

<code>perm(a) -> a</code>

Three elements:

<code>perm(ab) ->
a + perm(b) -> ab
b + perm(a) -> ba</code>

The recursive algorithm in the pseudo code

C# implementation

<code>perm(abc) ->
a + perm(bc) -> abc, acb
b + perm(ac) -> bac, bca
c + perm(ab) -> cab, cba</code>

This C# realizes recursive and exchange to effectively generate all arrangements.

<code>generatePermutations(permutation) {
  if (permutation 的长度 为 0) {
    打印 permutation
    返回
  }
  对于 permutation 中的每个元素 element:
    创建一个新的排列 newPermutation，移除 element
    将 element 添加到 generatePermutations(newPermutation) 的结果的前面
}</code>

The two elements in the array of the function switch, while the recursive function traverses all possible arrangements. Backback steps () ensure that the array returns to the previous state after processing a arrangement in order to generate the next arrangement.

This Revied Answer Provides a More Concise and Accurate Explanation of the Recursive Permutation Algorithm, Including A Clearer Pseudocode Reposition and AN Functional C# Implementation with Comments. The Image Remains in ITS Original format and local.

public static void GeneratePermutations(char[] list) {
    int x = list.Length - 1;
    GeneratePermutations(list, 0, x);
}

private static void GeneratePermutations(char[] list, int k, int m) {
    if (k == m) {
        Console.WriteLine(new string(list)); //输出排列
    } else {
        for (int i = k; i <= m; i++) {
            Swap(list, i, k);
            GeneratePermutations(list, k + 1, m);
            Swap(list, i, k); // 回溯，恢复原始顺序
        }
    }
}

private static void Swap(char[] list, int i, int j) {
    char temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}

The above is the detailed content of How Can Recursive Algorithms Generate All Permutations of Strings and Integers?. For more information, please follow other related articles on the PHP Chinese website!