Kombinationsmöglichkeiten II

[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;

}