permutation(orderings) of a string of words but separated by a comma in between

Question

Hello Everyone...

I'm having some difficulty having this code generate a number of permutations(orderings) on a string separated by commas ...I can do just a regular string and have the permutations work on just letters but it is a bit more difficult when doing it with words separated by the commas...

To have the program recognize the commas I used the StringTokenizer method and I'm putting it into an arrayList but that is really as far as I have gotten ...the problem again is I'm having trouble permuting each word...to give an example I'll post it below this and then my code below that...thank you for your help everyone! ...and by permutations I mean orderings of the words separated by the comma's

For example, if the input coming in on the BufferedReader looked like:

red,yellow

one,two,three

the output on the PrintWriter should look like:

red,yellow

yellow,red



one,two,three

one,three,two

two,one,three

two,three,one

three,one,two

three,two,one

Note that the input had 3 lines total, including the blank line after "one,two,three" while the output had 11 lines total, including one blank line after "yellow,red" and two blank lines after "three,two,one". It is vital that you get the format exactly correct as the testing will be automated and will require this format. Also note that the order of the output lines for each problem does not matter. This means the first two lines of the output could also have been:

yellow,red

red,yellow

---

here is the code I have so far ...I have commented some stuff out so don't worry about those parts

import java.io.*;

import java.util.*;

public class Solution

{

 public static void run(BufferedReader in, PrintWriter out)

    throws IOException

{

 String str = new String(in.readLine());

 while(!str.equalsIgnoreCase(""))
 {
 PermutationGenerator generator = new PermutationGenerator(str);
 ArrayList<String> permutations = generator.getPermutations();
 for(String str: permutations)
 {
  out.println(in.readLine());
 }
 out.println();
 out.println();

 }
 out.flush();

}







public class PermutationGenerator
{

 private String word;


public PermutationGenerator(String aWord)
{
 word = aWord;
}



public ArrayList<String> getPermutations()
{
 ArrayList<String> permutations = new ArrayList<String>();
 //if(word.length() == 0)
 //{
  //permutations.add(word);
  //return permutations;

 //}

  StringTokenizer tokenizer = new StringTokenizer(word,",");

     while (tokenizer.hasMoreTokens())
     {
      permutations.add(word);
      tokenizer.nextToken();
     }
 /*     
 for(int i = 0; i < word.length(); i++)
 {
  //String shorterWord = word.substring(0,i) + word.substring(i + 1);
  PermutationGenerator shorterPermutationGenerator = new PermutationGenerator(word);
  ArrayList<String> shorterWordPermutations =     
    shorterPermutationGenerator.getPermutations();

  for(String s: shorterWordPermutations)
  {
   permutations.add(word.readLine(i)+ s);
  }
 }*/
 //return permutations;


 }
}

}

Answer 1

You can use String.split() ( http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#split(java.lang.String) ) to get the individual words into as an array. You can separately generate all the permutations on integers {1..N} where N is the size of the word array. Then just walk the word array using the numeric permutations as indices.

Answer 2

1. Parse your input line (which is a comma-separated String ow words) into array of Strings (String[] words).
2. Use some permutation generator that works on a array, you can easily find such generator using google. U want a generator that can be initialized with Object[], and has a method like Object[] nextPermutation().
3. Put it together into your solution.

PS U can also use a Integer permutation generator and generate all permutations from 0 to (words.length - 1); each such permutation will give you an array of indexes of words[] to be printed out.