
03242004, 12:23 AM
#151
Hey Ratboy...here's a little snippet of Java code (apparently we gotta represent!) that would work for your letter matching thing. It's basically a function that takes in a sorted array, and produces every single permutation of it while it still has one. It keeps testing hasNext() for the while loop condition and if it returns true and enters the loop, we call next to get the next "word". Then each "word" would have to be checked against a dictionary. So here's the permutation code...
Code:
boolean hasNext()
{return hasAnother;} //where hasAnother is just a boolean
Object next()
{
hasAnother = nextPermutation(tempArray);
return ""; //yeah so it's sloppy code (real one is all static too)...sue me
} // it was only written to play word whomp!
boolean nextPermutation (char[] a)
{
if (a.length <= 1)
{return false;}
int i = a.length  1;
while (true)
{
int j = i;
if (a[i] < a[j])
{
int k = a.length;
while (!(a[i] < a[k])) {}
swap(a, i, k);
reverse(a, j);
return true;
}
if (i == 0)
{
reverse(a, 0);
return false;
}
}
}
void reverse (char[] a, int i)
{
int j = a.length  1;
while (i < j)
{swap(a, i++, j);}
}
void swap (char[] a, int i, int j)
{
char tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
I had to write a program a few semesters ago that solved crypt arithmetic problems (if you don't know what that is, check it out here ), so it had to make all permutations of a set of letters and another that played boggle (so it had to check words against a dictionary..and recursively search the board to see if it exists) so I just kinda borrowed from both.
Interestingly enough, I have already written something very similar to what you're describing several months ago. My dad really likes playing this game called "Word Whomp" where they jumble up 6 letters and you have to find all the valid words of length 3, 4, 5, or 6...so I just wrote a program to do it for me! It's specifically designed for those length words though and won't work for more than that. If you're interested, all necessary files can be found here. The above methods are used in it (and Words.java contains the main method used to run everything).
"The author of that poem is either Homer or, if not Homer, somebody else of the same name."

04042004, 03:32 PM
#152
Originally posted by bwkaz
[B]Um... no it isn't...
First, it would require, at MINIMUM, 16 billion gigabytes of code space (since it'll be at least one byte for each value of a and b, that's 4 billion, squared, possibilities).
Oops. My bad, you're right it's NOT very practical. I mean, when you read it back it almost looks like it was joking.
Whatever it is I'm asking no doubt someone will find the answer in some obvious place and accuse me of not STWFing or RTFMing.
I swear I did, I'm just stupid.

04062004, 09:57 AM
#153
heres a new one for you.
I was just in math class thinking about it when I thought...
is it possible to find the apsolute value of an integer without using a dummy variable and obviously another method or function.
GlennaclawZ
Registered Linux User: #342515
Slackware 10  kernel 2.6.10
AMD Athlon 3000+
512 RAM pc2700
NVIDIA GeForce2 Integrated
www.rexpro.com For life!!!

04062004, 10:03 AM
#154
Code:
if( var < 0) {
var *= 1;
}

04062004, 10:05 AM
#155
[QUOTE]Originally posted by gamblor01
[B]Hey Ratboy...here's a little snippet of Java code (apparently we gotta represent!) [QUOTE]
better Permutation:
Code:
public class Permutation
{
ArrayList arrayList; //declaring variables
Random random;
Double wrapper;
int array[];
int arraySpot;
Permutation() //constructors
{
random = new Random();
arrayList = new ArrayList();
array = new int[10];
}
public int[] fillArray() //filling array
{
for(int i = 0; i < 10; i++)
{
int number = 1;
array[i] = number;
}
return array;
}
public void generatePerm() //generating permutation
{
for(int k = 0; k <= 10; k++)
{
arraySpot = random.nextInt(10) + 1;
wrapper = new Double(arraySpot);
arrayList.add(wrapper);
System.out.print(arrayList.get(k) + " ");
}
initList(arrayList);
}
public void initList(ArrayList list) //filling array back up
{
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
list.add("7");
list.add("8");
list.add("9");
list.add("10");
}
}
Last edited by GlennaclawZ; 04072004 at 10:00 AM.
Registered Linux User: #342515
Slackware 10  kernel 2.6.10
AMD Athlon 3000+
512 RAM pc2700
NVIDIA GeForce2 Integrated
www.rexpro.com For life!!!

04062004, 12:15 PM
#156
Originally posted by lagdawg
Code:
if( var < 0) {
var *= 1;
}
wow that was alot easier than I thought...
Registered Linux User: #342515
Slackware 10  kernel 2.6.10
AMD Athlon 3000+
512 RAM pc2700
NVIDIA GeForce2 Integrated
www.rexpro.com For life!!!

04062004, 12:49 PM
#157
How about without an if statement?

04062004, 01:03 PM
#158
In Perl:
unless( var > 0) {
var *= 1;
}
Registered Linux User #325947
Check out Feather Linux, my distro.
(Yes, it's shameless self promotion, deal with it )

04062004, 07:40 PM
#159
I can do it without an if, but I need a dummy variable:
Code:
int y = ((int)(x & 0x800000000u)) >> 31;
/* y is all 1 bits now if x was negative, and 0 otherwise */
x ^= y; /* either flip all the bits (y all 1 bits) or leave them alone (y = zero) */
x += (y & 1); /* either add 1 or 0 */
Assuming x is a signed, two's complement, 32bit int, that is (which is the case on x86). If x86 used signmagnitude numbers instead of two's complement, then it'd be as easy as:
Code:
x &= ~(0x7fffffff);
to turn off the sign bit, but that's not the case.

04082004, 04:46 PM
#160
Scotty: Captain, we din' can reference it!
Kirk: Analysis, Mr. Spock?
Spock: Captain, it doesn't appear in the symbol table.
Kirk: Then it's of external origin?
Spock: Affirmative.
Kirk: Mr. Sulu, go to pass two.
Sulu: Aye aye, sir, going to pass two.

04092004, 03:51 PM
#161
god....i'll be going to UTA in the fall for computer science, hopefully by the time i get out i know what the hell you guys are talking about in this thread

04102004, 02:27 AM
#162
Okay, I read this book "Archimede's Revenge" a couple weeks ago and it has a buttload of stuff like this, basically all this number and geometry thoery and stuff. Good reading. Here's one of the problems:
"Suppose there are 100 people in a group, and you want to find out if 50 of them know each other".
This can be done on paper by drawing 100 dots, connecting lines between people that know each other, and looking for all the people that know 49 others that all know the other 49.
Yeah, it's one of those problems that as the set of people gets larger, the amount of work that it would require to find the answer increases exponentially.
Find an algorithm that finds the answer in a manner such that the answer is found in an amount of work like n * number of people, rather than number of people ^ n.
I was working on a method where you make a table, with all the people in the columns and all the people in the rows. Mark an X in the appropriate spot where people know one another(including that person knowing themself). Then remove all people that have less than the needed number of associations. Then you are left with all the people knowing the amount of people needed to associate with. Then, if all the spaces are filled, the answer is 'yes', they all know each other. I belive this approach is not exponential, but I could be wrong.
Registered Linux User #328016
I cna ytpe 300 wrods pre mniute
Slackware 10.0
Shuttle AN35N nForce2 mobo
AMD Athlon XP 2600
512 MB DDR RAM
XFX GeForce FX 5200 256 MB
40 GB Western Digital HDD

04122004, 11:10 AM
#163
duncanbojangles:
This problem is basically for a group of n people find out if n/2 people know each other.
The method you propose will only work in O(n^2) time. Or number of people ^ 2.
First: To find all of the people in the group who know at least (n/2  1) you will have to visit every person and at the least for every peson you will have to visit is (n/2  1) if they now the first (n/21) people. There fore just to find all the people who know more than (n/2  1) people requires a minimum time of: n * (n/2  1) or 1/2 n^2  n which is on the order of n^2.
Edit
I just realized the the First part of your solution can be accomplished like the second part with an upper triangular adjacency matrix and would only require the following number of visits if you kept a count along the way for each person:
(n^2  n) / 2 = 1/2 n^2  1/2 n which is less than 1/2 n^2  n but it is still on the order of O(n^2).
Second: To check whether all the people who know n/21 people know all the others you have to check whether the resulting upper triangular adjacency matrix is full.
(example for n = 10 and n/2 = 5)
x x x x x
0 x x x x
0 0 x x x
0 0 0 x x
0 0 0 0 x
This matrix could be the result of removing rows from the original table / matrix, but since the lower triangle (everything under the diagonal) is the same as the upper triangle you only need to look at the upper triangle not including the diaganol and you must visite each one of those to see if they are x or not so we must visit
(5^2  5) / 2 or ((n/2)^2  n) / 2 or 1/4 (n^2)  1/2 n
which is of order O(n^2) as well
so your solution is exponential in nature.
Last edited by lagdawg; 04122004 at 11:34 AM.

04122004, 06:21 PM
#164
Darn. Oh well. The problem applies to any amount of people knowing any number of people...it didn't necessarily have to be 50 out of 100, that was just the example they used in the book. Thanks for pointing that out to me, guess I'm just not MathGenius material
Edit!: After I thought about it, you may be able to reduce the amount of twork it requires to see who one person knows. If, for person A you find out they know B, C, D, and E, then B, C, D, and E will not have to check if they know A. This reduces a lot of work in theory, but in code you'd still have to check on the status of "knowingness of A". As long as the search is done in order, though, A, B, C, D, E, then you know that at E, they already know whether or not they know A, B, C, or D, so they don't have to check. This reduces a lot of overhead by only making E start looking at F.
Last edited by duncanbojangles; 04122004 at 06:27 PM.
Registered Linux User #328016
I cna ytpe 300 wrods pre mniute
Slackware 10.0
Shuttle AN35N nForce2 mobo
AMD Athlon XP 2600
512 MB DDR RAM
XFX GeForce FX 5200 256 MB
40 GB Western Digital HDD

04132004, 09:19 AM
#165
This problem can be solved recursively but it is slow on the order of O(n^2) or greater. But I beleive you could use dynamic programming to solve the recursion from the bottom up. Basically you only do each calculation once. Not sure how to do it right now but I'm working on it.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

