Permutation programming challenge (Java)

Question

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

These are not permutations, but something like subsets. Furthermore, your example lacks the case "one, three". — JF Meier
– JF Meier, Commented Jul 18, 2016 at 16:08
"These are not permutations, but something like subsets" I know permutations wasn't the best word, but I wasn't sure what else to use. "your example lacks the case "one, three".": Sorry, I made an edit, I intended the sections to be in consecutive order in addition to the other parameters. — Beyarkay
– Beyarkay, Commented Jul 18, 2016 at 16:16
If n is the number of words, then every binary number with n bits represents a solution where 1 means include the word and 0 means skip the word: 1=001=three, 2=010=two, 3=011=two+three, 4=100=one, 5=101=one+three, 6=110=one+two, 7=111=one+two+three. — m69 ''snarky and unwelcoming''
– m69 ''snarky and unwelcoming'', Commented Jul 18, 2016 at 18:09

Tomer W · Accepted Answer · 2016-07-18 17:59:50Z

1

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

edited Jul 18, 2016 at 17:59

Tomer W

3,4132 gold badges32 silver badges49 bronze badges

answered Jul 18, 2016 at 16:15

Youcef LAIDANI

60.2k21 gold badges111 silver badges178 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Beyarkay Over a year ago

Thanks, that worked perfectly. I am quite a novice programmer; would anything change by splitting the declaration/assignment of 'query'? so that it is declared outside the for loop and then reassigned to "" inside of the for loop?

Youcef LAIDANI Over a year ago

you are welcom, i really don't understand what is your question here: would anything change by splitting the declaration/assignment of 'query'? so that it is declared outside the for loop and then reassigned to "" inside of the for loop?

Beyarkay Over a year ago

My understanding is that by putting a declaration inside the for loop, Java is redeclaring the 'query' variable each time. Would it be better practice to declare it outside the for loop and then assign it to an empty string inside the for loop, thereby possible saving time/memory/something? (because it does not have to unnecessarily declare a new variable each time)

Youcef LAIDANI Over a year ago

@Beyarkay yes this is true, you can declare your variable outside the loop and then assign it to an empty string inside the for loop, yes this is better.

Collectives™ on Stack Overflow

Permutation programming challenge (Java)

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

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

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

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related