生成字符串排列和组合的智能方法

algorithm java permutation combinations

2022-09-03 13:20:15

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

解决方案非常愚蠢。从某种意义上说，它是不可扩展的

如果我增加的大小呢？database
如果我的最终目标打印字符串长度需要为 N，该怎么办？

是否有任何智能代码可以以非常智能的方式生成可扩展的排列和组合字符串？

答案 1

您应该检查以下答案：获取字符串或组合的每个可能的排列，包括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<result.length; j++){
            System.out.println(result[j]);
        }
    }
}

尽管可以进一步改进内存，因为此解决方案首先生成内存的所有解决方案（数组），然后再打印它。但想法是一样的，那就是使用递归算法。

答案 2

这闻起来像是用二进制计数：

001
010
011
100
101
...

我的第一个直觉是使用二进制计数器作为字符的“位图”来生成这些可能的值。但是，这里有几个建议使用递归的相关问题的精彩答案。看