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

解決策はかなりばかげています。という意味でスケーラブルではありません。

  1. のサイズを大きくするとどうなりdatabaseますか?
  2. 最終的に対象とする印刷文字列の長さを N にする必要がある場合はどうすればよいですか?

スケーラブルな順列と組み合わせ文字列を本当にスマートな方法で生成できるスマートなコードはありますか?

4

7 に答える 7

18

この回答を確認する必要があります: 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]);
        }
    }
}

メモリをさらに改善することもできますが、このソリューションはすべてのソリューションを最初にメモリ (配列) に生成してから印刷できるようにするためです。しかし、再帰アルゴリズムを使用するという考え方は同じです。

于 2013-11-15T03:57:38.357 に答える
3

これはバイナリでカウントするようなにおいがします:

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

私の最初の本能は、バイナリカウンターを文字の「ビットマップ」として使用して、それらの可能な値を生成することです。ただし、ここには、再帰の使用を提案する関連する質問に対する素晴らしい回答がいくつかあります。見る

于 2013-11-15T03:52:06.013 に答える
0

非再帰的なオプションを探している人のために、ここに数値順列のサンプルがあります (簡単に適応できます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();
    }
于 2016-09-22T13:41:48.493 に答える
0

インタビューの質問の1つとして、この質問に出くわしました。以下は、再帰を使用してこの問題に対して実装したソリューションです。

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

}
}
于 2014-09-28T19:38:37.750 に答える