FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


approaches in developing an anagram pseudocode





Denvis
I want to develop an application that takes a string of letters (A-Z) and spit out all the possibilities in terms of combinations we can make based on that string.

My software design teacher created an algorithm that does exactly that (4 characters, but can be changed).

Code:

begin
index = 1
     for x=1 to 4
            for y=1 to 4
                  for z=1 to 4
                        for w=1 to 4
                               if x+y+z+w=10 and x*y*z*w=24 then
                                     list(index) = 1000*x+100*y+10*z+w
                                     index=index+1
                               end if
                        next
                  next
            next
     next
     input WORD
     for loop = 1 to 24
            x=mid(list(loop),1,1) REM assuming you can pull digits out of a number like letters out of a word.
            y=mid(list(loop),2,1)
            z=mid(list(loop),3,1)
            w=mid(list(loop),4,1)
            anagram(loop)=mid(word,x,1)+ mid(word,y,1)+ mid(word,z,1)+ mid(word,w,1)
     next
end


^ the above is pseudocode

Basically, he designed it so that it makes all the possible combinations out of 4 numbers, and then use those numbers to selectively pick letters of the input word to create 24 combinations (there will be repeats)

I made my own however it seems to be missing a few combinations (removes repeats)

Code:
begin
input n REM 4 char string
original_n = n
   for x = 0 to length of n
      for i = 1 to length of n
         temp = mid(n,x,1)
         mid(n,x,1) = mid(n,i,1)
         mid(n,i,1) = temp
            for y = 0 to length of list() REM no repeats area
               if n != list(y) AND y = len(list) then REM != is not
                  list(y+1) = n
               endif
            next
      next
      n = original_n
   next
end


One seems to not work at all (at least with 4 + char strings) and the other one works but seems inefficient and long. I want to know if there are any other possible ways to do this... if you could respond using pseudocode i'd be very grateful!
Peterssidan
I have hard to get how everything is supposed to work. For instance, what is the purpose of
Code:
if x+y+z+w=10 and x*y*z*w=24 then
in the first code.

In your code you write
Code:
for x = 0 to length of n
From other code it looks like everything starts at index 1 so why does you start with zero here.

In the first code mid() was used with numbers but you use it on a string. With mid(n,x,1) you mean something like n[x] (the x:th char in n). Is that right? So you swap characters (n[x] <-> n[i]). and you then loop through the list but your if branch makes it so that you only consider the last case because of y = len(list). So I read your code as:

Code:
input n
original_n = n;
for x = 0 to len(n) {
    for i = 1 to len(n) {
        swap(n[x], n[i])
        if (list.last() == n) {
            add n to list
        }
    }
    n = original_n
}


Sorry if I confuzes you more than help. Ignore me if you want.

EDIT: I think you are after permutations, not combinations in a mathematically sense.
Peterssidan
I hand calculated the code as I understand it and with the string "abcd" I get the following:

x i str
0 1 bacd
0 2 cabd
0 3 dabc

1 1 abcd
1 2 acbd
1 3 adbc

2 1 bacd // same as earlier but still stored
2 2 bacd // same as prev, skip!
2 3 badc

3 1 adcb
3 2 adbc // same as earlier but still stored
3 3 adbc // same as prev, skip!

Some of these are copies and I think that the number of permutations for a string of length 4 is 4! = 24. This algorithm constructs much less so it can in no way generate all possible permutations.
AftershockVibe
This is one of the classic computing problems. It's not that easy to some up with an algorithm to do it efficiently in the general case.

It has lots of implementations though. Here is a nice one in Java:
http://www.merriampark.com/comb.htm
Related topics
Yahoo developing an audio search engine!
Pirated Software : What if we can't afford original ones
Pardus(linux)Developing by turks
whats your best IQ score?
Do's and Dont's in writing fanfiction
United Nations a failure?
anagram
developing a game in python
GRAW 2 FAQ
honey
Japan urges world to cut emissions 50% by 2050
Is China a threat to the world economy?
my team is developing a naruto mmorpg!
Developing Communities
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.