如何使用不同的“r”数字制作所有字符串组合？

Question

我想编写一个函数，它接受一个“整数”和一个“字符串数组”，然后返回所有可能的组合。考虑到所有字符串都是不同的这是一个例子：ArrayList<Strings> strings={a,b,c}int n= strings.size();k= 1;String sol="";while(k!=n+1){sol+=function(strings,k);//<== this is the problemk++;}String[] solution= sol.split(" ");并在删除重复元素之后：//Solution expected:={a,b,c,ab,bc,ac,abc} //the elements should not be repeated

Answer 1

现在这是获取字符串排列的一个有趣的转折，说起来容易做起来难。无论如何，如果您确实有一种方法可以根据为每个排列提供的最小/最大长度值为您提供所需的排列，那么实现起来相对简单，而且我确信仅StackOverflow就有很多这样的代码示例。

通常排列是在简单的字符串上完成的，"abc"而不是包含在某种类型的单个字符/字符串集合中的元素，如{'a', 'b', 'c'}或{"a", "b", "c"}。为了有效地获得所需的排列，您需要将 ArrayList 元素转换为字符串，以便{"a", "b", "c"}将"abc". 除非每个元素实际上包含多个字符串字符，否则在集合中继续操作是没有意义的，因此将集合转换为字符串是有意义的。

首先，您需要一种执行字符串排列的方法，我确信 StackOverflow 中有很多方法可以解决。在任何情况下，我都会为您提供我对排列方法的再现，该方法允许您提供一个字符串，提供每个排列所需的字符长度，并删除重复项（或不删除）。该方法只接受一个字符串，以保持方法的灵活性。然而，它确实返回一个 String 的 ArrayList，您当然可以通过对代码进行一些修改来更改为返回您喜欢的任何内容。如果您确实更改了代码，请记住该方法是递归的：

/**

 * This method will generate all possible permutations of the supplied input

 * string and return all those permutations within an String

 * ArrayList.<br><br>

 *

 * @param inputString     (String) The string to acquire permutations

 *                        from.<br>

 *

 * @param length          (Integer) The desired min/max string length of

 *                        returned permutations. In other words, if you only

 *                        want all permutations consisting of 3 characters

 *                        then supply the number 3. If you want all possible

 *                        permutations to be returned then supply the number

 *                        0.<br>

 * 

 * @param removeDuplicates (Boolean) Supply boolean true to ensure there will 

 * be no duplicate permutations within the returned ArrayList. Supply false if 

 * duplicates are desired. You can get duplicate permutations if there are 

 * duplicate characters within the supplied input string, for example:<pre>

 * 

 *      "aabbcc"

 * 

 * can return these permutations: 

 * 

 *      a, a, b, b, c, c            1 Character Permutations. See the Duplicates?

 * 

 *      aa, ab, ac, aa, ab, ac,     2 Character Permutations

 *      ba, bb, bc, ba, bb, bc,         See the Duplicates?

 *      ca, cb, cc, ca, cb, cc

 *

 *      aab, aac, aba, abb, abc,    3 Character Permutations

 *      aca, acb, acc, aab, aac,        See the Duplicates?

 *      aba, abb, abc, aca, acb, 

 *      acc, baa, bab, bac, bba, 

 *      bbc, bca, bcb, bcc, baa, 

 *      bab, bac, bba, bbc, bca, 

 *      bcb, bcc, caa, cab, cac, 

 *      cba, cbb, cbc, cca, ccb, 

 *      caa, cab, cac, cba, cbb, 

 *      cbc, cca, ccb

 * 

 * However if boolean true is supplied to remove duplicates the results would 

 * be:

 *      

 *      a, b, c                     1 Character Max Permutations. No Duplicates.

 * 

 *      aa, ab, ac, ba, bb, bc,     2 Character Max Permutations

 *      ca, cb, cc                          No Duplicates

 *      

 *      aab, aac, aba, abb, abc,    3 Character Max Permutations

 *      aca, acb, acc, baa, bab,            No Duplicates

 *      bac, bba, bbc, bca, bcb, 

 *      bcc, caa, cab, cac, cba, 

 *      cbb, cbc, cca, ccb</pre>

 * 

 * 

 * @param recursiveResult (String) FOR INTERNAL RECURSIVE USE ONLY! DO NOT

 *                        SUPPLY A ARGUMENT HERE!<br>

 *

 * @return (String ArrayList)

 */

public ArrayList<String> getPermutations(String inputString, final int length, 

        boolean removeDuplicates, String... recursiveResult) {

    String currentResult = "";

    if (recursiveResult.length > 0) {

        currentResult = recursiveResult[0];

    }

    //Convert the inputString to a ArrayList of characters...

    ArrayList<Character> possibleChars = new ArrayList<>(inputString.length());

    for (int i = 0; i < inputString.length(); i++) {

        possibleChars.add(inputString.charAt(i));

    }

    ArrayList<String> result = new ArrayList<>(possibleChars.size());

    for (char append : possibleChars) {

        String permutation = currentResult + append; //create a new string with an additional character

        if (permutation.length() == length || length == 0) {

            result.add(permutation); //add the permutation to the result

        }

        if (possibleChars.size() > 0) {

            //make a new list with the appendable characters

            ArrayList<Character> possibleCharsUpdated = (ArrayList) possibleChars.clone();

            //from that list, exclude the character we just appended

            possibleCharsUpdated.remove(new Character(append));

            //Convert the new character ArrayList to a String

            //of characters for the recursion...

            String passToRecursion = "";

            for (int i = 0; i < possibleCharsUpdated.size(); i++) {

                passToRecursion += possibleCharsUpdated.get(i);

            }

            //merge the result of a recursive call of this method and the result we already had

            result.addAll(getPermutations(passToRecursion, length, true, permutation));

        }

    }

    // Remove duplicates if desired...

    // LinkedHashSet doesn't allow for Duplicates 

    // and automatically removes them.

    if (removeDuplicates) {

        ArrayList<String> tmpArray = new ArrayList<>(new LinkedHashSet<>(result));

        result.clear();

        result.addAll(tmpArray);

        tmpArray.clear();

    }

    return result;

}

现在要从您提供的内容中获得您想要的结果，它会是这样的：

// Create String ArrayList

ArrayList<String> strings = new ArrayList<>();

strings.add("a"); strings.add("b"); strings.add("c");

// Convert ArrayList to a simple string

String stringToPermutate = String.join("", strings);

// Hold the number of elements within the strings ArrayList

int n = strings.size();

// Counter for while loop condition which will

// ultimately determine the Permutation Character

// Length for each iteration within the WHILE loop.

int k = 1;

// Prepare to build a result string that will hold

// the result from each call to the getPermutations

// method (which by the way is a recursive method).

StringBuilder sol = new StringBuilder();

while (k <= n) {

    // Call method to permutate our simple string based

    // on the Permutation Character Length stipulated by k

    ArrayList<String> permutations = getPermutations(stringToPermutate, k, true);

    // Convert ArrayList to a comma (, ) delimited string

    String listToString = String.join(", ", permutations); 

    // Ternary used here instead of IF/ELSE

    sol.append(sol.toString().equals("") ? listToString : ", " + listToString);

    // Increment counter

    k++;

}

// Split the contents of sol into a string Array

String[] solution = sol.toString().split(", ");

// Print solution String Array to Console window.

System.out.println(Arrays.toString(solution));

这是您最终应该在控制台窗口中显示的内容：

[a, b, c, ab, ac, ba, bc, ca, cb, abc, acb, bac, bca, cab, cba]