Kombinationsmöglichkeiten eines char Arrays berechnen

Hey Leute,

Ich suche z.Z. vergeblich nach einer einfachen Lösung sämtliche Kombinationsmöglichkeiten des Inhaltes eines char Arrays zu berechnen und auszugeben. Beispiel:

char array[3] = "ABC";

Ausgabe:
A
B
C
AA
AB
AC
BB
BC
CC
AAA
AAB
AAC
ABA
ACA
ABB
ACC
ABC
ACB
und so weiter

Das ganze halt mit einer vordefinierten Länge(hier z.B. 1-3).

Mir fällt im Moment leider nichts brauchbares ein.

Danke im voraus!

MfG Endl

//Edit:
Habe einen fehler bei den 2er Gruppen gemacht sollte so aussehen:

AA
AB
AC
BB
BA
BC
CC
CB
CA

drakon

Sowas lässt sich sehr elegant rekursiv lösen.
Wenn es effizienter sein soll kannst du dir einfach überlegen, dass du ja zuerst mal alle Zeichen ausgeben sollst, welche die Länge 1 haben, dann mit der Länge 2 usw.
Analog, wie man auch mit Zahlen hinaufzählt.

darkfate

drakon schrieb:

Sowas lässt sich sehr elegant rekursiv lösen.

Rekursive Lösungen sind leider nur in der Theorie elegant.

Hier haben wird man über n! Knoten rekursiv iterieren müssen was für den Stack sicherlich unschön ist.

darkfate schrieb:

Hier haben wird man über n! Knoten rekursiv iterieren müssen was für den Stack sicherlich unschön ist.

So ein Quatsch!

Es kommt auf die Tiefe des "Aufruf-Baums" an und nicht, wieviele "Knoten" der hat, was im übrigen auch nicht n! gewesen wäre. Die Tiefe des "Aufruf-Baums" bei so einem rekursiven Ansatz für das Aufzählen aller Kombinationsmöglichkeiten der Länge n wäre n selbst. Das ist natürlich kein Problem für den automatischen Speicher.

kk

darkfate

krümelkacker schrieb:

..

Immer deine sinnlosen Beiträge. Wie schon so oft gesagt: Wenn du nicht hilfst oder einen sinnvollen Beitrag zu melden hast, dann melde dich doch einfach nicht. Es nutzt nichts wenn du aus deinem Keller mit Kraftausdrücken schreibst die du in der Öffentlichkeit niemals von dir geben würdest.

Jede Rekursion bringt eine Rücksprungadresse mehr auf dem auf 1MB begrenzten Stack. Somit stellt es sicherlich ein Problem dar.

Zu deinem zweiten sinnlosen Kommentar. Alleine die Anzahl der Permutationen sind n! da fehlen auch noch diese Teilpermutationen.

volkard

krümelkacker hat aber sowas von recht.
do weißt, was passiert, wenn man mehr als 69 elemente zum permutieren hat? du kannst die rechenzeit nicht mehr mit dem schultaschenrechner berechnen. und 69 dinge passen eigentlich meistens vielleicht schon gelegentlich auf den stack.

Nexus

darkfate schrieb:

Immer deine sinnlosen Beiträge. Wie schon so oft gesagt: Wenn du nicht hilfst oder einen sinnvollen Beitrag zu melden hast, dann melde dich doch einfach nicht.

Sinnlos war das garantiert nicht. Deine Aussagen werden nicht wahrer, indem du andere schlecht machst.

Bei Beispiel des Threaderstellers sind es drei Zeichen. Das sind drei Rekursionsebenen. Du hast in jedem komplexeren Programm die hundertfache Aufruftiefe und es stört niemanden.

Natürlich musst du das Problem nicht rein funktional angehen und auch die Zeichen auf gleicher Ebene mit Rekursion behandeln.

darkfate schrieb:

...

Klarer Fall: [SELF](OWNED)

darkfate

volkard schrieb:

krümelkacker hat aber sowas von recht.

Hat er eben nicht. Er wusste doch gar nicht wie ich es bei der ersten Betrachtung implementieren würde? Ich bitte mal an dieser Stelle um eine Antwort woher du wusstest wie ich es geplant habe?

volkard schrieb:

do weißt, was passiert, wenn man mehr als 69 elemente zum permutieren hat? du kannst die rechenzeit nicht mehr mit dem schultaschenrechner berechnen. und 69 dinge passen eigentlich meistens vielleicht schon gelegentlich auf den stack.

Diese Begründung ist absolut Nachvollziehbar. Nachdem ich auch ein wenig rumprobiert habe, bin ich auch darauf gekommen, dass es besser und schneller geht. Wenn er so geantwortet hätte, würde es auch keinen Flame geben. Er ist wie immer der Brandherd.

Nexus schrieb:

Sinnlos war das garantiert nicht. Deine Aussagen werden nicht wahrer, indem du andere schlecht machst.

Immer wieder das Problem. Er hat angefangen. Wie kommst du auf die Idee das ich ihn schlechter mache als er ist? Wieso sprichst du jetz mich an? Steht mein Post vor seinem?

Nexus schrieb:

Das sind drei Rekursionsebenen. Du hast in jedem komplexeren Programm die hundertfache Aufruftiefe und es stört niemanden.

So intelligent konnte man argumentieren. Hat er aber nicht.

xDDDD schrieb:

darkfate schrieb:

...

Klarer Fall: [SELF](OWNED)

Komm lass gut sein krümmelkacker, hier weiß jeder dass es nur einen gibt der auf so ein Niveau sinken kann, da hilft auch kein neuer nick.

Ich poste mal einen ersten Ansatz ohne Gewähr auch Typsicherheit/undefiniertes Verhalten und Sonstiges... damit der Thread wenigstens einen Sinn hat.

#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;
}

Ist aber wie man sieht nur rekursiv und kein C++

volkard

darkfate schrieb:

volkard schrieb:

krümelkacker hat aber sowas von recht.

Hat er eben nicht. Er wusste doch gar nicht wie ich es bei der ersten Betrachtung implementieren würde? Ich bitte mal an dieser Stelle um eine Antwort woher du wusstest wie ich es geplant habe?

Weil ich angenommen hatte, daß Du schlau bist. Ich fürchte, nach Deinem letzen Posting kannst Du das in Bezug auf Permutationenprogrammierung auch nicht mehr so recht leugnen. hihi.
Naja, eventuell ist dies oder jenes einen MOment zu spät oder zu früh gesagt worden, aber alles im Bereich, wie es für mich gut verständlich ist und kein Grund für rote Köpfchen .

darkfate

Nexus schrieb:

Bei Beispiel des Threaderstellers sind es drei Zeichen.

Endl schrieb:

sämtliche Kombinationsmöglichkeiten des Inhaltes eines char Arrays zu berechnen und auszugeben

Jetzt könnte ich genau so antworten wie Krümmelkacker in seinem ersten Post mit: SO EIN QUATSCH! Ist es angenehme Antwort nachdem du sein Anliegen nicht richtig verstanden hast so wie ich im ersten Moment anscheinend keine optimale Lösung hatte? Nein ist es nicht. Da wird aber kein Wort in seine Richtung gesprochen der es permanent fast in jedem Post macht. Scheuklappen?

Ein char Array kann auch laenger als drei Zeichen sein. Hat nirgendwo geschrieben dass es nur drei Zeichen sein sollen.

darkfate

volkard schrieb:

Weil ich angenommen hatte, daß Du schlau bist.

Tja..

volkard schrieb:

Ich fürchte, nach Deinem letzen Posting kannst Du das in Bezug auf Permutationenprogrammierung auch nicht mehr so recht leugnen. hihi.

Ich hatte Zorn und wollte bei dem ganzen Ärger wenigstens eine Lösung bieten damit der Fragende nicht andauernd Flame lesen muss.

volkard schrieb:

Naja, eventuell ist dies oder jenes einen MOment zu spät oder zu früh gesagt worden, aber alles im Bereich, wie es für mich gut verständlich ist und kein Grund für rote Köpfchen .

Nein eben nicht. Dieser Krümmelkacker buksiert andauernd mit seinen absolut Sinnlosen kommentaren die eher Zorn als Hilfe bringen.

Michael E.

darkfate schrieb:

volkard schrieb:

krümelkacker hat aber sowas von recht.

Hat er eben nicht. Er wusste doch gar nicht wie ich es bei der ersten Betrachtung implementieren würde? Ich bitte mal an dieser Stelle um eine Antwort woher du wusstest wie ich es geplant habe?

Wen interessiert, wie du es geplant hast? Du kannst die rekursive Lösung nicht dadurch schlecht machen, dass du sie total verunstaltest.

So intelligent konnte man argumentieren. Hat er aber nicht.

Ich erkenne bei ihm mehr Argumentation als bei dir => eigene Nase.

darkfate

Michael E. schrieb:

Wen interessiert, wie du es geplant hast?

Lies erst einmal um was es geht.

Michael E. schrieb:

Ich erkenne bei ihm mehr Argumentation als bei dir => eigene Nase.

Lies doch einmal den Thread durch bevor du schreibst.

Michael E. schrieb:

Du kannst die rekursive Lösung nicht dadurch schlecht machen, dass du sie total verunstaltest.

Was ist denn dass bitteschön für eine Aussage? Wo ist da der Bezug zu überhaupt irgend etwas?

Nexus

darkfate schrieb:

Immer wieder das Problem. Er hat angefangen. Wie kommst du auf die Idee das ich ihn schlechter mache als er ist? Wieso sprichst du jetz mich an? Steht mein Post vor seinem?

Ich habe nirgends gesagt, dass ich krümelkackers "So ein Quatsch!" gut finde. Aber du lässt dich auch wirklich sehr leicht provozieren. Immerhin hat krümelkacker nebenbei sachlich geantwortet und dir das Problem erklärt, du solltest seinen Post nicht auf einen Flame reduzieren. Ich habe auch nicht das Gefühl, dass das "So ein Quatsch" allzu persönlich gemeint ist (auch wie ich krümelkacker vom Forum hier kenne). Bei "deine Posts sind immer sinnlos" fällt es mir hingegen schon schwerer, das zu glauben.

Ich will damit nur sagen, dass du in Zukunft vielleicht etwas lockerer reagieren und nicht gleich alle Kritik als feindselig erachten solltest. Und Rechtfertigungen wie "er hat angefangen" hast du nun wirklich nicht nötig.

unskilled

warum hat bisher eigtl niemand std::next_permutation vorgeschlagen?

mindestens für die n-elementigen geht das super - für die ein- und zweielementigen(bzw nicht n-elementigen) fällt mir zugegebenermaßen keine super-tolle idee damit ein...

bb

volkard

Es paßt zwar nicht mehr ganz so ins C++-Forum, und ich müßte eigentlich dichtmachen, aber ich lasse den Thread mal laufen.
Der Fragesteller Endl kann sich ja die benötigten Informationen herausziehen.
Zu Permutationen gibts AFAIR sigar eibnen Artikel im Magazin. http://www.c-plusplus.net/forum/viewtopic-var-t-is-178286-and-postdays-is-0-and-postorder-is-asc-and-start-is-0.html
Hier waren nur Kombinationsmöglichkeiten gefragt, fürchte ich. Die würde ich nichtmal rekursiv machen. Das geht auch wie ein mechanischen Zählwerk http://de.wikipedia.org/w/index.php?title=Datei:Handzaehler01_clip.jpg&filetimestamp=20060614112826 irgendwie.

volkard

unskilled schrieb:

warum hat bisher eigtl niemand std::next_permutation vorgeschlagen?

Da hatten wir bis gerade Glück gehabt. Weil es nicht um die 3!=6 Permutaionen von ABC geht, sondern um die 3^3=27 Kombinationen. Um Genau zu sein, um die 3^2 zweibuchstabigen und 3^1 einbuchstabigen auch, aber das kann ein Schleifchen außenrum ja gut machen.

darkfate

Nexus schrieb:

Ich habe nirgends gesagt, dass ich krümelkackers "So ein Quatsch!" gut finde.

Nutzt nichts wenn du aber nur meinen Post anmerkst. Ist nicht das erste mal übrigens.

Nexus schrieb:

Aber du lässt dich auch wirklich sehr leicht provozieren.

Weil es eben wie gesagt nicht das erste mal ist. Und es ist nicht das erste mal das komischerweise keiner seinen absolut unnötigen Kommentar bemängelt.

Nexus schrieb:

Immerhin hat krümelkacker nebenbei sachlich geantwortet und dir das Problem erklärt,

Super damit wäre ich glücklich. Ich habe noch nie Jemanden angepöbelt der mir sachlich kritisch geantwortet hat.

Nexus schrieb:

du solltest seinen Post nicht auf einen Flame reduzieren.Ich habe auch nicht das Gefühl, dass das "So ein Quatsch" allzu persönlich gemeint ist (auch wie ich krümelkacker vom Forum hier kenne).

Wenn ich mich mit dir unterhalte und dich zwischendurch beleidige dann versuch du mal das Gespräch nicht auf die Beleidigungen zu reduzieren. Erst recht wenn es der erste Satz war.

Nexus schrieb:

Bei "deine Posts sind immer sinnlos" fällt es mir hingegen schon schwerer, das zu glauben.

Geh doch seine Posts durch. Er hat eine total unverschämte Art. Wenn manch einer sich das bieten lässt ist es ok... ich nicht.

Nexus schrieb:

Ich will damit nur sagen, dass du in Zukunft vielleicht etwas lockerer reagieren und nicht gleich alle Kritik als feindselig erachten solltest. Und Rechtfertigungen wie "er hat angefangen" hast du nun wirklich nicht nötig.

Wie gesagt, wenn er so reden möchte, soll er es Zuhause bei seinen Eltern/Freunden oder wem auch immer tun. Ich möchte das nicht.

Michael E.

darkfate schrieb:

Michael E. schrieb:

Wen interessiert, wie du es geplant hast?

Lies erst einmal um was es geht.

Hab ich.

Michael E. schrieb:

Ich erkenne bei ihm mehr Argumentation als bei dir => eigene Nase.

Lies doch einmal den Thread durch bevor du schreibst.

Hab ich immer noch.

Michael E. schrieb:

Du kannst die rekursive Lösung nicht dadurch schlecht machen, dass du sie total verunstaltest.

Was ist denn dass bitteschön für eine Aussage? Wo ist da der Bezug zu überhaupt irgend etwas?

Zum von mir Zitierten.

Aber da ich weiß, dass du sowieso ein hoffnungsloser Fall bist, bin ich auch schon wieder weg