如何获取字符串中组的所有排列

问题本质上是如何生成所有这些组，然后检查它们是否是回文！

我注意到，这不一定是最好的策略。首先生成所有组，然后检查它们是否是回文组比仅生成那些回文组的效率要低得多。

但是本着回答所提问题的精神，让我们递归地解决问题。我将生成所有组;检查一组组是否是回文作为练习。我还将忽略一组组至少包含两个元素的要求;这很容易检查。

优雅

地解决这个问题的方法是递归推理。与所有递归解决方案一样，我们从一个简单的基本情况开始：

空字符串有多少个分组？ 只有空分组;也就是说，其中没有元素的分组。

现在我们假设我们有一个解决较小问题

的解决方案，并问"如果我们有一个解决较小问题的解决方案，我们如何使用该解决方案来解决更大的问题？

好吧，假设我们有一个更大的问题。我们有一个包含 6 个字符的字符串，我们希望生成所有分组。此外，分组是对称的;第一个组与最后一个组的大小相同。通过假设，我们知道如何解决任何较小字符串的问题。

我们按如下方式解决问题。假设字符串是 ABCDEF。 我们从两端剥离 A 和 F，我们解决 BCDE 的问题，它记住我们知道如何通过假设来做，现在我们在每个解决方案前面加上 A 并附加 F。

BCDE 的解决方案是(B)(C)(D)(E), (B)(CD)(E), (BC)(DE), (BCDE) .同样，我们假设我们的归纳假设我们有解决较小问题的方法。 然后，我们将这些与 A 和 F 结合起来，为 ABCDEF 生成解决方案：(A)(B)(C)(D)(E)(F), (A)(B)(CD)(E)(F), (A)(BC)(DE)(F) 和 (A)(BCDE)(F) 。

我们取得了良好的进展。我们完成了吗？ 不。接下来，我们剥离 AB 和 EF，并递归解决 CD 的问题。 我不会费力地完成这项工作。我们完成了吗？不。我们剥离 ABC 和 DEF，递归解决中间空字符串的问题。我们完成了吗？不。(ABCDEF(也是一种解决方案。现在我们完成了。

我希望草图能激发解决方案，现在它很简单。我们从一个辅助函数开始：

    public static IEnumerable<T> AffixSequence<T>(T first, IEnumerable<T> body, T last)
    {
        yield return first;
        foreach (T item in body)
            yield return item;
        yield return last;
    }

这应该很容易理解。现在我们做真正的工作：

    public static IEnumerable<IEnumerable<string>> GenerateBlocks(string s)
    {
        // The base case is trivial: the blocks of the empty string 
        // is the empty set of blocks.
        if (s.Length == 0)
        {
            yield return new string[0];
            yield break;
        }
        // Generate all the sequences for the middle;
        // combine them with all possible prefixes and suffixes.
        for (int i = 1; s.Length >= 2 * i; ++i)
        {
            string prefix = s.Substring(0, i);
            string suffix = s.Substring(s.Length - i, i);
            string middle = s.Substring(i, s.Length - 2 * i);
            foreach (var body in GenerateBlocks(middle))
                yield return AffixSequence(prefix, body, suffix);
        }
        // Finally, the set of blocks that contains only this string
        // is a solution.
        yield return new[] { s };
    }

让我们测试一下。

        foreach (var blocks in GenerateBlocks("ABCDEF"))
            Console.WriteLine($"({string.Join(")(", blocks)})");

输出为

(A)(B)(C)(D)(E)(F)
(A)(B)(CD)(E)(F)
(A)(BC)(DE)(F)
(A)(BCDE)(F)
(AB)(C)(D)(EF)
(AB)(CD)(EF)
(ABC)(DEF)
(ABCDEF)

所以你去吧。

您现在可以检查每个分组是否是回文，但为什么呢？ 上面介绍的算法可以很容易地修改，以消除所有非回文，如果前缀和后缀不相等，只需不递归：

if (prefix != suffix) continue;

该算法现在仅枚举块回文。让我们测试一下：

        foreach (var blocks in GenerateBlocks("BBACBB"))
            Console.WriteLine($"({string.Join(")(", blocks)})");

输出如下;再次注意，我没有过滤掉"整个字符串"块，但这样做很简单。

(B)(B)(AC)(B)(B)
(B)(BACB)(B)
(BB)(AC)(BB)
(BBACBB)

如果您对此主题感兴趣，请考虑阅读我的系列文章，介绍如何使用相同的技术在语言中生成每个可能的树拓扑和每个可能的字符串。它从这里开始：

http://blogs.msdn.com/b/ericlippert/archive/2010/04/19/every-binary-tree-there-is.aspx

这应该有效：

   public List<string> BlockPalin(string s) {
        var list = new List<string>();
        for (int i = 1; i <= s.Length / 2; i++) {
            int backInx = s.Length - i;
            if (s.Substring(0, i) == s.Substring(backInx, i)) {
                var result = string.Format("({0})", s.Substring(0, i));
                result += "|" + result;
                var rest = s.Substring(i, backInx - i);
                if (rest == string.Empty) {
                    list.Add(result.Replace("|", rest));
                    return list;
                }
                else if (rest.Length == 1) {
                    list.Add(result.Replace("|", string.Format("({0})", rest)));
                    return list;
                }
                else {
                    list.Add(result.Replace("|", string.Format("({0})", rest)));
                    var recursiveList = BlockPalin(rest);
                    if (recursiveList.Count > 0) {
                        foreach (var recursiveResult in recursiveList) {
                            list.Add(result.Replace("|", recursiveResult));
                        }
                    }
                    else {
                    //EDIT: Thx to @juharr this list.Add is not needed...
                    //    list.Add(result.Replace("|",string.Format("({0})",rest)));
                        return list;
                    }
                }
            }
        }
        return list;
    }

并像这样称呼它(编辑：再次感谢@juharr，不需要不同的(：

        var x = BlockPalin("BONBON");//.Distinct().ToList();
        var y = BlockPalin("ONION");//.Distinct().ToList();
        var z = BlockPalin("BBACBB");//.Distinct().ToList();

结果：

• x 包含 1 个元素：(BON((BON(
• Y 包含 1 个元素：(ON((I((ON(
Z包含3个元素：(B((BACB((B(，(B((B((
• AC((B((B(和(BB((AC((BB(

虽然不像 @Eric Lippert 提供的那么优雅，但人们可能会发现以下迭代字符串分配免费解决方案很有趣：

struct Range
{
    public int Start, End;
    public int Length { get { return End - Start; } }
    public Range(int start, int length) { Start = start; End = start + length; }
}
static IEnumerable<Range[]> GetPalindromeBlocks(string input)
{
    int maxLength = input.Length / 2;
    var ranges = new Range[maxLength];
    int count = 0;
    for (var range = new Range(0, 1); ; range.End++)
    {
        if (range.End <= maxLength)
        {
            if (!IsPalindromeBlock(input, range)) continue;
            ranges[count++] = range;
            range.Start = range.End;
        }
        else
        {
            if (count == 0) break;
            yield return GenerateResult(input, ranges, count);
            range = ranges[--count];
        }
    }
}
static bool IsPalindromeBlock(string input, Range range)
{
    return string.Compare(input, range.Start, input, input.Length - range.End, range.Length) == 0;
}
static Range[] GenerateResult(string input, Range[] ranges, int count)
{
    var last = ranges[count - 1];
    int midLength = input.Length - 2 * last.End;
    var result = new Range[2 * count + (midLength > 0 ? 1 : 0)];
    for (int i = 0; i < count; i++)
    {
        var range = result[i] = ranges[i];
        result[result.Length - 1 - i] = new Range(input.Length - range.End, range.Length);
    }
    if (midLength > 0)
        result[count] = new Range(last.End, midLength);
    return result;
}

测试：

foreach (var input in new [] { "BONBON", "ONION", "BBACBB" })
{
    Console.WriteLine(input);
    var blocks = GetPalindromeBlocks(input);
    foreach (var blockList in blocks)
        Console.WriteLine(string.Concat(blockList.Select(range => "(" + input.Substring(range.Start, range.Length) + ")")));
}

删除行if (!IsPalindromeBlock(input, range)) continue;将生成 OP 问题的答案。

目前尚不清楚您是想要所有可能的分组，还是只是可能的分组。这是一种方法，在我的头顶上，你可能会得到一个分组：

public static IEnumerable<string> GetBlocks(string testString)
{
    if (testString.Length == 0)
    {
        yield break;
    }
    int mid = testString.Length / 2;
    int i = 0;
    while (i < mid)
    {
        if (testString.Take(i + 1).SequenceEqual(testString.Skip(testString.Length - (i + 1))))
        {
            yield return new String(testString.Take(i+1).ToArray());
            break;
        }
        i++;
    }
    if (i == mid)
    {
        yield return testString;
    }
    else
    {
        foreach (var block in GetBlocks(new String(testString.Skip(i + 1).Take(testString.Length - (i + 1) * 2).ToArray())))
        {
            yield return block;
        }
    }
}

如果你给它bonbon，它会返回bon。如果你给它onion它会还给你on，i。如果你给它bbacbb，它会给你b、b、ac。

这是我

的解决方案(没有VS，所以我使用java做到了(：

int matches = 0;
public void findMatch(String pal) {     
        String st1 = "", st2 = "";
        int l = pal.length() - 1;   
        for (int i = 0; i < (pal.length())/2 ; i ++ ) {
            st1 = st1 + pal.charAt(i);
            st2 = pal.charAt(l) + st2;
            if (st1.equals(st2)) {
                matches++;
                // DO THE SAME THING FOR THE MATCH
                findMatch(st1);
            }
            l--;
        }   
    }

逻辑很简单。我制作了两个字符数组并比较它们以找到每个步骤中的匹配项。关键是你也需要为每场比赛检查同样的事情。

findMatch("bonbon"); // 1
findMatch("bbacbb"); // 3

对于邦邦

来说，这样的事情呢？

string bonBon = "BONBON";

首先检查偶数或奇数的字符数。

bool isEven = bonBon.Length % 2 == 0;

现在，如果它是偶数，则将字符串分成两半。

if (isEven)
{
   int halfInd = bonBon.Length / 2;
   string firstHalf = bonBon.Substring(0, halfInd );
   string secondHalf = bonBon.Substring(halfInd);
}

现在，如果它很奇怪，将字符串分成 3 个字符串。

else
{
   int halfInd = (bonBon.Length - 1) / 2;
   string firstHalf = bonBon.Substring(0, halfInd);
   string middle = bonBon.Substring(halfInd, bonBon.Length - halfInd);
   string secondHalf = bonBon.Substring(firstHalf.Length + middle.length);
}

可能不完全正确，但这是一个开始......仍然必须添加检查它是否真的是一个回文......祝你好运！！