c# - 加扰字符串

Question

如何对如下所示的字符串进行加扰，以实现所有可能的排列？是否有这种努力的 LINQ 方法？我搜索了谷歌，但在上面找不到任何东西。

STRING = "Little Red Riding Hood"

Answer 1

这是我过去使用过的一个优秀的置换库。这篇文章包含一个代码片段，我相信它会很好地满足您的需求（我已经稍微适应了）：

var inputSet = myString.ToCharArray();
var P2 = new Permutations<char>(inputSet, 
      GenerateOption.WithRepetition);
string format2 = "Permutations of {{A A C}} with Repetition; size = {0}";
Console.WriteLine(String.Format(format2, P2.Count));
foreach(IList<char> p in P2) {
  Console.WriteLine(String.Format("{{{0} {1} {2}}}", p[0], p[1], p[2]));
}

Answer 2

C++ 标准模板库 (STL) 中有一些方法，但我相信这些方法无法从 C# 访问（以任何方式）。我相信您必须为 STL 编写一个小的 C++ 包装器并从 C# 调用它；或在 C# 中编码排列。

更新：

生成 N 个项目的所有排列是旅行商问题 (TSP) 的必要前奏。这方面的算法遍布网络，这将解释如何在各种可能的顺序和并行算法中生成排列。

Answer 3

您想对字符串的字符进行Knuth/Fisher-Yates 洗牌。

这里有一堆 C# 实现，你可以适应字符串而不是数组：使用 Random 和 OrderBy 是一个好的 shuffle 算法吗？

Answer 4

这是一个完整的示例程序：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var sentences = new List<string>
            {
                "Little Red Riding Hood",
                "Three Little Pigs",
                "Jack and the Beanstalk"
            };

            foreach (var sentence in sentences)
            {
                Console.WriteLine("----------------------------------");

                foreach (var permutation in Permute(sentence.Split(' ')))
                {
                    foreach (string word in permutation)
                    {
                        Console.Write(word + " ");
                    }

                    Console.WriteLine();
                }
            }

            // If you want to put all the permutations for all the sentences into a List<string>, you can just do this:

            List<string> permutations = new List<string>();

            foreach (var sentence in sentences)
            {
                permutations.AddRange(Permute(sentence.Split(' ')).Select(perm => string.Join(" ", perm)));
            }

            Console.WriteLine("The total number of perms is: " + permutations.Count);
        }

        /// <summary>
        /// Provides a sequence of enumerators for obtaining all permutations of a sequence.
        /// Each enumeration in the returned sequence itself enumerates one of the permutations of the input sequence.
        /// Use two nested foreach statements to visit each item in each permuted sequence.
        /// </summary>

        public static IEnumerable<IEnumerable<T>> Permute<T>(IEnumerable<T> sequence)
        {
            return permute(sequence, sequence.Count());
        }

        // Returns an enumeration of enumerators, one for each permutation of the input.

        private static IEnumerable<IEnumerable<T>> permute<T>(IEnumerable<T> sequence, int count)
        {
            if (count == 0)
            {
                yield return new T[0];
            }
            else
            {
                int startingElementIndex = 0;

                foreach (T startingElement in sequence)
                {
                    IEnumerable<T> remainingItems = allExcept(sequence, startingElementIndex);

                    foreach (IEnumerable<T> permutationOfRemainder in permute(remainingItems, count - 1))
                    {
                        yield return concat<T>(new T[] { startingElement }, permutationOfRemainder);
                    }

                    ++startingElementIndex;
                }
            }
        }

        // Implements the recursive part of Permute<T>

        private static void permute<T>(T[] items, int item, T[] permutation, bool[] used, Action<T[]> output)
        {
            for (int i = 0; i < items.Length; ++i)
            {
                if (!used[i])
                {
                    used[i] = true;
                    permutation[item] = items[i];

                    if (item < (items.Length - 1))
                    {
                        permute(items, item + 1, permutation, used, output);
                    }
                    else
                    {
                        output(permutation);
                    }

                    used[i] = false;
                }
            }
        }

        // Enumerates over all items in the input, skipping over the item with the specified index.

        private static IEnumerable<T> allExcept<T>(IEnumerable<T> input, int indexToSkip)
        {
            int index = 0;

            foreach (T item in input)
            {
                if (index != indexToSkip)
                {
                    yield return item;
                }

                ++index;
            }
        }

        // Enumerates over contents of two lists sequentially.

        private static IEnumerable<T> concat<T>(IEnumerable<T> a, IEnumerable<T> b)
        {
            foreach (T item in a)
            {
                yield return item;
            }

            foreach (T item in b)
            {
                yield return item;
            }
        }
    }
}