Permutation programmieren

sub_zero

Hallo,

ich habe ein kleines Problem: ich benötige eine Funktion, die aus ca. 25 ein- oder zweistelligen Ziffern alle 6-stelligen(!) Kombinationen darstellt. Ich komme einfach nicht drauf, möchte gar keine Lösung, sondern einen Denkanstoss zum Lösungsansatz. Kann jemand helfen?

Danke,
Andreas

Denkanstoss: Wie berechnet man in der Stochastik die Anzahl möglichen Kombinationen?

Denkanstoss2: Fang nicht mit 25 und 6 an; nimm kleine Zahlen und verallgemeinere!

Taurin

sub_zero schrieb:

... aus ca. 25 ein- oder zweistelligen Ziffern alle ...

Was ist eine zweistellige Ziffer?

Edit: Noch ein Denkanstoß: Sowas kann man ganz fein rekursiv lösen.

leo aka qsch

Taurin schrieb:

Was ist eine zweistellige Ziffer?

Taurin schrieb:

Edit: Noch ein Denkanstoß: Sowas kann man ganz fein rekursiv lösen.

mach es lieber linear, das kann man genauso leicht linear wie rekursiv machen und linear ist im allgemeinen immer zu bevorzugen

spjoe

ziffern 2,5 --> n element = 2
k klasses = 6

formel ist: n^k

mfg

Taurin

leo aka qsch schrieb:

mach es lieber linear...

Linear? Was soll das in diesem Zusammenhang bedeuten? Du meinst nicht iterativ?

ziffern 2,5 --> n element = 2
k klasses = 6

formel ist: n^k

Er möchte nicht wissen, wie viele es gibt, er möchte alle Permutationen berechenen und irgendwas damit machen.

spjoe

Die formel is für variation mit wiederholung. des wollte er oda?!

sub_zero

Hallo,

erstmal vielen Dank für die Antworten. Es dürfen keine Wiederholungen vorkommen (sorry, hier war ich etwas unpräzise), wäre sonst ja auch zu einfach. Also nicht einfach n^k sondern eher so:
n!/(k!*(n-k)!). Nur wie packe ich das in eine Funktion? Das Programm soll die verschiedenen Kombinationen nur ausgeben, sonst nichts.

Gruß,
Andreas

Fischi

sub_zero schrieb:

Hallo,

erstmal vielen Dank für die Antworten. Es dürfen keine Wiederholungen vorkommen (sorry, hier war ich etwas unpräzise), wäre sonst ja auch zu einfach. Also nicht einfach n^k sondern eher so:
n!/(k!*(n-k)!). Nur wie packe ich das in eine Funktion? Das Programm soll die verschiedenen Kombinationen nur ausgeben, sonst nichts.

Gruß,
Andreas

Dies hier wäre eine Minimalvariante, die sich noch eignet wenn n und m klein sind. (Funktion berechnet m elementige Teilmenge aus n elementiger Grundmenge)

int m,n;

int *pIndexSet=0;

bool NextValue(int iPosition)
{
if (iPosition<0)
	return false;

pIndexSet[iPosition]++;
if (pIndexSet[iPosition]>(n-m)+iPosition)
	{
	if (!NextValue(iPosition-1))
		return false;
	int max = 0;
	for (int i=0;i<iPosition;i++)
		if (pIndexSet[i]>max)
			max=pIndexSet[i];
	pIndexSet[iPosition] = max+1;
	}
return true;
}

bool GetIndexSet()
{
if (!pIndexSet)
	{
	pIndexSet = new int [m];
	for (int i=0;i<m;i++)
		pIndexSet[i] = i;
	return true;
	}

if (!NextValue(m-1))
	{
	if(pIndexSet)
		delete [] pIndexSet;
	pIndexSet = 0;
	return false;
	}
return true;
}

void main()
{
n=7;
m=5;
while ( GetIndexSet() )
	{
	for (int i=0;i<m;i++)
		printf("%d",pIndexSet[i]);

	printf("\n");
	}

}

Für effektivere Algorithmen:

http://www.theory.csc.uvic.ca/~cos/inf/comb/CombinationsInfo.html

Viele Grüße
Fischi

[EDIT] delete eingefügt [/EDIT]

Taurin

In dem Code oben fehlt ein delete

spjoe

Delete?! sind wir nicht im ansi C forum. Darum meine ich ein free währe hier besser angebracht
mfg