brute forcing a monoalphabetic cipher

[unregistered]

I know there are other better ways to break it like statistical analysis but I was wondering how do I generate the entire keyspace of 26! without having 26 nested loops or so.

assuming I have an array
char key[26];
which will be initialized to each key in the entire keyspace on each pass, how do I go about creating such an algorithm?

[R0mai]

See: http://cplusplus.com/forum/articles/25291/#msg135148

or you can use std::next_permutation()
http://cplusplus.com/reference/algorithm/next_permutation/
which essentially does the same as helios' solution.

[Galik]

I'd use a vector to keep track of the loop position for each variable in the permutation, a kind of 'permutation register':

#include <iostream>
#include <vector>

const size_t KEY_SIZE = 26;

int main()
{
	// Value set
	const std::string V = "abcdefghijklmnopqrstuvwxyz";

	// Key
	std::string K(KEY_SIZE, 0);

	// Permutation register
	std::vector<size_t> P(K.size(), 0);

	// Repeat while more permutations
	for(size_t p(0); p < P.size();)
	{
		// Generate key
		for(size_t k(0); k < K.size(); ++k) { K[k] = V[P[k]]; }

		// Use key
		std::cout << "key: " << K << '\n';

		// Increment permutation register
		for(p = 0; p < P.size() && ++(P[p]) >= V.size(); P[p++] = 0);
	}
}

[unregistered]

@Galik
hey, your solution worked but can you explain the logic on the permutation register especially the Increment permutation register part?

[Galik]

The permutation register is a vector of indices into V, the set of possible values. So if P[0] has the int value of 2, that 2 is an index into the string V and represents a char 'c'. So by incrementing P[0] I can extract any value from set V.

So what I am doing is giving the first element of P (being P[0]) an increasing value until it is too large to index V because it has run out of chars. When that happens I reset P[0] to 0 (indexing a again) and move on to the next element of the permutation register P[1].

But note that I only move on to P[1] if P[0] reached its limit. And also with P[1], I increment it and then only if it reached its limit, do I reset it to 0 and move up to P[2].

So, in this line here:

for(p = 0; p < P.size() && ++(P[p]) >= V.size(); P[p++] = 0);

I am using p as a counter through the elements of P. Starting with element 0 I increase its value by one. Only if its value reaches the largest value in V do I reset its value to 0 and move up to the next value.

It is analogous to the decimal counting system when you increment the first column and if it reaches 9 you have to return it to 0 and increment the next highest column in sequence. And in turn, if that digit has already reached 9 then it is reset to 0 and you move up to the next highest column and so on until you increment a digit that does not cause an increment to the next digit.

So, the above code is equivalent to:

		// Increment permutation register

		// Starting from element 0
		for(p = 0; p < P.size(); ++p)
		{
			// increment that element
			P[p]++;

			// Is this element larger as large as
			// the number of elements in V?
			if(P[p] >= V.size())
			{
				// If so return its value to 0 and move on
				// to the next value
				P[p] = 0;
			}
			else
			{
				// Otherwise stop looping because we
				// need to try these values before moving
				// on to the next.
				break;
			}
		}