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

Question

这不是家庭作业，尽管它看起来像是。我一直在浏览英国计算机奥林匹克竞赛的网站，发现了这个问题（问题 1）：here。我对此感到困惑，我想看看你们是怎么想的。我想不出任何巧妙的方法来将所有内容分组（之后检查它是否是回文很简单，即 originalString == new String(groupedString.Reverse.SelectMany(c => c).ToArray)，假设它是一个字符数组）。

有什么想法吗？谢谢！

工作人员的文本：

A palindrome is a word that shows the same sequence of letters when reversed. If a word can have its letters grouped together in two or more blocks (each containing one or more adjacent letters) then it is a block palindrome if reversing the order of those blocks results in the same sequence of blocks.

For example, using brackets to indicate blocks, the following are block palindromes:

• BONBON can be grouped together as (BON)(BON);

• ONION can be grouped together as (ON)(I)(ON);

• BBACBB can be grouped together as (B)(BACB)(B) or (BB)(AC)(BB) or (B)(B)(AC)(B)(B)

Note that (BB)(AC)(B)(B) is not valid as the reverse (B)(B)(AC)(BB) shows the blocks in a different order.

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

Answer 1

像这样的 BONBON 怎么样...

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);
}

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

Answer 2

不清楚您是想要所有个可能的分组，还是只需要 a 个可能的分组。这是一种方式，脱离我的头脑，你可能会得到 a 分组：

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，它会 return bon。如果你给它 onion，它会还给你 on、i。如果你给它bbacbb，它就会给你b,b,ac.

Answer 3

这应该有效：

   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)

Answer 4

这是我的解决方案（没有 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

Answer 5

And the question is essentially how to generate all of those groups, to then check whether they are palindromes!

我注意到这不一定是最好的策略。首先生成所有组然后检查它们是否是回文比 仅生成回文组 .

效率低得多

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

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

空字符串有多少组？只有空分组；即没有元素的分组。

现在我们假设我们有一个较小问题的解决方案，然后问 "if we had a solution to a smaller problem, how could we use that solution to solve a larger problem?"

好的，假设我们有一个更大的问题。我们有一个包含 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)})");

输出如下；再次注意，我没有过滤掉 "entire string" 块，但这样做很简单。

(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

Answer 6

虽然不像@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 问题的答案。

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

How to get all permutations of groups in a string?

c#

pseudocode