How to calculate and apply all possible char combinations

[UncleBazerko]

Are you talking about when you said:

Do not mix responsibilities. Only responsibility of next() should be generation of next string.
Ideally you should test your password where output statement is now.

Because recall that when you said that, I didn't have the "print_all" function in my code yet.

Also, password is too big to be guessed.

Well, not really. My password was 8 characters long, and my max was set to 10:

std::string password = "97034031";//password to be guessed
	const std:: size_t max = 10;//maximum password string length to guess for 

But I'll take your word for it. In the following code, I've undone the original loop changes, and changed the maximum password guess length back to 5 chars:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

//using namespace std;

//char letters[] = { 'a', 'b', 'c' };
static const char letters[] =
"0123456789"
"!@#$%^&*"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";

template <typename T, std::size_t N>/*Why can't this line just be "template <typename T>"? 
									Because then you cannot tell that you want an array here.*/
std::size_t array_size(T(&)[N])
{
	return N;/*It is called safe array size: if you call it on naything not an array, it will 
			 give you an error (unlike sizeof which often returns size of pointer instead of array)*/
}
bool next(std::string& in)//Mutates string, setting it to the next in set of all possible combinations. 
						  //If you run provided code you will see how is it done. It returns true if there 
						  //was no "rollover" (like preventing a car milage meter from displaying "0000"
						  //after exceeding "9999"), false otherwise. This is intended to prevent the
						  //generation of a possible combination more than once. "next" is a reference
						  //variable to the current combination being generated.
{
	for (std::size_t i = 0; i < in.size(); ++i)
		if (in[i] == letters[array_size(letters) - 1]){ //if current letter is last in set ...

		in[i] = letters[0]; //Then we assign first letter and let loop continue

		}//end of "if (in[i] == letters[array_size(letters) - 1])"
		else {
			std::size_t pos = std::distance(std::begin(letters),
				//Computes the distance between two iterators. It's used to find
				//the distance between the beginning of letters array and the pointer 
				//to the currently found element (to get the index of that element) in
				//the array

				std::find(std::begin(letters), std::end(letters), in[i]));//"in[i]" is the second iterator that
			                                                              //looks for the current letter being
			                                                              //pointed to in letters array
			
			in[i] = letters[++pos]; //Else we increment the index and use it to assign 
			                        //the next letter in the set and return true.
			
			return true; //As indication that it is not the last possible string  
												
		}//end of else statement
		return false; //If loop finished, we exhausted all strings
		
}//closing brace of bool next

void print_all()
{
	std::string password = "sam40";//password to be guessed
	const std:: size_t max = 5;//maximum password string length to guess for 
	for (std::size_t size = 1; size <= max; ++size) {//Generate sequences of all possible length
		//Create string of correspomding length. Note that we CANNOT use space as initializer
		//Or nothing would work at all.
		std::string guess(size, letters[0]);
		bool again = false;
		do { //Inner loop, generates all possible variation of given length
			again = next(guess); //Generate next string 			
			/*see reference to class template instantiation 'std::iterator_traits<std::string>' being compiled*/
			//std::cout << guess << '\n';
		} while (again);/*Is the loop logic still broken?*/
		if (guess == password){
			std::cout << "The password is: " << guess << std::endl;
		}
		else{
			std::cout << "Sorry, no matching password was found." << std::endl;
		}
		return;
		//std::cout << '\n';

	}//end of for loop
}

int main()
{
	print_all();
}

But I'm still getting the same error. So now what?

[MiiNiPaa]

Which error? Code is syntaxically correct.

Line 76. It terminates loop after checking all 1 long passwords. Also it only checks passwords like a, aa, aaa etc.

Ideally you should test your password where output statement is now.

Where is (now commented) output is?

Add return after outputting password.

After checking pasword and outputting if it is correct.
http://coliru.stacked-crooked.com/a/d18c77a54198095b

Well, not really. My password was 8 characters long, and my max was set to 10:

I might not said this clear: it will work if you do not ming waiting several days to get result.

[UncleBazerko]

Wow! I wish I knew about Coliru sooner. There's just one more little problem. If the program fails to find a matching password, (whether it be because the password was longer than the maximum character limit, or simply because a match wasn't found), where am I supposed to implement and output statement saying that a match wasn't found?

#include <iostream>
#include <iterator>
#include <algorithm>
#include <string>

//using namespace std;

//char letters[] = { 'a', 'b', 'c' };
static const char letters[] =
"0123456789"
"!@#$%^&*"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";

template <typename T, std::size_t N>/*Why can't this line just be "template <typename T>"? 
									Because then you cannot tell that you want an array here.*/
std::size_t array_size(T(&)[N])
{
	return N;/*It is called safe array size: if you call it on naything not an array, it will 
			 give you an error (unlike sizeof which often returns size of pointer instead of array)*/
}
std::string password = "aaaaa";//password to be guessed
int num_guesses = 0;
bool next(std::string& in)//Mutates string, setting it to the next in set of all possible combinations. 
						  //If you run provided code you will see how is it done. It returns true if there 
						  //was no "rollover" (like preventing a car milage meter from displaying "0000"
						  //after exceeding "9999"), false otherwise. This is intended to prevent the
						  //generation of a possible combination more than once. "next" is a reference
						  //variable to the current combination being generated.
{
	for (std::size_t i = 0; i < in.size(); ++i)
		if (in[i] == letters[array_size(letters) - 1]){ //if current letter is last in set ...

		in[i] = letters[0]; //Then we assign first letter and let loop continue

		}//end of "if (in[i] == letters[array_size(letters) - 1])"
		else {
			std::size_t pos = std::distance(std::begin(letters),
				//Computes the distance between two iterators. It's used to find
				//the distance between the beginning of letters array and the pointer 
				//to the currently found element (to get the index of that element) in
				//the array

				std::find(std::begin(letters), std::end(letters), in[i]));//"in[i]" is the second iterator that
			                                                              //looks for the current letter being
			                                                              //pointed to in letters array
			
			in[i] = letters[++pos]; //Else we increment the index and use it to assign 
			                        //the next letter in the set and return true.
			
			return true; //As indication that it is not the last possible string
			//num_guesses++;
												
		}//end of else statement
		return false; //If loop finished, we exhausted all strings
		std::cout << "Sorry, no matching password was found." << std::endl;
		/*Currently doesn't display. Also note that I've reset my password to "aaaaa",
		but a match wasn't found. Does this have something to do with preventing a
		rollover?*/
		
}//closing brace of bool next

void print_all()
{
	const std:: size_t max = 5;//maximum password string length to guess for 
	for (std::size_t size = 1; size <= max; ++size) {//Generate sequences of all possible length
		//Create string of correspomding length. Note that we CANNOT use space as initializer
		//Or nothing would work at all.
		std::string guess(size, letters[0]);
		bool again = false;
		do { //Inner loop, generates all possible variation of given length
			again = next(guess); //Generate next string 			
			/*see reference to class template instantiation 'std::iterator_traits<std::string>' being compiled*/
			//std::cout << guess << '\n';
			num_guesses++;
			if (guess == password){
				std::cout << "After " << num_guesses << ", The password is: " << guess << std::endl;
				return;
			}
		} while (again);
		
		//std::cout << '\n';

	}//end of for loop
}

int main()
{
	print_all();
}

[MiiNiPaa]

And again you are trying to make next() function to do extra work. Do not touch it. It is already finished.
Also your output statement is right after statement which literally tells "stop function here. do not execute anything past this point"

All guessing work is happening inside for loop. So you need to place output statemnt after it.

[UncleBazerko]

Without adding to the next function, all I could think of was to invoke the next variable after the end of the for loop in the print_all() function. I have more /*questions*/:

void print_all()
{
	const std:: size_t max = 5;//maximum password string length to guess for 
	for (std::size_t size = 1; size <= max; ++size) {//Generate sequences of all possible length
		//Create string of correspomding length. Note that we CANNOT use space as initializer
		//Or nothing would work at all.
		std::string guess(size, letters[0]);
		bool again = false;
		do { //Inner loop, generates all possible variation of given length
			again = next(guess); //Generate next string 			
			/*see reference to class template instantiation 'std::iterator_traits<std::string>' being compiled*/
			//std::cout << guess << '\n';
			num_guesses++;
			if (guess == password){
				std::cout << "After " << num_guesses << " guesses, The password is: " << guess << std::endl;
				/*This output still worked, but I'm getting a warning:
				"warning: the address of 'bool next(std::string&)' will never be NULL [-Waddress]"
				What is this? Either it returns true or false. How can a boolean be null?*/
				return;
			}
		} while (again);		
		
		//std::cout << '\n';

	}//end of for loop
	if (next == false){//if we have exhausted all possible strings but a match still wasn't found
		std::cout << "Sorry, no matching password was found." << std::endl;
		/*This cout statement never outputs, and thus doesn't seem to be working. Also, when I reset
		the password to "aaaaa", nothing happens. Does this have something to do with preventing a
		rollover? It's very unlikely that anyone would use a password like "aaaaa", but I want my
		program to check for it anyway.*/
		return;
	}	
}

int main()
{
	print_all();
}

[MiiNiPaa]

if (next == false){

next is a function which is not equal to false by definition. Warning warns you about that.
You do not need condition here. If outer loop finishes without outputting password and returning it means that we did not find the password, isn't it?

Does this have something to do with preventing a rollover?

Nothing in the code prevents a rollover. return value of next() just detects it. We need to know about that so we would prevent generating same sequence of passwords over and over.

Also, when I reset the password to "aaaaa", nothing happens.

How long did you wait? "aaaaaa" is the last password to check, so it would take maximum amount of time for it. You should wait around 5 minutes:

After 1159861724 guesses, The password is: aaaaa

Process returned 0 (0x0)   execution time : 213.845 s
Press any key to continue.

[UncleBazerko]

If outer loop finishes without outputting password and returning it means that we did not find the password, isn't it?

Well yes, which is why I don't want to leave the user hanging around 20 minutes for nothing. It's rude to write programs like that.

How long did you wait? "aaaaaa" is the last password to check, so it would take maximum amount of time for it. You should wait around 5 minutes

I waited well over 5 minutes. I used Coliru, and even after less than 40 seconds, the yellow glowing behind the code (indicating that the code is being executed) stopped. Nothing happened. You are still using Coliru, right?

[MiiNiPaa]

I used Coliru

All online compilers would break execution if it won't finish in set amount of time. It is rarely more than 10 seconds.

If you are writing code which is likely to take more than several seconds to execute, do not use online compilers.

Well yes, which is why I don't want to leave the user hanging around 20 minutes for nothing.

Question was, why do you need to chheck something when we are already know that password was not found.

[dhayden]

A brute force attack will take a lot of time no matter what, but the performance problem with your code is the std::find() call in next(). I profiled it and that call is taking 70% of the time.

One way to solve this is to precompute the next letter. I've sketched it out without your comments here.

bool
next(std::string & in, char nextChar[])
{
    for (std::size_t i = 0; i < in.size(); ++i) {
        if (in[i] == letters[array_size(letters) - 1]) {
            in[i] = letters[0];
        } else {
            in[i] = nextChar[in[i]];
            return true;
        }
    }
    return false;
}

void
print_all()
{
...
    char nextChar[256]= {0};

    for (std::size_t i = 0; i < array_size(letters)-1; ++i) {
        nextChar[letters[i]] = letters[i+1];
    }

    for (std::size_t size = 1; size <= max; ++size) {
        ...
        do {
            if (guess == password) {
                std::cout << "The password is: " << guess << std::endl;
                return;
            }
        } while (next(guess, nextChar));
    }
    std::cout << "Sorry, no matching password was found." << std::endl;
}

A cleaner solution would have nextChar as a static inside next() which gets populated the first time next is called:

bool
next(std::string & in)
{
    static bool first = true;
    static char nextChar[256]= {0};
    if (first) {
        first = false;
        for (std::size_t i = 0; i < array_size(letters)-1; ++i) {
            nextChar[letters[i]] = letters[i+1];
        }
    }
    ...
}

But this kills the performance. In my test, passing nextChar ran in 2.047s compared to 2.953s with nextChar inside next(). This was searching for the password "12345"

[MiiNiPaa]

This is complicates code when OP has trouble with it right now. Lookup table implementation will be fastest, but it is harder to explain. BTW: if using simple char as lookup table key, there is no sense to make table larger than 128 characters without code making sure that it will work, as char is often signed.

Actually it is a good example of algorithm-level optimisation: transforming quadratic algorithm into linear.

Additionally you can do additional work in initialization:

for (std::size_t i = 0; i < array_size(letters)-1; ++i)
    nextChar[letters[i]] = letters[i+1];
nextChar[letters[array_size(letters)]] = letters[0];

and simplify next finding:

for (std::size_t i = 0; i < in.size(); ++i) {
    in[i] = nextChar[in[i]];
    if (in[i] != letters[0])
        return true;
}
return false;