1

I want to generate possible tokens using forward traversal in Java. For example if I have a string "This is my car". I need to generate tokens

  • "This is my car"
  • "This is my"
  • "This is"
  • "This"
  • "is my car"
  • "is my"
  • "is"
  • "my car"
  • "my"
  • "car"

What is the best way to do this? Any examples? Thanks.

5
  • 4
    Tokenize the string with split(" "), then use a doubly nested loop to generate.
    – nhahtdh
    Dec 11, 2012 at 14:53
  • 1
    It appears that your examples preserve the original ordering from the starter string: "is my car", not "this car" or "car my". Is that intentional, or an accident?
    – CPerkins
    Dec 11, 2012 at 14:54
  • Also, does the order in which you produce the tokens matter?
    – NPE
    Dec 11, 2012 at 14:55
  • use regex to split it will give you the result and what have you tried?
    – sunleo
    Dec 11, 2012 at 14:56
  • This is not a programming exercise. I am a Oracle developer and just started using Java. I tried doing it using recursion but failed. I will post the code if needed. Order doesn't matter. I don't need out of order tokens like "car my" or "this car". Thanks.
    – M99
    Dec 11, 2012 at 14:58

4 Answers 4

5

Here is another solution with split and nested loops:

public static void main(String[] args) {
    String original = "this is my car";

    String[] singleWords = original.split(" ");  // split the String to get the single words
    ArrayList<String> results = new ArrayList<String>();  // a container for all the possible sentences
    for (int startWord = 0; startWord < singleWords.length; startWord++) {  // starWords start with 0 and increment just until they reach the last word
        for (int lastWord = singleWords.length; lastWord > startWord; lastWord--) { // last words start at the end and decrement just until they reached the first word 
            String next = "";
            for (int i = startWord; i != lastWord; i++) { // put all words in one String (starting with the startWord and ending with the lastWord)
                next += singleWords[i] + " "; 
            }
            results.add(next);  // add the next result to your result list
        }
    }

    // this is just to check the results. All your sentences are now stored in the ArrayList results
    for (String string : results) {
        System.out.println("" + string);
    }
}

and this was my result when I tested the method:

this is my car 
this is my 
this is 
this 
is my car 
is my 
is 
my car 
my 
car 
2

Use Guava:

String yourOriginalString = "This is my car";
final Set<String> originalWords = 
        Sets.newLinkedHashSet(
                Splitter.on(CharMatcher.WHITESPACE).trimResults().split(yourOriginalString));
final Set<Set<String>> variations = Sets.powerSet(originalWords);
for (Set<String> variation : variations) {
    System.out.println(Joiner.on(' ').join(variation));
}

Output:

This
is
This is
my
This my
is my
This is my
car
This car
is car
This is car
my car
This my car
is my car
This is my car
3
  • Thanks. But the problem with this is, It generated the out of order tokens. For ex: "car my", "car my this" etc.
    – M99
    Dec 11, 2012 at 15:02
  • OK, then you either need to filter the results or use this as inspiration for your own results Dec 11, 2012 at 15:04
  • @M99 my bad, I used HashSet instead of LinkedHashSet. Check my update to see if that works for you Dec 11, 2012 at 15:11
1

Here is a possible way:

//Just a method that seperates your String into an array of words based on the spaces
//I'll leave that for you to figure out how to make
String[] array = getSeperatedWords(<yourword>);
List<StringBuffer> bufferArray = new ArrayList<StringBuffer>();

for(int i = 0; i < array.length; i++){
    StringBuffer nowWord = array[i];
    for(int j = i; j < array.length; j++{
        nowWord.append(array[j]);
    }
    bufferArray.add(nowWord);
 }
 for(int i = 0; i < bufferArray.length; i++){
    System.out.print(bufferArray.get(i));
 }
1
  • Wouldn't a string like "is my" be skipped if you're iterating j from i to the end of the array? Dec 11, 2012 at 15:09
1
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {

        String var = "This is my car";
        permute(var);

    }

    public static void permute(String var) {

        if(var.isEmpty())
            return;

        String[] arr = var.split(" ");  

        while(arr.length > 0) {
            for(String str : arr) {
                System.out.print(str + " ");
            }
            arr = (String[]) Arrays.copyOfRange(arr, 0, arr.length - 1);
            System.out.println();               
        }       

        String[] original = var.split(" ");
        permute(implodeArray((String[]) Arrays.copyOfRange(original, 1, original.length), " "));

    }

    public static String implodeArray(String[] inputArray, String glueString) {

        String output = "";

        if (inputArray.length > 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(inputArray[0]);

            for (int i=1; i<inputArray.length; i++) {
                sb.append(glueString);
                sb.append(inputArray[i]);
            }

            output = sb.toString();

        }

        return output;

    }        

}

Read this book, you will be a master on recursion: http://mitpress.mit.edu/sicp/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.