Simple Word Generator Help

[iiSoMeGuY 7x]

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:

#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.

[Eri523]

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

(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.

(from there i can figure out menu option two)

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

[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.

[iiSoMeGuY 7x]

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

[iiSoMeGuY 7x]

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

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!

[Eri523]

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. 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.

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...

[iiSoMeGuY 7x]

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

ya, miss counted

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...

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

[Eri523]

....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.

I'm a notorious non-gamer and had to look up Black Ops first, and I'm amazed by its sales figures. 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.

[Austin.Soucy]

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.

[iiSoMeGuY 7x]

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

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 )

[iiSoMeGuY 7x]

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"

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.

[Austin.Soucy]

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?

[Eri523]

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.

[monarch_dodra]

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:

#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:

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.

[iiSoMeGuY 7x]

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!