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

Smart way to generate permutation and combination of String

提问by Cheok Yan Cheng

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

I would like to generate the following strings sequence, based on given database.

我想根据给定的database.

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

I can only think of a pretty "dummy" solution.

我只能想到一个非常“虚拟”的解决方案。

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

The solution is pretty dumb. It is not scale-able in the sense that

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

1. What if I increase the size of database?
2. What if my final targeted print String length need to be N?

1. 如果我增加database?
2. 如果我的最终目标打印字符串长度需要为 N 怎么办？

Is there any smart code, which can generate scale-able permutation and combination string in a really smart way?

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

采纳答案by justhalf

You should check this answer: Getting every possible permutation of a string or combination including repeated characters in Java

您应该检查这个答案：在 Java 中获取字符串或组合的所有可能排列，包括重复字符

To get this code:

要获取此代码：

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

Although further improvement in memory could be made, since this solution generates all solution to memory first (the array), before we can print it. But the idea is the same, which is to use recursive algorithm.

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

回答by dj_segfault

This smells like counting in binary:

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

• 001
• 010
• 011
• 100
• 101
• ...

• 001
• 010
• 011
• 100
• 101
• ...

My first instinct would be to use a binary counter as a "bitmap" of characters to generate those the possible values. However, there are several wonderful answer to related questions here that suggest using recursion. See

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

• 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/

• 如何使这种组合/排列方法递归？
• 找出所有组合和排列 - Java
• java字符串排列组合查找
• http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

回答by Jesse Nelson

Ok, so the best solution to permutations is recursion. Say you had n different letters in the string. That would produce n sub problems, one for each set of permutations starting with each unique letter. Create a method permutationsWithPrefix(String thePrefix, String theString)which will solve these individual problems. Create another method listPermutations(String theString)a implementation would be something like

好的，所以排列的最佳解决方案是递归。假设字符串中有 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);
}

回答by Vikram Bhat

Java implementation of your permutation generator:-

置换生成器的 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);
        }

}

}

回答by DeepInJava

i came across this question as one of the interview question. Following is the solution that i have implemented for this problem using recursion.

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

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

}
}

回答by BlueMoon93

For anyone looking for non-recursive options, here is a sample for numeric permutations (can easily be adapted to char. numberOfAgentsis the number of columns and the set of numbers is 0to numberOfActions:

为寻找非递归的选项，这里是数字排列的样本（可以很容易地适应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();
    }

回答by Rathina Moorthy Nataraj

// 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!!