使用递归在 C# 中进行排列

• 下载源代码 - 1,012 B
• 下载应用程序 - 2.57 KB

引言

最近，在寻找一种对字符串字符进行解扰的方法时，我偶然发现了一篇 Alexander Bogomolny 的文章，题为“计算和列出所有排列”。这篇文章来自互动数学杂谈和谜题，介绍了三种不同的算法，它们都能够为给定的一组元素生成排列列表。

为了用 C# 3.0 重写几年前用 VBA 为 Microsoft Excel 创建的单词解扰程序，我使用了文章中的三种基于 Java 的算法之一，即递归算法，并用 C# 重写。此外，我添加了一些增强功能，包括递归算法将排列应用于用户输入的字符串字符，并将输入字符串的每个排列返回给用户。

背景

首先，快速复习一下数学知识。排列是一组元素的所有可能组合。例如，给定一组三个整数：{ 0, 1, 2 }，这三个整数有六种可能的排列：{ 012, 021, 102, 120, 201, 210 }。一组元素的排列总数可以表示为 3! 或 n 阶乘，其中 n 代表集合中元素的数量。三个元素有 3! 排列，即 1 x 2 x 3 = 6。四个元素有 4! 排列，即 1 x 2 x 3 x 4 = 24。五个元素有 120；六个元素有 720，以此类推。变化会迅速增加；它们的增长是指数级的。

请注意，Bogomolny 提出的递归算法返回给定元素集合的所有排列，并且不考虑集合中重复的元素，这反过来会产生重复的排列。例如，给定由四个字符组成的集合 { t, e, s, t }，该算法将返回 { test } 两次；一次用于排列 { 0123 }，一次用于 { 3120 }。要使用 C# 计算带重复元素的排列，我建议从 Adrian Akison 撰写的 CodeProject 文章开始，题为“使用 C# 泛型的排列、组合和变体”。

互联网和 CodeProject 上还有许多其他关于排列的综合文章。我不会重复已经写过的内容。本文的目的是演示 Bogomolny 令人费解的简单代码如何生成给定输入字符集合的完整排列列表。

Using the Code

为了演示递归算法，我使用 Microsoft Visual Studio 2008 创建了一个简单的控制台应用程序。本文的源代码由一个包含两个类的单个类 (.cs) 文件组成。编译并执行后，控制台应用程序会要求用户输入一个字符串字符（字母、数字或符号）。应用程序将输入字符串转换为字符数组并存储其长度（输入的字符数）。

class Program
{
    static void Main(string[] args)
    {
        Console.Write("Input String>");
        string inputLine = Console.ReadLine();

        Recursion rec = new Recursion();
        rec.InputSet = rec.MakeCharArray(inputLine);
        rec.CalcPermutation(0);

        Console.Write("# of Permutations: " + rec.PermutationCount);
    }
}

然后，使用递归，应用程序计算给定输入字符数的元素集合的每个可能的排列，作为一系列整数，代表每个字符的初始位置，从 0 开始。例如，用户输入字符串 'ugb'，应用程序从中计算出三个元素从 0 开始的六个可能排列：{ 012, 021, 102, 120, 201, 210 }。然后，应用程序从字符数组 { u, g, b } 中检索与排列对应的各个字符，并将它们返回给用户：{ ugb, ubg, gub, gbu, bug, bgu }。

/// <summary>
/// Algorithm Source: A. Bogomolny, Counting And Listing 
/// All Permutations from Interactive Mathematics Miscellany and Puzzles
/// http://www.cut-the-knot.org/do_you_know/AllPerm.shtml, Accessed 11 June 2009
/// </summary>
class Recursion
{
    private int elementLevel = -1;
    private int numberOfElements;
    private int[] permutationValue = new int[0];

    private char[] inputSet;
    public char[] InputSet
    {
        get { return inputSet; }
        set { inputSet = value; }
    }

    private int permutationCount = 0;
    public int PermutationCount
    {
        get { return permutationCount; }
        set { permutationCount = value; }
    }

    public char[] MakeCharArray(string InputString)
    {
        char[] charString = InputString.ToCharArray();
        Array.Resize(ref permutationValue, charString.Length);
        numberOfElements = charString.Length;
        return charString;
    }

    public void CalcPermutation(int k)
    {
        elementLevel++;
        permutationValue.SetValue(elementLevel, k);

        if (elementLevel == numberOfElements)
        {
            OutputPermutation(permutationValue);
        }
        else
        {
            for (int i = 0; i < numberOfElements; i++)
            {
                if (permutationValue[i] == 0)
                {
                    CalcPermutation(i);
                }
            }
        }
        elementLevel--;
        permutationValue.SetValue(0, k);
    }

    private void OutputPermutation(int[] value)
    {
        foreach (int i in value)
        {
            Console.Write(inputSet.GetValue(i - 1));
        }
        Console.WriteLine();
        PermutationCount++;
    }
}

关注点

如您所见，递归算法可以构成一个有效的单词解扰器的基础。输入字符串 'ugb' 代表乱序单词 'bug'。我的下一篇文章将演示使用 Bogomolny 的递归算法对单词进行解扰。

历史

• 2009 年 6 月 12 日 - 版本 1.0
  • 初始版本