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

Question

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 怎么办？

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

score 18 · Accepted Answer

你应该检查这个答案：Getting every possible permutation of a string or combination including repeat characters in 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]);
        }
    }
}

尽管可以进一步改进内存，但由于此解决方案首先生成内存（数组）的所有解决方案，然后我们才能打印它。但是思路是一样的，就是使用递归算法。

score 3 · Accepted Answer

这闻起来像二进制计数：

001
010
011
100
101
...

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

score 2 · Accepted Answer

排列生成器的 Java 实现：-

public class Permutations {


    public static void permGen(char[] s,int i,int k,char[] buff) {
        if(i<k) {
            for(int j=0;j<s.length;j++) {

                buff[i] = s[j];
                permGen(s,i+1,k,buff);
            }
        }       
        else {

         System.out.println(String.valueOf(buff)); 

        }

    }

    public static void main(String[] args) {
        char[] database = {'a', 'b', 'c'};
        char[] buff = new char[database.length];
        int k = database.length;
        for(int i=1;i<=k;i++) {
            permGen(database,0,i,buff);
        }

}

}

score 0 · Accepted Answer

好的，所以排列的最佳解决方案是递归。假设字符串中有 n 个不同的字母。这将产生 n 个子问题，每个子问题对应于从每个唯一字母开始的每组排列。创建一种方法permutationsWithPrefix(String thePrefix, String theString)来解决这些个别问题。创建另一个方法listPermutations(String theString)，实现将类似于

void permutationsWithPrefix(String thePrefix, String theString) {
   if ( !theString.length ) println(thePrefix + theString);
   for(int i = 0; i < theString.length; i ++ ) {
      char c = theString.charAt(i);
      String workingOn = theString.subString(0, i) + theString.subString(i+1);   
      permutationsWithPrefix(prefix + c, workingOn);
   }
} 

void listPermutations(String theString) {
   permutationsWithPrefix("", theString);
}

score 0 · Accepted Answer

我遇到了这个问题作为面试问题之一。以下是我使用递归针对此问题实施的解决方案。

public class PasswordCracker {

private List<String> doComputations(String inputString) {

    List<String> totalList =  new ArrayList<String>();
    for (int i = 1; i <= inputString.length(); i++) {

        totalList.addAll(getCombinationsPerLength(inputString, i));
    }
    return totalList;

}

private ArrayList<String> getCombinationsPerLength(
        String inputString, int i) {

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

    if (i == 1) {

        char [] charArray = inputString.toCharArray();
        for (int j = 0; j < charArray.length; j++) {
            combinations.add(((Character)charArray[j]).toString());
        }
        return combinations;
    }
    for (int j = 0; j < inputString.length(); j++) {

        ArrayList<String> combs = getCombinationsPerLength(inputString, i-1);
        for (String string : combs) {
            combinations.add(inputString.charAt(j) + string);
        }
    }

    return combinations;
}
public static void main(String args[]) {

    String testString = "abc";
    PasswordCracker crackerTest = new PasswordCracker();
    System.out.println(crackerTest.doComputations(testString));

}
}

score 0 · Accepted Answer

对于任何寻找非递归选项的人，这里有一个数字排列示例（可以很容易地适应char。numberOfAgents是列数，数字集0是numberOfActions：

    int numberOfAgents=5;
    int numberOfActions = 8;
    byte[][]combinations = new byte[(int)Math.pow(numberOfActions,numberOfAgents)][numberOfAgents];

    // do each column separately
    for (byte j = 0; j < numberOfAgents; j++) {
        // for this column, repeat each option in the set 'reps' times
        int reps = (int) Math.pow(numberOfActions, j);

        // for each column, repeat the whole set of options until we reach the end
        int counter=0;
        while(counter<combinations.length) {
            // for each option
            for (byte i = 0; i < numberOfActions; i++) {
                // save each option 'reps' times
                for (int k = 0; k < reps; k++)
                    combinations[counter + i * reps + k][j] = i;
            }
            // increase counter by 'reps' times amount of actions
            counter+=reps*numberOfActions;
        }
    }

    // print
    for(byte[] setOfActions : combinations) {
        for (byte b : setOfActions)
            System.out.print(b);
        System.out.println();
    }

score 0 · Accepted Answer

// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

import java.util.*;
public class Permutation {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("ENTER A STRING");
        Set<String> se=find(in.nextLine());
        System.out.println((se));
    }
    public static Set<String> find(String s)
    {
        Set<String> ss=new HashSet<String>();
        if(s==null)
        {
            return null;
        }
        if(s.length()==0)
        {
            ss.add("");
        }
        else
        {
            char c=s.charAt(0);
            String st=s.substring(1);
            Set<String> qq=find(st);
            for(String str:qq)
            {
                for(int i=0;i<=str.length();i++)
                {
                    ss.add(comb(str,c,i));
                }
            }
        }
        return ss;

    }
    public static String comb(String s,char c,int i)
    {
        String start=s.substring(0,i);
        String end=s.substring(i);
        return start+c+end;
    }

}


// IF YOU NEED REPEATITION USE ARRAYLIST INSTEAD OF SET!!

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

7 回答 7

Related

Reference