std::next_permutation

Hey,

ich habe z.B. ein set:

std::set<char> dictionary = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
								  'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F',
								  'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
								  'W', 'X', 'Y', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0' };

Hiervon möchte ich alle Möglichen 5stelligen Kombinationen generieren lassen.
Bin auf std::next_permutation gestoßen, nur wie beschränke ich das auf eine Länge von 5?

Grüße

Columbo

Hiervon möchte ich alle Möglichen 5stelligen Kombinationen generieren lassen.

Ich glaub' nicht dass du genug Speicher dafür hast.

Fytch

Das sind schon ohne Wiederholung etwa 777 Mio. Möglichkeiten. std::next_permutation ist hierbei nicht sonderlich gut geeignet (was nicht bedeutet, dass sich nicht ein umständliches Beispiel konstruieren lässt, das std::next_permutation nutzt).

Aber bitte:

#include <set>
#include <array>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
	// typedef std::set<char> DictType; // std::set-Iteratoren sind AFAIK langsam
	typedef std::array<char, 26 * 2 + 10> DictType;
	const DictType dictionary = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p',
								 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F',
								 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
								 'W', 'X', 'Y', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
	enum
	{
		CombinationLen = 5
	};

	std::array<DictType::const_iterator, CombinationLen> Stack;
	Stack.fill(std::begin(dictionary));

	typedef std::array<DictType::value_type, CombinationLen> CombinationType;
	std::vector<CombinationType> Combinations;

	for(std::size_t Depth = 0; ;)
	{
		if(Stack[Depth] == std::end(dictionary))
		{
			Stack[Depth] = std::begin(dictionary);
			if(Depth == 0)
			{
				break;
			}
			else
			{
				--Depth;
				++Stack[Depth];
			}
		}
		else
		{
			auto CurrentPos = std::next(std::begin(Stack), Depth);
			if(std::find(std::begin(Stack), CurrentPos, Stack[Depth]) != CurrentPos)
			{
				++Stack[Depth];
			}
			else
			{
				if(Depth + 1 != CombinationLen)
				{
					++Depth;
				}
				else
				{
					CombinationType NewComb;
					for(std::size_t i = 0; i < CombinationLen; ++i)
					{
						NewComb[i] = *Stack[i];
					}
					Combinations.push_back(NewComb);
					++Stack[Depth];
				}
			}
		}
	}

	for(auto const& Entry : Combinations)
	{
		for(auto Char : Entry)
		{
			std::cout << Char << ' ';
		}
		std::cout << '\n';
	}
}

Edit: Mein Code gibt auch Kombinationen ohne Wiederholungen aus, ansonsten wäre es trivial.

Moechtest Du alle geordneten Kombinationen haben, d.h. {a, b, c, d, e} != {e, d, c, b, a} oder spielt die Ordnung keine Rolle?

Columbo

Ohne Beachtung der Reihenfolge könnte es so aussehen:

#include <iostream>

int main()
{
	char const chars[] = "abcdefghijklmnopqrstuvwxyz"
	                     "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	                     "0123456789";

	for (std::size_t a = 4; a != sizeof chars - 1; ++a)
	for (std::size_t b = 3; b != a; ++b)
	for (std::size_t c = 2; c != b; ++c)
	for (std::size_t d = 1; d != c; ++d)
	for (std::size_t e = 0; e != d; ++e)
		std::cout << chars[e] << chars[d] << chars[c] << chars[b] << chars[a] << '\n';
}