生成字符串的排列和组合的聪明方法

15 浏览
0 Comments

生成字符串的排列和组合的聪明方法

String database[] = {'a', 'b', 'c'};

根据给定的database，我想生成以下字符串序列。

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
...

我只能想到一个相当"笨"的解决方案。

public class JavaApplication21 {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        char[] database = {'a', 'b', 'c'};
        String query = "a";
        StringBuilder query_sb = new StringBuilder(query);
        for (int a = 0; a < database.length; a++) {
            query_sb.setCharAt(0, database[a]);
            query = query_sb.toString();                    
            System.out.println(query);            
        }
        query = "aa";
        query_sb = new StringBuilder(query);
        for (int a = 0; a < database.length; a++) {
            query_sb.setCharAt(0, database[a]);    
            for (int b = 0; b < database.length; b++) {    
                query_sb.setCharAt(1, database[b]);    
                query = query_sb.toString();                    
                System.out.println(query);
            }
        }
        query = "aaa";
        query_sb = new StringBuilder(query);
        for (int a = 0; a < database.length; a++) {
            query_sb.setCharAt(0, database[a]);    
            for (int b = 0; b < database.length; b++) {    
                query_sb.setCharAt(1, database[b]);    
                for (int c = 0; c < database.length; c++) {                    
                    query_sb.setCharAt(2, database[c]);                        
                    query = query_sb.toString();                    
                    System.out.println(query);
                }
            }
        }
    }
}

这个解决方案相当笨拙。它在以下几个方面不具备可扩展性：

  1. 如果我增加database的大小会怎么样？
  2. 如果我最终要打印的字符串长度需要是N，会怎么样？

有没有一种更聪明的代码能够以一种真正聪明的方式生成可扩展的排列组合字符串呢？

0

3 答案

0 Comments

这个问题的出现是因为需要找到一种智能的方法来生成字符串的排列和组合。解决方法可以通过使用递归或者使用二进制计数器来实现。

递归方法可以通过以下问题的答案来解决：

- "How do I make this combinations/permutations method recursive?"

- "Find out all combinations and permutations - Java"

- "java string permutations and combinations lookup"

- "http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/"

然而，使用二进制计数器的方法并不适用于这个问题，因为其中的"aa"是一个有效的排列。

相反，可以使用更高的进制数来解决这个问题，例如三进制，如果有三个元素的话可以使用三进制来生成排列和组合。但是这种方法仍然不够可扩展，如果将来的数据库中有四个元素，那么就无法使用三进制来生成排列和组合。

如果数据库中有n个元素，那么可以使用n进制来解决这个问题，这正是问题的提问者所要求的。

解决这个问题的方法可以通过递归或者使用n进制来生成排列和组合。

0
0 Comments

问题的出现原因：该问题的出现原因是需要在Java中生成字符串的排列和组合，但没有一个方便和高效的方法可以实现。

解决方法：下面是一个Java实现的排列生成器的示例代码，可以通过递归来生成给定字符串的所有可能的排列：

public class Permutations {
    public static void permGen(char[] s,int i,int k,char[] buff) {
        if(i



这段代码中的`permGen`方法接受一个字符数组`s`，一个起始索引`i`，一个指定生成排列长度的参数`k`，以及一个用于存储当前排列的字符数组`buff`。通过递归调用，它会生成所有可能的排列，并将它们打印到控制台。


在`main`方法中，我们定义了一个字符数组`database`，并创建了一个与其长度相同的字符数组`buff`。然后，我们使用一个循环来调用`permGen`方法，每次生成不同长度的排列。


使用这个方法，我们可以方便地生成给定字符串的所有排列。
0
0 Comments

智能生成字符串的全排列和组合是一个常见的问题。解决这个问题的方法通常涉及使用递归算法。以下是一个在Java中实现此目标的代码示例：

public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else {
        //initialize our returned list with the number of elements calculated above
        String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);
        //append the sublists to each element
        int arrayIndex = 0;
        for(int i = 0; i < elements.length; i++){
            for(int j = 0; j < allSublists.length; j++){
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }
        return allLists;
    }
}
public static void main(String[] args){
    String[] database = {"a","b","c"};
    for(int i=1; i<=database.length; i++){
        String[] result = getAllLists(database, i);
        for(int j=0; j



这个代码使用了递归算法来生成给定字符串的所有可能排列和组合。它接受一个字符串数组和一个整数作为输入，返回一个包含所有可能排列和组合的字符串数组。代码首先检查输入的长度是否为1，如果是，则直接返回原始字符串数组。否则，它会根据输入的长度计算返回数组的大小，并使用递归调用来获取长度比输入小1的所有可能排列和组合。然后，它将这些子列表与原始字符串数组中的每个元素组合起来，将结果存储在返回数组中。最后，代码通过一个嵌套循环遍历返回数组并打印所有可能的排列和组合。


虽然这个解决方案在内存方面可以进一步改进，因为它先将所有解决方案生成到内存中（数组），然后才能打印出来。但其基本思想是相同的，即使用递归算法。


一个小的改进是将allLists的初始化移到else（主要）部分。


更新过的代码如下：




public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);
        //initialize our returned list with the number of elements calculated above
        String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];
        //append the sublists to each element
        int arrayIndex = 0;
        for(int i = 0; i < elements.length; i++){
            for(int j = 0; j < allSublists.length; j++){
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }
        return allLists;
    }
}
public static void main(String[] args){
    String[] database = {"a","b","c"};
    for(int i=1; i<=database.length; i++){
        String[] result = getAllLists(database, i);
        for(int j=0; j



这个更新的代码将allLists的初始化移到了递归调用之后，这样可以更好地组织代码和减少不必要的内存分配。
0