It appears you have not yet registered with our community. To register please click here.

Origin XT RPG Network Home

Recursive algorithm needed


Jul 13 2005, 07:46 PM (Post #1)
I Love Jingy
* * * * * * * * *
Posts: 11,212
Cash: 2,142,701,519 / 2,147,483,647
Group: Cabinet Member
Joined: 11/30/04 08:44 PM
Anyone seen the algorithm used to find all possible letter/digit permutations of a word/number? I need one to find all possible combinations of "words" given certain letters, preferably a recursive one. I found one some months ago in C#, but I forgot to copy it down >_<
Post Options

3 Pages < 1 2 3 
Jul 21 2005, 12:58 AM (Post #31)
I Love Jingy
* * * * * * * * *
Posts: 11,212
Cash: 2,142,701,519 / 2,147,483,647
Group: Cabinet Member
Joined: 11/30/04 08:44 PM
Programmers also debug and make a hell of a lot more money. In America, anyways.

Well, this is what I got as of a few days ago, and it does work (however inefficient). I'm gonna make it more efficient after I finish my certification and have some more free time.
CODE
/**  
 *  Created from a variation of Horstmann's PermutationGenerator
 *   http://www.sfs.uni-tuebingen.de/~nvail/SS05/Ch17/ch17.html
 *
 */
 //import java.io.*; Not needed yet since I'm still using the EasyReader and EasyWriter classes.
public class Descrambler
{
 private String word;
   private int current;
   private Descrambler restGenerator;
   private static String file = "CustomWordList.txt";
   
public static void main(String[] args){
 EasyReader console = new EasyReader();
 String argument = "";
 
 if (args.length ==1 ){
  argument = args[0];
 } else if (args.length == 0){

  System.out.print("Current file: " + file + "\nEnter command: ");
  argument = console.readLine();
 }
 while (!argument.equalsIgnoreCase("#exit")){

  if (argument.length() > 5 && argument.substring(0, 5).equalsIgnoreCase("#add:")){
   if (getNumMatch(argument.substring(5)) == 0){ //will not allow any permutations to be added, fix later
    addWord(argument.substring(5));
   } else{
    System.out.println("The word already exists in specified file.");
   }
  }
  else if (argument.length() == 5 && argument.substring(0, 5).equalsIgnoreCase("#list")){
   list();
  }
  else if (argument.length() > 7 && argument.substring(0,7).equalsIgnoreCase("#match:")){

   int count = getNumMatch(argument.substring(7));
   if (count == 0){
    System.out.println("\nNo matches found.");
   } else{
   
    Descrambler generator = new Descrambler(argument.substring(7));
    int countWord = wordCount();
    String[] str = new String[count];
    String s = new String(), temp = new String();

    EasyReader inFile;
    int i = 0;
    int n = 0;
   
    while (generator.hasMorePermutations()){
     temp = generator.nextPermutation();
     inFile = new EasyReader(file);
     
     while (i++ < countWord){
      s = inFile.readLine();

     
      if (s.equalsIgnoreCase(temp)){
       str[n++] = s;
      }
     }
     i = 0;
     inFile.close();
    }
     System.out.println("\n" + n + " matches found:");
     for (i = 0; i < n; i++){
      System.out.println(str[i]);
     }
   }
  }
  else if (argument.equalsIgnoreCase("#count")){
   System.out.println("Word Count: " + wordCount());
  }
  else if (argument.length() > 6 && argument.substring(0,6).equalsIgnoreCase("#perm:")){
   Descrambler generator = new Descrambler(argument.substring(6));
   while (generator.hasMorePermutations())
    System.out.println(generator.nextPermutation());
  }
  else if (argument.equalsIgnoreCase("#help")){
   System.out.println("#add:word    adds a new word to CustomWordList.txt");
   System.out.println("#list        lists all words in current file");
   System.out.println("#exit        exits the program.");
   System.out.println("#count       displays current number of words in current file");
   System.out.println("#perm:word   displays all permutations of the group of characters.");
   System.out.println("#match:word  unscrambles the word.");
   System.out.println("#file:file   changes text file to file specified in current directory.");
   System.out.println("#currentfile displays the name of the current text file.");
  }
  else if (argument.length() > 6 && argument.substring(0,6).equalsIgnoreCase("#file:")){
   System.out.println("File changed from " + file + " to " + (file = argument.substring(6)));
  }
  else if (argument.equalsIgnoreCase("#currentfile")){
   System.out.println(file);
  }
  else{
   System.out.println("\nInvalid command.");
  }
 
  System.out.print("\nEnter command: ");
  argument = console.readLine();
 }
   }

public Descrambler(String aWord){
 word = aWord;
       current = 0;
       if (word.length() > 1)
  restGenerator = new Descrambler(word.substring(1));
   }


   public String nextPermutation(){
       if (word.length() == 1){
          current++;
          return word;
       }

       String r = word.charAt(current) + restGenerator.nextPermutation();

       if (!restGenerator.hasMorePermutations()){
       
          current++;
         
          if (current < word.length()){
             String restString = word.substring(0, current) + word.substring(current + 1);
             restGenerator = new Descrambler(restString);
          }
       }

       return r;
   }

   public boolean hasMorePermutations(){
       return current < word.length();
   }

public static void addWord(String aWord){
  int count = wordCount();
 
  String[] list = new String[count];
  int i = 0;
  EasyReader inputFile = new EasyReader("CustomWordList.txt");

  while (i < count){
   list[i++] = inputFile.readLine();
  }

  inputFile.close();


  EasyWriter outFile = new EasyWriter("CustomWordList.txt");
  i = 0;

  while (i < count){
  outFile.println(list[i++]);
 }

 outFile.print(aWord);
 System.out.println("Item added: " + aWord);

 outFile.close();  
}

public static void list(){
 EasyReader inFile = new EasyReader(file);
 long count = wordCount();
 int i = 0;
 
 while (i < count){
  System.out.println(inFile.readLine());
  i++;
 }
 inFile.close();
}

public static int getNumMatch(String aWord){
 Descrambler generator = new Descrambler(aWord);
 int count = wordCount();
 EasyReader inputFile;
 String s = new String();
 int n = 0;
 int i=0;
 
 while (generator.hasMorePermutations()){
  s = generator.nextPermutation();
  inputFile = new EasyReader(file);
 
  while (i++ < count){
   if (inputFile.readLine().equalsIgnoreCase(s))
    n++;
  }
  inputFile.close();
  i = 0;
 }
 
 return n;
}

public static int wordCount(){  
 EasyReader inFile = new EasyReader(file);
 int count = 0;
 
 while (!inFile.eof()){
  inFile.readLine();
  count++;
 }
 inFile.close();
 
 return count -1;
}
}


I need a Collection (preferably) with fast iteration, preferably expandable so that I don't have to use wordCount() to iterate through all 350+k lines just to set the size. I'm thinking about HashSet because I don't want duplicates and it's sposed to be reasonably fast for iteration but slow for insertion and deletion (which doesn't concern me). Anyone else have any ideas? I simple array (what I'm using atm) isn't going to work well.

This post has been edited by Duke: Jul 21 2005, 02:24 AM
Post Options

Jul 21 2005, 05:34 AM (Post #32)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
bigeyes.gif If you don't wanna lose zeny put it in a .TXT file and attach it. Not that hard.

Damn, Java looks pretty cool.
Post Options

Jul 21 2005, 01:14 PM (Post #33)
I Love Jingy
* * * * * * * * *
Posts: 11,212
Cash: 2,142,701,519 / 2,147,483,647
Group: Cabinet Member
Joined: 11/30/04 08:44 PM
It's not hard to learn. Just a few syntax rules that are not common sense.
Post Options

Jul 21 2005, 06:25 PM (Post #34)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
I tried learning it before, but the first chapter got me to quit. It told me to download a compiler, and Sun's compiler crashed my comp every time. I gave up
Post Options

Jul 21 2005, 06:38 PM (Post #35)
I Love Jingy
* * * * * * * * *
Posts: 11,212
Cash: 2,142,701,519 / 2,147,483,647
Group: Cabinet Member
Joined: 11/30/04 08:44 PM
Don't use a compiler then. Just read from the books and learn syntax. It tells you what is and what is not legal.
Post Options

Jul 21 2005, 09:38 PM (Post #36)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
>_> Writing the code with no product is pointless
Post Options

Jul 21 2005, 10:26 PM (Post #37)
I Love Jingy
* * * * * * * * *
Posts: 11,212
Cash: 2,142,701,519 / 2,147,483,647
Group: Cabinet Member
Joined: 11/30/04 08:44 PM
Then don't write the code. Just read the material for a while, and when you're fairly comfortable dl a compiler.
Post Options

Jul 22 2005, 05:14 AM (Post #38)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
>_< I TOLD YOU A COMPILER DOES NOT WORK
Post Options

3 Pages < 1 2 3