Kombinationsmöglichkeiten II

[The_Fury]

Hey,

Da mir volkard in meinem letzten Thread dazu geraten hat einen Neuen aufzumachen, tue ich das jetzt.

Diesmal aber mit dem eigentlichen Problem.
Ich habe z.B.folgendes Array:

char set[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";

Jetzt möchte ich aus diesem Array sämtliche Kombinationsmöglichkeiten für Strings berechnen und zwar mit der Länge 1-10.

Also:
A
B
..
AA
BB
AB
..
AAAABC2FsK
usw.

Und bevor jetzt jemand sagt dass es ziemlich viele davon gibt(ca. 1,527375914832281763277376583922*e^6223 Möglichkeiten)

und diese sehr viel Speicherplatz fressen würden wenn ich sie in eine TXT schreibe, ich weiß das, ich habe etwas anderes damit vor.

PS: bitte diesmal kein geflame wer wann mit was angefangen hat

//EDIT: Mir ist desweiteren klar dass es genug Wordlists und Rainbowtables im Net gibt.. diese lösen mein Problem aber leider nicht.

MfG Fury

[darkfate]

Es gibt doch genügend Passwortlisten im Internet die sogar gezippt mehrere Gigabytes groß sind. Da sind auch Sonderzeichen dabei.

Für 1-10 müsste mein geposteter Algorithmus locker langen.

Ich ziehe mal den ersten rekursiven Ansatz hier rüber:

#include <stdio.h>
#include <string.h>
static int t=1;
void permutiere(char *eingabe, char *permutation);
char *substr (const char *eingabe, int start, int laenge);

int main() {

	char wort[] = "AB";
	int i,n = (int) strlen(wort);

	for(i=0;i<n;i++){ 
		char *tmpword = malloc((i+1)*sizeof(char));
		t=0;
		tmpword = substr(wort,0,i+1);
		permutiere(tmpword,tmpword);
	}

	printf("Entgueltige Tiefe %i\n",t);
	return 0;
}

void permutiere(char *eingabe, char *permutation) {

	char *tausche,*selbst;
	char tempwort;
	t++;

	if (*(permutation+1) == 0) printf("%s\n", eingabe);
	else {
		for(tausche = permutation; *tausche; ++tausche) {
			for(selbst = permutation; *selbst != *tausche; ++selbst);
			if (selbst == tausche) {
				tempwort = *tausche;
				*tausche = *permutation;
				*permutation = tempwort;
				permutiere(eingabe, permutation+1);
				*permutation = *tausche;
				*tausche = tempwort;
			}
		}
	}
}

char *substr (const char *eingabe, int start, int laenge) {
	char *puffer;
	if (eingabe == NULL) return NULL;
	if (start < 0) start = strlen (eingabe) + start;
	if (start < 0) start = 0;
	if (laenge < 0) laenge = 0;
	if (start >strlen (eingabe)) start = strlen (eingabe);
	if (laenge > strlen (&eingabe[start]))  laenge = strlen (&eingabe[start]);
	if ((puffer= (char*) malloc (laenge + 1)) == NULL) return NULL;

	memcpy (puffer, &(eingabe[start]), laenge);
	puffer[laenge] = '\0';

	return buff;
}

Hier ein nicht rekursiver Ansatz:
Das kann man intelligenter wie eine n dimenionale quadrik aufspannen, ganz ohne Rekursion.

hier in 3D in Buchstaben:

ABC
ACB
BAC
BCA
CBA
CAB

hier 3D in Koordinaten einer einfachen Ebene

-X-----Y-----Z-
0.0 - 1.0 - 2.0
0.0 - 2.0 - 1.0
1.0 - 0.0 - 2.0
1.0 - 2.0 - 0.0
2.0 - 1.0 - 0.0
2.0 - 0.0 - 1.0

Wenn man das erste Array anschaut muss man einfach nur eine Sequenz erzeugen.
Jedes Element n-1 mal wiederholen.

Das zweite Array beginnend mit dem zweiten Element bis zum ersten Element. Dann beginnend mit dem dritten Element bis zum ersten Element usw..

Das dritte Element ist keines der ersten beiden.

Nur für diese Anfangssequenz müsste man sich etwas überlegen.

Man braucht halt drei Arrays mit n³-2n²+n Elementen. Dürfte theoretisch besser sein als andauern Rücksprungadressen auf dem Stack abzulegen. Außerdem kann man damit schön Mehrkernprozessoren auslasten.

Ein dritter Ansatz ist einfach eine Sequenz zu erzeugen die folgendes Berücksichtigt:
ABC - ABC
ACB - ACB
BAC - BAC
BCA - BCA
CBA - CBA
CAB - CAB

[Nukularfüsiker]

Artikel über Permutationen inkl. passender Lösung in C++.

Ich ziehe mal den ersten rekursiven Ansatz rüber:

Es war C++ gefragt

[darkfate]

Nukularfüsiker schrieb:

Artikel über Permutationen inkl. passender Lösung in C++.

Ich ziehe mal den ersten rekursiven Ansatz rüber:

Es war C++ gefragt

Kann man ja noch gerne umschreiben Eine andere Lösung als Rekursiv und bereits vorhandene Lösungen wäre auch mal wieder schön.

[knivil]

ca. 1,527375914832281763277376583922*e^6223 Möglichkeiten

Nein, es gibt 853'058'371'866'181'866 Moeglichkeiten. Also etwa 10^24. Aber irgendwo musst du sie ja speichern, wenn du damit was machen willst.

[krümelkacker]

The_Fury schrieb:

char set[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";

Jetzt möchte ich aus diesem Array sämtliche Kombinationsmöglichkeiten für Strings berechnen und zwar mit der Länge 1-10.

Wenn Du hier "xxx" durch "xxxxxxxxxx" ersetzt und "ABC" durch "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890" ersetzt, dann macht das Programm dort genau das, was Du willst -- abgesehen von der Reihenfolge. Zunächst werden alle 10-stellingen Kombis generiert, dann die 9-stellingen, u.s.w. Aber das solltest Du ohne Probleme umdrehen können.

@darkfate: Es geht hier nicht um Permutationen.

@knivel: also etwa 10^18

[knivil]

Aehm, ja 3*6 = 18. im uebrigen favorisieren ich meine Loesung in Haskell von hier. C oder C++ ist dafuer denkbar ungeeignet.

[darkfate]

knivil schrieb:

C oder C++ ist dafuer denkbar ungeeignet.

Ich finde es gibt für Berechnungen nichts besseres als C/C++ weil es die einzige Sprache ist, für die es GPGPU Interface für alle Grafikkarten gibt.

Für diese Aufgabe sind acht Threads eines üblichen i7 Quads zu wenig.
Dauert einfach zu lang.

[The_Fury]

knivil: wie kommst du auf 10^24? das wären dann die Möglichkeiten allein für 10 stellige Strings bei einem Array mit der Größe 24, soweit ich weiß.
Zur Speicherung: ich will das Ganze nirgendwo Speichern sondern die Ketten zur Laufzeit ausarbeiten, sobald das funktioniert werde ich dann voraussichtlich eine Funktion Implementieren in der das Ganze dann schon berechnet und verschlüsselt steht(will eine Art MD5/MD4/SHA1/usw Cracker programmieren(nein ich habe damit nichts 'böses' vor ich mach das nur um mich weiterzubilden)).

Ansonsten möchte ich mich recht herzlich für die schnelle Hilfe bedanken, habe mein Problem gelöst indem ich eure Sources als Vorlage verwendet habe.

//Edit: darkfate: genau das habe ich vor

MfG Fury

[knivil]

wie kommst du auf 10^24?

Ich komme auf 10^18 und zwar durch den Hinweis "Länge 1-10". Dein Pool "ABCDE..90" hat 62 Zeichen. Es gibt 62 Moeglichkeiten fuer Woerter der Laenge 1, 62*62 Moeglichkeiten der Laenge 2, 62^3 Moeglichkeiten der Laenge 3, .. 62^10 Moeglichkeiten der Laenge 10. Addiert man diese, so komme ich auf eben diese Zahl.

[Martin Richter]

Viel Spaß beim Warten auf das Ergebnis:

#include "stdio.h"
#include "string.h"

void Fill(char* str, const char* szCharSet, size_t iPos, size_t iMaxLen)
{
	if (iPos==iMaxLen)
	{
		str[iMaxLen] = 0;
		puts(str);
		return;
	}

	// add each possible character
	for (size_t i=0, iChars=strlen(szCharSet); i<iChars; ++i)
	{
		str[iPos] = szCharSet[i];
		// Do the same for the remaining positions
		Fill(str,szCharSet,iPos+1,iMaxLen);
	}
}

void Fill(const char* szCharSet, size_t iMaxLen)
{
	char* szWork = new char[iMaxLen+1];
	for (size_t  iLen=1; iLen<=iMaxLen; ++iLen)
		Fill(szWork,szCharSet,0,iLen);
	delete [] szWork;
}

int _tmain(int argc, _TCHAR* argv[])
{
	const size_t MAX_LEN = 10;
	const char CHARSET[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";

	Fill(CHARSET,MAX_LEN);
	return 0;
}

Rekursionstiefe maximal 10.
Anzahl 62¹⁺⁶²2+62^3+...+6210 = ca. 8,53*10^17

[volkard]

Martin Richter schrieb:

...

Die ist aber hübsch.

[drakon]

Martin Richter schrieb:

...

Ich habe so ziemlich das gleiche gemacht für eine rekursive Lösung. Wollte es eigentlich gestern mal noch posten, aber da volkard angedroht hat den alten Thread zu löschen habe ich es gelassen.
Habs Heute nochmal (zwecks Syntaxübung) auch mal noch in Eiffel gemacht, aber es nicht gwagt das mal mit einem grösseren Quelle als 3 zu testen.

Ich habe lediglich den Teil mit den führenden Leerzeichen wahrscheinlich umständlicher gemacht. War doch ein wenig umständlicher, als ich gedacht habe. Habe mir das eher als 5-10 Zeiler vorgestellt mit einer Rekursiven Lösung.

[warum nicht so?]

ohne Rekursion, ohne max länge, mit C++:

#include <vector>
#include <cstddef>

template<typename T>
void brute_force( const T* const pool_beg, std::size_t length )
{
    const T* const pool_end = pool_beg + length;
    std::vector<const T*> position;
    std::vector<T> current_combination;

    for(;;) //alternativ eine maximale länge als abbruchbedingung
    {
        typename std::vector<T>::size_type j = 0;

        for(; j != current_combination.size(); ++j)
        {
            ++position[j];
            if(position[j] != pool_end )
            {
                current_combination[j] = *position[j];
                break;
            }
            else
            {
                position[j] = pool_beg;
                current_combination[j] = *pool_beg;
            }
        }
        if(j == current_combination.size())
        {
            position.push_back(pool_beg);
            current_combination.push_back(*pool_beg);
        }

        //ausgeben oder was auch immer von current_combination
    }
}

#include <string>

int main()
{
    std::string pool = "ABC";
    brute_force(&pool[0], pool.size());
}

[Martin Richter]

Und noch einer, nicht rekursiv mit einfachen Datentypen...

#include "stdio.h"
#include "string.h"

void Fill2(const char* szCharSet, size_t iMaxLen)
{
	size_t iChars=strlen(szCharSet);

	// buffer to build and buffer to track permutation count
	char* szWork = new char[iMaxLen+1];
	size_t *aUsage = new size_t[iMaxLen];
	// Just init with the start combination (position 0)
	for (size_t i=0; i<iMaxLen; ++i)
		szWork[i] = szCharSet[aUsage[i] = 0];
	szWork[iMaxLen] = 0;

	for (;;) 
	{
		// Output current combination (may be the first)
		puts(szWork);

		// get next iteration (start at end)
		size_t iPos;
		for (iPos=iMaxLen; iPos; iPos--)
		{
			szWork[iPos-1] = szCharSet[++aUsage[iPos-1]];
			if (aUsage[iPos-1]<iChars)
				break;
			else
				// Need to change previous position, so reset current
				szWork[iPos-1] = szCharSet[aUsage[iPos-1] = 0];	
		}

		// reached the end (overflow)
		if (iPos==0)
			break;
	}

	delete [] szWork;
	delete [] aUsage;
}

void Fill(const char* szCharSet, size_t iMaxLen)
{
	for (size_t  iLen=1; iLen<=iMaxLen; ++iLen)
		Fill2(szCharSet,iLen);
}

int _tmain(int argc, _TCHAR* argv[])
{
	const size_t MAX_LEN = 10;
	const char CHARSET[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";
	Fill(CHARSET,MAX_LEN);
	return 0;
}

[knivil]

@warum nicht so?: Warum uebergibst du die maximale Laenge nicht als Parameter? Endlosschleifen sind nicht so der Bringer.

Im uebrigen vermisse ich eine Iteratorloesung. Ein einfaches ++ sollte dann zur naechsten Kombination fuehren. Das waehre auch sinnvoll, wenn man nicht alle Moeglichkeiten generieren will, sondern sie nach und nach bearbeiten moechte.

[krümelkacker]

Mir war grad langweilig. Noch eine iterative Version:

#include <iostream>
#include <vector>
#include <string>

using std::vector;
using std::string;

void next(vector<int> & v, int base)
{
  unsigned pos = 0;
  while (pos<v.size()) {
    if (++v[pos] < base) return;
    v[pos++] = 0;
  }
  v.push_back(0);
}

void print(vector<int> const& v, string const& cset)
{
  for (unsigned i=v.size(); i-->0;) {
    std::cout << cset[v[i]];
  }
  std::cout << '\n';
}

int main()
{
  const string cset = "ABC";
  const unsigned maxlen = 3;
  const unsigned base = cset.size();
  vector<int> x;
  for (;;) {
    next(x,base);
    if (x.size()>maxlen) break;
    print(x,cset);
  }
}

kk

[warum nicht so?]

Martin Richter schrieb:

Und noch einer, nicht rekursiv mit einfachen Datentypen...

Für die einfachen Datentypen kannst du das template ja spezialisieren.

knivil schrieb:

@warum nicht so?: Warum uebergibst du die maximale Laenge nicht als Parameter? Endlosschleifen sind nicht so der Bringer.
Im uebrigen vermisse ich eine Iteratorloesung. Ein einfaches ++ sollte dann zur naechsten Kombination fuehren. Das waehre auch sinnvoll, wenn man nicht alle Moeglichkeiten generieren will, sondern sie nach und nach bearbeiten moechte.

Das Problem beim Durchiterieren ist, dass man bei jeder "Stelle" der kombination checken muss, an welchem Ort im Pool sie gerade steht. In meiner Funktion speichere ich das in Positions.
Ein iterativer Ansatz sähe so aus (jetzt lexikalisch korrekt):

#include <vector>
#include <cstddef>

template<typename T>
bool generate_next_combination(const T* pool_beg,
                               std::size_t length,
                               std::vector<T>& current_combination,
                               std::size_t max_length)
{
    int j = current_combination.size()-1;

    for(; j >= 0; --j) //rückwärts für lexikalische Richtigkeit
    {
        for(typename std::vector<T>::size_type i = 0; i != length; ++i)
        {
            if(current_combination[j] == pool_beg[i])
            {
                if(i+1 != length)
                {
                    current_combination[j] = pool_beg[i+1];
                    return true;
                }
                else
                    current_combination[j] = *pool_beg;
            }
        }
    }
    if(j < 0)
    {
        if(current_combination.size()==max_length)
            return false; //vll vector noch clearen
        current_combination.insert(current_combination.begin(),*pool_beg); //neues element vorne hinzufügen. Vll anderer Container als vector
    }
    return true;
}

#include <string>
#include <iostream>

int main()
{
    std::string pool = "10";
    std::string start_key = "100";
    std::vector<char> key (start_key.begin(), start_key.end());

    std::sort(pool.begin(), pool.end());
    //std::unique(pool.begin(), pool.end());

    while( generate_next_combination( &pool[0], pool.size(), key, 4 ) )
        std::cout<<std::string(key.begin(), key.end())<<std::endl;

}