Posted by Benjamin Johnston on 1999-04-25
I haven't seen these questions answered yet, so I'll answer them.
>first off I'm trying to make an antagram creator... (yes I know there's
>a website that will do this for me, but I want to do it myself) I've
>decided to use the Linux operating system to do this so I can create
>simple programs which might become useful later on and so I can get the
>hang of pipes and/or shell scripts... and compiling C using GCC and
>makefiles... (I'm used to Borland's nice IDE for Turbo C) basicaly
>it'll be a great learning experence for me... :)
>
>I just would like to know a few things:
>
>Question 1: Does RedHat 5.2 come with a file containing words like a
>dictionary w/o definitions? If not where can I get one?
There is probably a dictionary somewhere, maybe with a password program (so
that you dont use passwords that are common words). Whenever I need to get
a dictionary/word-list I find that hacking sites are pretty usefull...
Hackers use them to crack passwords, programmers can use them for good (in
anagram generators or spell checkers)
>Question 2: Does anyone know of an algorithm to take an array and
>finding all the possible combinations for the array? ex. finding all
>the possibilities of 123: 123, 132, 213, 231, 312, 321
>
>I tried to figure this out for myself, but I could only get my algorithm
>to work on arrays of 3 and 4 elements and would screw up on any array
>larger than that... any suggestions would be appreciated.... Psudocode
>should be good enough for me... :)
The first thing that comes to mind is something with recursion, like this
(this is Java, but
it shouldn't be hard to convert to c)....
public class DisplayCombinations {
private static int[] array = { 2, 7, 9, 4 }; /*the data to sort -- doesn't
need to be numbers*/
private static int[] temp = { 0, 0, 0, 0 };
/* 'temp' must be a zero array of the same size as 'array' */
public static void main(String[] args) {
combinations(0);
}
private static void combinations(int depth) {
int i;
if (depth==array.length) {
for (i=0; i<array.length; i++) {
System.out.print(array[temp[i]-1]);
}
System.out.print("\n");
} else {
i=0;
do {
if (temp[i]==0) {
temp[i]=depth+1;
combinations(depth+1);
temp[i]=0;
}
i++;
} while (i<temp.length);
}
return;
}
}
Ok, this will display all the possible orderings... but beware; for 6 items,
there will be 6! (6*5*4*3*2*1) possible orderings and for 20 items there
will be 20! (20*19*18*...*4*3*2*1 = 2432902008176640000 combinations)
This will not print the results sorted, but for sorted output use the
following slightly slower, and more complex code for combinations...
private static void combinations(int depth) {
int i;
int j;
if (depth==array.length) {
for (i=0; i<array.length; i++)
for (j=0; j<array.length; j++)
if (temp[j]-1==i)
System.out.print(array[j]);
System.out.print("\n");
} else {
i=0;
do {
if (temp[i]==0) {
temp[i]=depth+1;
combinations(depth+1);
temp[i]=0;
}
i++;
} while (i<temp.length);
}
return;
}
If you REALLY want me too, I could probably rewrite it in c, but I'm a bit
rusty, and hopefully you can work out how it works.
Good luck with your programming.
-Benjamin Johnston
s355171@xxxxxxx.xx.xxx.xx
Previous post | Next post | Timeline | Home