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 13 2005, 08:14 PM (Post #2)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
Nope but I can make one... Why do you need it? So are you saying something like how many ways can you arrange the letters in "scrap" while S stays in place, and list all the combos? stongue.gif
Post Options

Jul 13 2005, 08:31 PM (Post #3)
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
Yeah, listing all the different ways to arrange the letters, so the first letter would move also. There's a common algorithm out there some where, I just can't find it <_< If you can write one, that'd be good ssmile.gif
Post Options

Jul 13 2005, 08:57 PM (Post #4)
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
Problem solved. I'll tweek it a bit, but it's got the meat of what I need sbiggrin.gif

QUOTE
/**
    This class generates permutations of a word.
*/
class PermutationGenerator
{
 
  public static void main(String[] args)
    {
       PermutationGenerator generator
          = new PermutationGenerator("1234");
       while (generator.hasMorePermutations())
          System.out.println(generator.nextPermutation());
    }
    /**
       Constructs a permutation generator.
       @param aWord the word to permute
    */
    public PermutationGenerator(String aWord)
    {
       word = aWord;
       current = 0;
       if (word.length() > 1)
          restGenerator = new PermutationGenerator(word.substring(1));
       //System.out.println("Generating " + word );
    }

    /**
       Computes the next permutation of the word.
       @return the next permutation
    */
    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 PermutationGenerator(restString);
          }
       }

       return r;
    }

    /**
       Tests whether there are more permutations.
       @return true if more permutations are available
    */
    public boolean hasMorePermutations()
    {
       return current < word.length();
    }

    private String word;
    private int current;
    private PermutationGenerator restGenerator;
}
Post Options

Jul 13 2005, 10:07 PM (Post #5)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
What language is that? Java's an OOP?
Post Options

Jul 13 2005, 10:21 PM (Post #6)
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
Yeah.

I'm working on a prog to unscramble words (wrote one before in VB.NET, but my source code was lost FROWN.GIF), and I need a text file that will hold a word list with no words repeated. Anyone know a site that has a few?
Post Options

Jul 16 2005, 08:10 PM (Post #7)
Member Of The Year 2005
* * * * * * * * *
Posts: 10,363
Cash: -77,174 / 11,869,762
Group: Administrator
Joined: 2/28/03 10:58 AM
I need something like this. I need a list that will basically go:

a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
0
1
2
3
4
5
6
7
8
9
aa
ab
ac
ad
ae
af
ag
ah
ai
aj

etc etc all the way to


99999999999999999999


Is there anyway to get the computer to do this for me or do I need to type it all out myself?
Post Options

Jul 16 2005, 10:52 PM (Post #8)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
QUOTE (Duke @ Jul 13 2005, 03:21 PM)
Yeah.

I'm working on a prog to unscramble words (wrote one before in VB.NET, but my source code was lost FROWN.GIF), and I need a text file that will hold a word list with no words repeated. Anyone know a site that has a few?
*



I used to have one of those .DIC files with like 50k words in it. I'll try to find it.

QUOTE (Garlic Junior @ Jul 16 2005, 01:10 PM)
I need something like this. I need a list that will basically go:

a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
0
1
2
3
4
5
6
7
8
9
aa
ab
ac
ad
ae
af
ag
ah
ai
aj

etc etc all the way to


99999999999999999999


Is there anyway to get the computer to do this for me or do I need to type it all out myself?
*



Numbers? If you exclude that I can make one.
Post Options

Jul 16 2005, 10:56 PM (Post #9)
Member Of The Year 2005
* * * * * * * * *
Posts: 10,363
Cash: -77,174 / 11,869,762
Group: Administrator
Joined: 2/28/03 10:58 AM
Anything will do ssmile.gif
Post Options

Jul 18 2005, 12:48 PM (Post #10)
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 okay Grand: I found a text file with > 350k words.

Garlic: I would love to help you, I truly would, but my computer prolly can't handle creating all 37^19 * 36 different values to write it. It crashed after the first 92 megabytes of the text file o_o I couldn't even open the file it was so damn big.

Here's the code if you wanna use it on your computer (in java):

QUOTE
static EasyWriter file = new EasyWriter("numbers_letters.txt");
static String[] s = {"", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};

static byte b;

public static void main(String[] args){
  for (byte x1=0; x1<37; x1++)
  for (byte x2=0; x2<37; x2++)
  for (byte x3=0; x3<37; x3++)
  for (byte x4=0; x4<37; x4++)
  for (byte x5=0; x5<37; x5++)
  for (byte x6=0; x6<37; x6++)
  for (byte x7=0; x7<37; x7++)
  for (byte x8=0; x8<37; x8++)
  for (byte x9=0; x9<37; x9++)
  for (byte x10=0; x10<37; x10++)
  for (byte x11=0; x11<37; x11++)
  for (byte x12=0; x12<37; x12++)
  for (byte x13=0; x13<37; x13++)
  for (byte x14=0; x14<37; x14++)
  for (byte x15=0; x15<37; x15++)
  for (byte x16=0; x16<37; x16++)
  for (byte x17=0; x17<37; x17++)
  for (byte x18=0; x18<37; x18++)
  for (byte x19=0; x19<37; x19++)
  for (byte x20=1; x20<37; x20++)
   file.println(s[x1] + s[x2] + s[x3] + s[x4] + s[x5] + s[x6] + s[x7] + s[x8] + s[x9] + s[x10] + s[x11] + s[x12] + s[x13] + s[x14] + s[x15] + s[x16] + s[x17] + s[x18] + s[x19] + s[x20]);
}


I had to use an empty string ("") as a placeholder, but that leads to wasted memory and space since because it'll interupt your list with a few incorrect values (it'll be missing a character every once in a while). My head hurts and I don't want to think, so let's see if grand can come up with your list or something better than my horrible code lol.

This post has been edited by Duke: Jul 18 2005, 07:53 PM
Post Options

Jul 18 2005, 06:08 PM (Post #11)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
*scratches eyes* Oh god, that's frickin huge >_< I don't think I wanna code it.

Use a recursive function so you can define how long it can be.
Post Options

Jul 18 2005, 06:24 PM (Post #12)
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
With recursion more memory is taken up for each individual stack. With my computer, it'd die before it even creates the file. This code isn't particularly long o_o it's just 20 loops of basically the same thing. I wanted to use characters instead of Strings to save memory, but then it adds up all the unicode values instead of concatenation >_<

To fix the problem with my code, you can use booleans to determine whether to start with the first index or second:
QUOTE
for (byte x1=0; x1<37; x1++)
     if (x1 != 0) b1 = true;
  for (byte x2=0; x2<37; x2++)
     if (b1){
         x2 = 1;
         b1 = false;
     }
Post Options

Jul 18 2005, 07:40 PM (Post #13)
Not Odd anymore
* * * * * * * * * *
Posts: 45,875
Cash: 1,915,578 / 1,817,041,051
Group: Administrator
Joined: 7/10/02 09:48 PM
o_O PHP would be more simpler. Simple concat can be done with a period.

But still it would take forever.
Post Options

Jul 18 2005, 07:52 PM (Post #14)
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
Writing code isn't the problem. Using it is.

Garlic: why exactly do you need a list of 36^20 different values?
Post Options

Jul 18 2005, 08:07 PM (Post #15)
Member Of The Year 2005
* * * * * * * * *
Posts: 10,363
Cash: -77,174 / 11,869,762
Group: Administrator
Joined: 2/28/03 10:58 AM
<_<

If I told you I'd get arrested. Use your imagination.
Post Options

3 Pages  1 2 3 >