在字符串中生成字符组合不能完全起作用，为什么？ [英] Generating character combination in a string doesn't work entirely, why?

问题描述

我正在尝试生成字符串中所有字符的组合。因此，第一个参数是给定的字符串，第二个参数是字母数。所以 combinations（ ab，2）应该给我 aa，ab，ba，bb 和 combinations（ abc，2）应该给我 aa，ab，ac，ba，bb，bc，ca，cb，cc ，等等。

I'm trying to generate all combinations of the characters in a string. So the first parameter is the string given and the second parameter is the number of letters. So combinations("ab",2) should give me aa, ab, ba, bb and combinations("abc",2) should give me aa, ab, ac, ba, bb, bc, ca, cb, cc, etc.

在第一种情况下，我当前的代码为我提供了 aa，ab，bb （因此它跳过了 ba ）。
这是我的代码：

In the first case my current code gives me aa, ab, bb (so it skips ba). This is my code:

        public static void combinations(String s, int n)
        {
            combinations(s,"",n);
        }


        public static void combinations(String s, String prfx, int n)
        {
            if(n == 0)
            {
                System.out.println(prfx);
            }

            else
            {
                for(int i = 0; i < s.length(); i++)
                {
                    combinations(s.substring(i), prfx + s.charAt(i), n-1);

                }
            }
        }

什么是我做错了吗？如果您不只是给我正确的答案，还请给我一些解释，以便我可以借鉴，我将不胜感激，因为我不太擅长递归。谢谢。

What am I doing wrong? I would appreciate it if you don't just give me the correct answer, but also give me some explanation so I can learn from it, because I'm not so good at recursion. Thanks.

推荐答案

问题的根源在这里：

  combinations(s.substring(i), prfx + s.charAt(i), n-1);
               ^^^^^^^^^^^^^^

您要遍历字符串中的字符并依次使用每个字符作为前缀，然后进行递归调用以构建其余字符串的组合。但是，如果您仅将原始字符串的子字符串传递给递归调用，则不会生成所有可能的排列。在上述情况下，如您所见，它跳过了 ba，因为当循环到达字符串 ab的第二个字符时（当循环计数器 i 为1时） ），则进行此递归调用： combinations（ b， + b，1）。只能生成 bb，不能生成 ba。如果它是 combinations（ ab， + b，1），则将同时获得预期的组合 ba和 bb。

You want to loop through the characters in the string and use each character in turn as prefix, then make a recursive call to build the combinations for the rest of the string. However, if you only pass in a substring of the original string into the recursive call, it won't generate all possible permutations. In the above case, as you observed, it skips "ba" because when the loop gets to the 2nd character of the string "ab" (when the loop counter i is 1), this recursive call is made: combinations("b", "" + "b", 1). Which can only generate "bb", not "ba". If it were combinations("ab", "" + "b", 1) instead, you would get both of the expected combinations "ba" and "bb".

因此，您需要将整个字符串传递到每个递归调用中：

So you need to pass the whole string into each recursive call:

  combinations(s, prfx + s.charAt(i), n-1);

这篇关于在字符串中生成字符组合不能完全起作用，为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！