Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

arrays - Permutation programming challenge (Java)

Ok, so I have a programming challenge which I have tried solving myself but am really struggling with. To start off you have an Array of Strings (called 'words'), each of these Strings is a single word.

search_query = "these are all the words I start off with";        
String[] queries = search_query.split(" ");

The challenge is to output another array where each item in the array is one or more words long and the array contains every permutation of the words, but keeps the words in the original order, as well being consecutive. For example, the array for this string:

"one two three"

Should be:

{"one", "one two", "one two three", "two", "two three", "three"}

The order these items end up in is not important, however I am going to be going through this algorithm quite often so efficiency is somewhat important.

(Spoilers if you want to try it entirely yourself...)

Here is all my code I have so far:

search_query = "these are all the words I start off with";        
String[] queries = search_query.split(" ");
ArrayList<String> final_list = new ArrayList<>();
String query;

for (int i = 0; i < queries.length; i++) {     //i is the start index for one segment which will become a single item
    for (int j = i; j < queries.length; j++) { //j is the end index for one segment which will become a single item
        query = "";
        for (int k = i; k < j; k++) {  
   //each item in final_list is made up from the items in queries from index i to k, 
   // where k <=j and k >=i
            query += queries[k] + " ";
            final_list.add(query);
        }
    }
}
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Here is a simple solution of your problem,
you have a problem in your 3ed loop, you don't need it!

You just need to loop through your start(i) and end(j) indices as shown below:

public static void main(String[] args) {
    String search_query = "one two three";
    String[] queries = search_query.split(" ");

    List<String> liste = new ArrayList<>();

    for (int i = 0; i < queries.length; i++) {
        String query  = "";
        for (int j = i; j < queries.length; j++) {
            query  += queries[j] + " ";
            liste.add(query);
        }
    }

    for (String y : liste) {
        System.out.println(y);
    }
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...