Aus Buchstaben Vorgabe (abcd) alle möglichen Keys berechnen.

Hi zusammen,

ich versuche gerade aus einer Buchstaben vorgabe wie z.B "abcd" alle weiteren möglichen keys zu erzeugen wie z.B

abcd
aabc
cbad
... und der rest eben.

ich scheitere momentan an der umsetzung. Vielleicht kann mir einer von Euch einen Tip geben.

MG80S

Ich hätte eine wage Lösung im Kopf.....wage, sehr wage...

Du könntest aus der Länge des Keys folgende Permutationen ableiten:

0000
0001
0002
0003
0010
0011
.
.
3333

Also mit ein paar Schleifen könntest Du das schonmal realisieren. Und nun steht im Beispiel eine 0 für a usw. bis 3 für d.

Wie gesagt, ist wage, aber als Tip vielleicht brauchbar....

masterofx32

#include <windows.h>
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char* argv[]) {

	char *str = new char[101];
	char *digits = new char[36];
	char *tmp = new char[60];

	unsigned int digitcount = 0;

	ZeroMemory(str,101);
	ZeroMemory(digits,26);
	ZeroMemory(tmp,60);

	cin.getline(str,100,'\n');

	//Jedes Zeichen des Strings durchlaufen und überprüfen, ob bereits vorhanden
	for (size_t i=0;i<strlen(str);i++) {
		//Alle vorhanden Zeichen durchsuchen
		bool bZeichenvorhanden = false;

		for (unsigned int j=0;j<digitcount;j++) {
			if (str[i]==digits[j]) {
				bZeichenvorhanden = true;
			}
		}
		//Zeichen nocht nicht vorhanden > hinzufügen
		if (!bZeichenvorhanden) {
			digits[digitcount++] = str[i];
		}
	}

	if (digitcount > 8) {
		cout << "Zu viele Kombinationen" << endl;
		return 0;
	}
	cout << "Enthaltene Zeichen:" << digits << endl;

	int combinations = (int)pow((int)digitcount,(int)digitcount);
	char **result = new char*[combinations];

	for (int i=0;i<combinations;i++) {
		result[i] = new char[digitcount+1];
		ZeroMemory(result[i],digitcount+1);

		//In String unter Nutzung des vorhandenen Ziffernvorrats umwandeln
		itoa(i,tmp,digitcount);

		size_t len = strlen(tmp);

		if (len<digitcount) {
			//Führende Nullen anhängen
			FillMemory(result[i],digitcount-len,'0');
		}
		//In Zielarray kopieren
		strcpy(result[i]+(digitcount-len),tmp);

		for (int j=0;j<digitcount;j++) {
			//Ziffern durch Zeichen des Zeichenvorrats ersetzen
			result[i][j] = digits[result[i][j]-48];
		}
	}

	for (int i=0;i<combinations;i++) {
		cout << result[i] << " : ";
	}

	delete[] tmp;
	delete[] str;
	delete[] digits;

	return 0;
}

Ich bitte um Verzeihung bezüglich der Nutzung von ZeroMemory, etc

Ponto

Ein rekursiver Algorithmus findet sich unter:

http://www.c-plusplus.net/forum/viewtopic.php?t=84995

ssm

[cpp]#include <string>
#include <iostream>
#include <algorithm>

int main()
{
std::string str = "abcd";
while(std::next_permutation(str.begin(), str.end()))
{
std::cout << str << std::endl;
}
}[/cpp]

Ponto

ssm schrieb:

[cpp]#include <string>
#include <iostream>
#include <algorithm>

int main()
{
std::string str = "abcd";
while(std::next_permutation(str.begin(), str.end()))
{
std::cout << str << std::endl;
}
}[/cpp]

Erstens unterschlägt der Code die erste Permutation und zweitens ist hier gar nicht nach den Permutationen gefragt worden.

ssm

Ponto schrieb:

Erstens unterschlägt der Code die erste Permutation

richtig

Ponto schrieb:

zweitens ist hier gar nicht nach den Permutationen gefragt worden.

masterofx32

Na sowas, ich denke mal, ich war mit meiner Lösung etwas verplant
Werde ich mich eben zurück in mein Loch verkriechen

MG80S

Ich hätte noch was zu meiner wagen Idee oben. Allerdings "nur" C, funktioniert aber:

#include<stdlib.h>
#include<stdio.h>

int main()
{
	char *eingabe = new char[20];
	int *digits, i, laenge;
	printf("Ursprungs-Key:");
	scanf("%s",eingabe);
	laenge = strlen(eingabe);
	digits = new int[laenge+1];
	for(i=0; i<=laenge; i++)
	{
		digits[i] = 0;
	}
	do
	{
		printf("\n");
		for(i=0; i<laenge; i++)
		{
			printf("%c", eingabe[digits[i]]);
		}
		digits[0]++;
		for(i=0; i<laenge; i++)
		{
			if(digits[i]>=laenge)
			{
				digits[i] = 0;
				digits[i+1]++;
			}
		}
	}
	while(digits[laenge] == 0);
	printf("\n");
	delete digits;
	delete eingabe;
	return(0);
}

Seit wann gibt es in C new und delete?

MG80S

Okay, sorry. Halt so n Mischmasch-Zeug. Musste schnell gehen :p

Green_Ghost

So geht es schneller.
Die function hab ich von dem Link.

#include <string> 
#include <iostream> 

using namespace std; 

void k(std::string const & f, std::string const & result,  int len) 
{ 
  if (len == 0) { 
    std::cout << result << std::endl; 
    return; 
  } 
  std::string temp = result + " "; 
  for (std::string::size_type i = 0; i != f.size(); ++i) 
  { 
    temp[temp.size()-1] = f[i]; 
    k(f, temp, len-1); 
  } 
}

int main(){
  string eingabe,tmp;
  cin>>eingabe;
  int a=eingeb.size();
  k(eingabe,tmp,a);
  return 1;
}

Blackhawk

die std:: kannst du in void k weglassen

und in der sig bitte nur BBCode kein HTML verwenden ^^