Simple Word Generator Help

ok, so i havent been programming in a while and am VERY rusty. i can still read code easily, but i cant remember much when i try to write code on my own, soooooo....

i need to make a program that takes a line of up to 20 letters entered by the user and generate ALL possible outcomes of the scrambled letters (with possible spaces). now, i started the program here:

Code:

#include <iostream> #include <cstdlib> using namespace std; int main() { while (1) { char menu_choice[2]; cout << " ::Menu:: \n\n" << "1. Word Generator\n" << "2. Word Scrambler\n" << "3. Exit Program\n\n" << "Menu Choice: "; cin >> menu_choice; if (menu_choice[0] == '1') { char input[21]; system ("CLS"); cout << "Please enter up to 20 letters and this program will display all\npossible outcomes: "; cin.getline(input,20); system ("PAUSE"); system ("CLS"); } else if (menu_choice[0] == '2') { system ("CLS"); cout << "Option 2\n\n"; system ("PAUSE"); system ("CLS"); } else if (menu_choice[0] == '3') { return 0; } else if (menu_choice[0] != '3') { system ("CLS"); cout << "Invalid input.\n\nPress any key to continue..."; system ("PAUSE"); system ("CLS"); continue; } else { system ("CLS"); cout << "Invalid input.\n\nPress any key to continue..."; system ("PAUSE"); system ("CLS"); continue; } } }

Any help with the word generator (menu option one) would be grately appreciated (from there i can figure out menu option two), thanks in advance.

Re: Simple Word Generator Help

To generate all possible permutations of the entered characters I find the STL algorithm next_permutation() quite handy. The description of the algorithm is a bit abstract but I think the example is quite instructive. I'm not sure though whether this algorithm would work if the characters in the array are not all unique.

I'm not sure what you mean by

Quote:

Originally Posted by iiSoMeGuY 7x

(with possible spaces)

Someting like the following, given the characters "abc":

"abc", "a bc", "ab c", "a b c"

and of course all these with all the possible permutations of the characters between the spaces? I have no off-hand idea on how to generate these in a clever manner (and it's really late here) but I'll think about it. EDIT: Actually, I have an idea how to do that in the meantime, but first I'll wait and see whether this actually is what you want.

Quote:

(from there i can figure out menu option two)

Lucky you. :D I don't have the slightest idea what the difference between the two menu options might be. :ehh:

Re: Simple Word Generator Help

You may want to stop and think about how many possible combinations of 20 letters there are. Hope you're not busy for a while.

Re: Simple Word Generator Help

Quote:

Originally Posted by GCDEF

You may want to stop and think about how many possible combinations of 20 letters there are. Hope you're not busy for a while.

i know, there r something like 209715200000000000000000000 combinations (not including spaces), but i didnt figure that would be a problem with an algorithm, and the way i would like to make program you dont have to enter all 20, but a limit of 20

Re: Simple Word Generator Help

Quote:

Originally Posted by Eri523

Lucky you. :D I don't have the slightest idea what the difference between the two menu options might be. :ehh:

yaaaa, just trying to sound smart ;)
like i said, havent done this iin a while, and even when i was programming i didnt do anything like this (i still have ALL my old programs and how to's)

and ill check out that link, thanks man!

UPDATE: Yes, the link is exactly what im looking for, ill try it out and let you know, thanks again for the link, greatly appreciated! :D

Re: Simple Word Generator Help

Quote:

Originally Posted by iiSoMeGuY 7x

i know, there r something like 209715200000000000000000000 combinations (not including spaces), but i didnt figure that would be a problem with an algorithm, and the way i would like to make program you dont have to enter all 20, but a limit of 20

Well, not really that many. The number of combinations of 20 characters without spaces is about the factor 10^8 smaller than what you posted there. But that's still way too many to be stored on any imaginable hard disk and even without storing them I doubt that you're willing to wait until they all have been output to the console. :D BTW, the number of combinations, including spaces according to the pattern I suggested in post #2, would be n!*2^(n-1), with n being the number of (distinct) characters. Setting n=20, even that has two digits less than the number you posted.

Quote:

Originally Posted by iiSoMeGuY 7x

yaaaa, just trying to sound smart ;)

I was assuming you either designed that menu yourself and therefore know the requirements for sure or you got an assignment explaining the requirements in a bit more detail... :ehh:

Re: Simple Word Generator Help

Quote:

Originally Posted by Eri523

even that has two digits less than the number you posted.

ya, miss counted ;)

Quote:

Originally Posted by Eri523

I was assuming you either designed that menu yourself and therefore know the requirements for sure or you got an assignment explaining the requirements in a bit more detail... :ehh:

Yes, i designed this myself, from one of my older simple menus templates, and no, im not taking any classes, im self taught and got the idea from a Black Ops Zombie video (im a casual gamer in my free time and a friend said to look it up) and there are letters that u can get and spell out words which activate stuff, so then i started thinking about that Nation Treasure movie where the dork has that program where u type in letters and it gives u a list of what could be and they crack the password, then i thought back to when i used to use Cain and Abel to crack passwords on my old laptop and its basically the same principle, so i thought if they all could do y cant i??? (originally for use with the game, but i increased the letter input and added a word scrambler for the h**l of it).

....and now u know my hole thought process on y i wanted to make this program, hope i didnt bore u ;)

Re: Simple Word Generator Help

Quote:

Originally Posted by iiSoMeGuY 7x

....and now u know my hole thought process on y i wanted to make this program, hope i didnt bore u ;)

No, you can be assured you didn't. But I hope you admit me to put that into the "funny" category. :p

I'm a notorious non-gamer and had to look up Black Ops first, and I'm amazed by its sales figures. :eek: BTW, considering the fact that it's really new, the fact that I have a faint memory of having heard the name before is remarkable as well.

I had to look up Cain and Abel too. And although it actually appears to do brute force attacks, I can't really imagine it is able to reasonably do that on 20-character passwords. Take into account that 128-bit keys AFAIK are still considered safe, even against attacks done with super computers.
20 alphabetic characters, not taking case into account, are roughly equivalent to 94 bits. And I don't think you have a super computer... ;)

BTW, considering network packet sniffing a means of password recovery, as the Wikipedia article on Cain suggests, is IMO funny as well. ;)

Maybe they could do that in the game, but it's not realistic, at least not based on today's reality.

Re: Simple Word Generator Help

Quote:

Originally Posted by iiSoMeGuY 7x

ya, miss counted ;)
so then i started thinking about that Nation Treasure movie where the dork has that program where u type in letters and it gives u a list of what could be and they crack the password

If I remember correctly from the movie, there was a subtle difference in what their program did. The letters given to their program were not used more than once unless they were entered more than once. For instance:

Input: "A" "B" "C"
Output:
ABC
ACB
BAC
BCA
CAB
CBA

***NOT***
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC

I think this solution might be a little more manageable as it will cut down the number of possibilities. The only restriction is if you want the letter to be used more than once you must enter it the desired number of times.

You could make this more sophisticated by crossing each generated string with a dictionary database and returning any words that contain that particular combination. Then you would be able to see all words that your original letters could produce as well as the words that you could produce if you add more letters.( <-- This part will probably get very large though)

EDIT: I would also like to add that this approach would really start to pay off when you started using larger words. Imagine the input "TECHNOLOGY". If you allow your program to use the letters more than once you will have to deal with generations that obviously have no use:

TTTTTTTTTT
TTTTTTTTTE
TTTTTTTTTC
TTTTTTTTTH
TTTTTTTTTN
TTTTTTTTTO
TTTTTTTTTL
TTTTTTTTTO
TTTTTTTTTG
TTTTTTTTTY
TTTTTTTTET
TTTTTTTTEE
TTTTTTTTEC
TTTTTTTTEH
TTTTTTTTEN
TTTTTTTTEO
TTTTTTTTEL
TTTTTTTTEO
TTTTTTTTEG
TTTTTTTTEY
etc......

This kind of garbage would really take up the majority of your computing if you allow your program to re-use the letters.

Re: Simple Word Generator Help

Quote:

Originally Posted by Eri523

I had to look up Cain and Abel too. And although it actually appears to do brute force attacks, I can't really imagine it is able to reasonably do that on 20-character passwords. Take into account that 128-bit keys AFAIK are still considered safe, even against attacks done with super computers.
20 alphabetic characters, not taking case into account, are roughly equivalent to 94 bits. And I don't think you have a super computer... ;)

BTW, considering network packet sniffing a means of password recovery, as the Wikipedia article on Cain suggests, is IMO funny as well. ;)

it doesnt just do brute force, it does rainbow table and library attacks as well, but thats besides the point :P ...and i only did a little bit of hacking (mostly on myself to find MY own passwords that i didnt use in a long time), so lets not get into that please :D

Anyways, i was using that as a thought process reference because of the brute force attack, as it tries EVERY possible combination, and ONLY that part as the reference (i dont know y, it just came to mind ;) )

Re: Simple Word Generator Help

Quote:

Originally Posted by Austin.Soucy

I think this solution might be a little more manageable as it will cut down the number of possibilities. The only restriction is if you want the letter to be used more than once you must enter it the desired number of times.

ya, thats what i wanted in the first place :)
...and good memory, thats how the dude cracked the password "valley forge" ;)

Quote:

Originally Posted by Austin.Soucy

You could make this more sophisticated by crossing the each generated string with a dictionary database and returning any words that contain that particular combination. Then you would be able to see all words that your original letters could produce as well as the words that you could produce if you add more letters.( <-- This part will probably get very large though)

this....IS......PERFECT!!!!!! i just never knew how to do that, so if wouldnt mind giving me a link or telling me how to do that, please? Thanks. :)

Re: Simple Word Generator Help

Quote:

Originally Posted by iiSoMeGuY 7x

so if wouldnt mind giving me a link or telling me how to do that, please? Thanks. :)

One link is not going to show you how to do this. I have never implemented anything this large and since I have been looking for a new project i might just try my hand at this as well.

std::string is probably a good place to start.
http://www.cprogramming.com/tutorial/string.html
http://www.cplusplus.com/reference/string/string/

I don't know what kind of functionality std::string has for re-ordering the letters but the compare() and substr() can be used to compare to the dictionary database. Any gurus have input? Would it be easy enough to use char arrays for re-ordering and then cast to std::string for comparison?

Re: Simple Word Generator Help

Quote:

Originally Posted by Austin.Soucy

I don't know what kind of functionality std::string has for re-ordering the letters but the compare() and substr() can be used to compare to the dictionary database. Any gurus have input? Would it be easy enough to use char arrays for re-ordering and then cast to std::string for comparison?

Re-ordering is not a feature of std::string. I have already pointed to a way of generating permutations of distinct characters in post #2. How to enumerate combinations of non-distinct characters (like in your "TTT..." example) has been discussed in http://www.codeguru.com/forum/showthread.php?t=508086 and the thread I linked to from there in post #6.

I didn't really understand how your dictionary approach is supposed to work, but I would generally recommend to have the database do the lookup. They have optimized algorithms for things like that that you're unlikely to beat.

Re: Simple Word Generator Help

You can use an algorithm I submited in another thread for someone who had a similar need. You just have to provide a "letters of tech" type, for example:

Code:

#include <iostream> #include <vector> #include <algorithm> #include <iterator> #include <limits> const char TECH[] = "TECH"; struct letters_of_tech { letters_of_tech() : p(TECH){} letters_of_tech(char c) : p(0) { switch (c) { case 'T': {p=TECH+0;}break; case 'E': {p=TECH+1;} break; case 'C': {p=TECH+3;} break; case 'H': {p=TECH+4;} break; default: {p=TECH+5;} //points to '\0' } } letters_of_tech& operator++() {++p; return *this;} operator char() {return *p;} private: const char* p; }; template <typename iter> bool increment(iter first, iter last, typename std::iterator_traits<iter>::value_type min = std::numeric_limits<typename std::iterator_traits<iter>::value_type>::min(), typename std::iterator_traits<iter>::value_type max = std::numeric_limits<typename std::iterator_traits<iter>::value_type>::max()) { while((first!=last) && (*first == max)) { *first = min; ++first; }; if(first!=last) { ++*first; return true; } return false; } int main() { std::vector<letters_of_tech> vect(4); //vector<bool> is not a container do { std::copy(vect.rbegin(), vect.rend(), std::ostream_iterator<char>(std::cout)); std::cout << std::endl; }while(increment(vect.begin(), vect.end(), 'T', 'H')); }

outputs:

Code:

TTTT TTTE TTTC TTTH TTET TTEE TTEC TTEH TTCT TTCE TTCC TTCH TTHT TTHE TTHC TTHH TETT TETE TETC TETH TEET TEEE TEEC TEEH TECT TECE TECC TECH TEHT TEHE TEHC TEHH TCTT TCTE TCTC TCTH TCET TCEE TCEC TCEH TCCT TCCE TCCC TCCH TCHT TCHE TCHC TCHH THTT THTE THTC THTH THET THEE THEC THEH THCT THCE THCC THCH THHT THHE THHC THHH ETTT ETTE ETTC ETTH ETET ETEE ETEC ETEH ETCT ETCE ETCC ETCH ETHT ETHE ETHC ETHH EETT EETE EETC EETH EEET EEEE EEEC EEEH EECT EECE EECC EECH EEHT EEHE EEHC EEHH ECTT ECTE ECTC ECTH ECET ECEE ECEC ECEH ECCT ECCE ECCC ECCH ECHT ECHE ECHC ECHH EHTT EHTE EHTC EHTH EHET EHEE EHEC EHEH EHCT EHCE EHCC EHCH EHHT EHHE EHHC EHHH CTTT CTTE CTTC CTTH CTET CTEE CTEC CTEH CTCT CTCE CTCC CTCH CTHT CTHE CTHC CTHH CETT CETE CETC CETH CEET CEEE CEEC CEEH CECT CECE CECC CECH CEHT CEHE CEHC CEHH CCTT CCTE CCTC CCTH CCET CCEE CCEC CCEH CCCT CCCE CCCC CCCH CCHT CCHE CCHC CCHH CHTT CHTE CHTC CHTH CHET CHEE CHEC CHEH CHCT CHCE CHCC CHCH CHHT CHHE CHHC CHHH HTTT HTTE HTTC HTTH HTET HTEE HTEC HTEH HTCT HTCE HTCC HTCH HTHT HTHE HTHC HTHH HETT HETE HETC HETH HEET HEEE HEEC HEEH HECT HECE HECC HECH HEHT HEHE HEHC HEHH HCTT HCTE HCTC HCTH HCET HCEE HCEC HCEH HCCT HCCE HCCC HCCH HCHT HCHE HCHC HCHH HHTT HHTE HHTC HHTH HHET HHEE HHEC HHEH HHCT HHCE HHCC HHCH HHHT HHHE HHHC HHHH

Regarding dictionary and what not, it really really really depends what you want to do with all these permutations.

If all you care about is just listing everything and forget about it, this is the solution for you.

The DAWG data structure is strangely well adapted to this kind of problem actually. It can store ALL of the generated words in nothing more than a few bytes.

If you would indulge us in illustrating the need, I'd be thrilled to search for a solution.

EDIT: I see ERI already linked the thread.

Re: Simple Word Generator Help

Quote:

Originally Posted by monarch_dodra

If you would indulge us in illustrating the need, I'd be thrilled to search for a solution.

well, this would work perfectly actually, but as for the dictionary reference, i guess id like to make an extra option for that...

IE: user enters input, program shows output, then at the bottom (or top) an extra option that would ask "would like to cross-reference these options to a dictionary to make it easier to look for real words" or something like that...

thanks a lot! :)