Auflistung aller Groß-Kleinschreibungsmöglichkeiten eines Strings

Tw1x

Hallo Forum,

also wie bereits im Titel vermerkt, ich will ein Progrämmchen schreiben, das mir von einem String (10 Zeichen) alle Möglichkeiten der Groß- und Kleinschreibung ausgibt. Dazu habe ich mir gedacht, ich nehme eine (binäre) Zahl von 0 bis 127 (1111111) (der String enthält 3 Zahlen, die man natürlich in Frieden lassen muss...), welche direkt die jeweilige Möglichkeit darstellt. Um dann die einzelnen Bits der binären Zahl auf 1 und 0 zu überprüfen verwende ich in der inneren for-Schleife ein if(i & j), was dann nicht 0 ist, wenn der jeweilige Bit auf 1 ist, den ich untersuche (ich lege halt ne Bitmaske über meine 0 - 127 Zahl - also z.b. für das 4. Bit die 8 (0001000)).
Hier jetzt erstmal mein Programmcode und dann noch einige Erklärungen:

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>

int main(void) {
	int i, j;
	char test[] = "v76tcthg4j";
	char temp[] = "1234567890";
	strcpy(temp, test);
	for(i = 0; i < 128; i++) { // Möglichkeiten der Schreibung
		for(j = 1024; j > 0; j/=2) { // Einzelne Bits für die Buchstaben prüfen
			if(i & j) {
				if(!isdigit(temp[(int)log2(j)])) {
					temp[(int)log2(j)] = toupper(temp[(int)log2(j)]);
				}
			}
		if((i+1) < 10)
			printf("  %d. Möglichkeit: %s\n", i+1, temp);
		else if((i+1) < 100)
			printf(" %d. Möglichkeit: %s\n", i+1, temp);
		else
			printf("%d. Möglichkeit: %s\n", i+1, temp);
		strcpy(temp, test);
	}
}

Compiled wird das ganze mit

gcc sourcecode.c -lm

wegen der math.h include... (ja ich arbeite mit Linux^^)

Die äußere for-Schleife repräsentiert alle Möglichkeiten der Groß- und Kleinschreibung (2⁷, da 7 Zeichen á 2 Zustände).
Die innere for-Schleife soll, wie oben erwähnt, die einzelnen Bits des i (0 - 127) überprüfen um, wenn das jeweilige Bit gesetzt ist, in den if-Bedingungen den Buchstabe an der Stelle in einen Großbuchstabe zu ändern.
Die beiden If-Bedingungen sind dazu da, um außen das Bit zu prüfen, und innen zu prüfen, ob das Zeichen, das geändert werden würde, überhaupt ein Buchstabe ist (was passiert wohl, wenn man eine Zahl "groß" schreibt xD).
Der log2 ist deswegen da, damit der gerade aktive Schleifendurchlauf berechnet wird (innere for-Schleife). (Das spart halt 1 weitere Laufvariable ein.)

Der Rest mit dem 3-fachen printf() ist nur zur Schönheit da, damit auf der shell das Ganze perfekt untereinander ist (man beachte die Leerzeichen vor dem 1. %d).
Das strcpy() füllt meinen temporären String wieder mit der rohen Zeichenkette von ganz oben.

Dann ist die äußere Schleife wieder dran und es geht auf ein Neues wieder los.

Jetzt zum Problem:
Das Schöne ist ja ein Erfolgserlebnis bei einem 2. Progrämmchen mit der Zeichenkette "asdf", da sind alle 16 Möglichkeiten ausgespuckt worden. Jetzt ist die Situation eben durch die 10 Zeichen, wovon nur 7 Buchstaben sind, etwas anders und ich weiß nicht mehr weiter, denn die Ausgabe jetzt ist folgende (nur ein kleiner Ausschnitt):

1. Möglichkeit: v76tcthg4j
  2. Möglichkeit: V76tcthg4j
  3. Möglichkeit: v76tcthg4j
  4. Möglichkeit: V76tcthg4j
  5. Möglichkeit: v76tcthg4j
  6. Möglichkeit: V76tcthg4j
  7. Möglichkeit: v76tcthg4j
  8. Möglichkeit: V76tcthg4j
  9. Möglichkeit: v76Tcthg4j
 10. Möglichkeit: V76Tcthg4j
 11. Möglichkeit: v76Tcthg4j
 12. Möglichkeit: V76Tcthg4j
 13. Möglichkeit: v76Tcthg4j
 14. Möglichkeit: V76Tcthg4j
 15. Möglichkeit: v76Tcthg4j

Ausgegeben werden alle 128 Möglichkeiten, 1 & 3; 2 & 4 und noch einige mehr Zeilen sind jedoch exakt dasselbe! Ich weiß einfach nicht mehr weiter, wo mein Denkfehler bei der kleinen Steigerung von 4 Zeichen auf 10 Zeichen liegt und frage deshalb jetzt hier nach.

Ich hoffe ihr könnt mir helfen, bei fehlenden Informationen oder Sonstigem stehe ich natürlich gerne bereit!

Beste Grüße
Tw1x

PS: gibt's hier keinen ausdrucksvolleren "mad"-Smiley!?

Wie ist denn die Großziffer von 7 ?

Tw1x

ähm, Großziffer!?
Was meinst du mit Großziffer von 7?

SeppJ

Tw1x schrieb:

ähm, Großziffer!?
Was meinst du mit Großziffer von 7?

Wie sieht eine groß geschriebene '7' aus?

Tw1x

haha, lol xD

Nein, also wie oben erwähnt, die Zahlen werden ja ignoriert... hoffe ich zumindest.

Bei der Umwandlung schon.
Aber nicht bei der Ausgabe.

Und schau dir mal die Möglichkeiten der Formatspecifier von printf an. Das f bedeutet da übringes formatiert. Ok probier mal

printf("%3d. Möglichkeit: %s\n", i+1, temp);

Tw1x

Ok, also das %3d bringt ja nur die Einrückung (wie gesagt, die Ausgabe ist ja eigentlich egal...), was ich aber nicht verstehe ist, warum die Buchstabenkombinationen doppelt und dreifach vorkommen, es soll ja jede Kombination 1 einziges Mal vorkommen, also so nach dem Motto:

v76tcthg4j
v76tcthg4J
v76tcthG4j
v76tcthG4J
//und so weiter...

Es listet aber bereits mit der 2. Möglichkeit ein großes "V" auf, es sollte lauf 0000001 aber klein sein...

Sonst noch Vorschläge vielleicht?

EOP

Hab ich irgendwannmal geschrieben. Ist zwar WIN, aber du wirst das Prinzip verstehen.

private:
	std::wstring m_input;
	size_t m_len; // length of m_input
	std::vector<std::wstring> m_vResults; // results

Aufruf:

RecGenerate( m_input, 0 );

void CGenerator::RecGenerate( std::wstring output, size_t pos )
{
	TCHAR ch = output.at( pos );
	if( _istalpha( static_cast<wint_t> (ch) ) )
		ch = flip( ch );
	else ch = _T('\0');

	if( pos < m_len )
	{
		RecGenerate( output, pos + 1 );
		if( ch )
		{
			output.replace( pos, 1, 1, ch );
			RecGenerate( output, pos + 1 );
		}
	}
	else
	{
		//wcout << output << endl;
		m_vResults.push_back( output );
		if( ch )
		{
			output.replace( pos, 1, 1, ch );
			//wcout << output << endl;
			m_vResults.push_back( output );
		}
	}
} // void CGenerator::RecGenerate( std::wstring output, size_t pos )

TCHAR flip( TCHAR ch )
{
	wint_t wc = static_cast<wint_t> (ch);
	if( _istalpha( wc ) )
	{
		if( _istupper( wc ) )
			ch = _totlower( ch );
		else
			ch = _totupper( ch );
	}
	return( ch );
}

Tw1x

Hallo,

danke für eure Antworten, die letzte Antwort verstehe ich gar nicht, das heißt, ich verstehe noch "void" und andere Schlüsselwörter, aber da ich ein ziemlicher Anfänger bin, verstehe ich von dem Code gar nichts...

Ich habe mir mein Programm nochmal angeschaut und jetzt die Reihenfolge umdrehen wollen, mit der das aufgelistet wird (nicht mehr vorne groß-klein-groß-klein-... sondern hinten an den Strings); habe das auch jetzt geschafft, durch die Einführung einer weiteren Zählvariable k, die ich statt dem log2-Zeugs da verwende.
Dann ist mir noch aufgefallen, dass ich die 128 in der inneren for-Schleife falsch gewählt habe, da muss ne 64 hin. Somit hab ich die Lösung fast, jetzt nur noch schnell die Zahlen ignorieren lassen und nochmal testen, dann funktionierts.
Ich werde die lauffähige Lösung hier noch reineditieren, danach kann geclosed werden.

EOP

Tw1x schrieb:

die letzte Antwort verstehe ich gar nicht, das heißt, ich verstehe noch "void" und andere Schlüsselwörter, aber da ich ein ziemlicher Anfänger bin, verstehe ich von dem Code gar nichts...

Ja, eigentlich wundere ich mich selber was ich da zusammengebastelt habe. Aber es fumktioniert. Auch mit Zahlen, Sonderzeichen.

Jetzt, da du deine Aufgabe selber gelöst hast, kann ich ja meinen Ansatz zeigen.

int main(void) {
  int i, j, k;
  char test[] = "v76tcthg4j";
  const int test_size = strlen(test);
  for(i = 0; i < (1<<(test_size - 3)); i++) {
    printf("%3d. Möglichkeit: ", i+1);
    for (j=k=0; j<test_size; j++, k++) {
      while (isdigit(test[j]))
        putchar(test[j++]);
      putchar((i & (1<<k)) ? toupper(test[j]) : test[j]);
    }
    putchar('\n');
  }
}

@EOP: Das ist der Beweis, dass man mit ein bisschen C-Kenntnis viel weiter kommt als mit ein bisschen C++-Kenntnis. Dein Code ist langsam (O(2^(alphas+nonalphas)) statt O((2^alphas)+nonalphas), Rekursion, Zwischenspeichern in vector) und umständlich (win-zeugs, m_len redundand, Rekursion, warum replace, Pseudo-OOP).

EOP

Was ist denn an m_len redundant? Ich brauch ja ne Abbruchbedingung für die Rekursion. So berechne ich sie einmal und "gut is".

Du hast doch schon m_input.length() ?

Tw1x

Ok, das "reineditieren" von meinem letzten Post einfach wegdenken, habe es nicht geschafft, die Zahlen mit rein zu kriegen...

Mein Dank geht an hsrtrzh<W4, dankesehr, dein Code funktioniert perfekt... nahezu perfekt zumindest, werde die Reihenfolge noch umdrehen, will nämlich, dass am Stringende zuletzt das Zeichen variiert wird, also so:

...
V76TCTHg4j
V76TCTHg4J
V76TCTHG4j
V76TCTHG4J

Wie ich sehe, arbeitest du mit Bitverschiebung? (Bitverschiebungen mag ich gar nicht, die verstehe ich zwar grad so, aber ich finde die so unübersichtlich...)
Könntest du den Code noch ausführlich kommentieren, dass ich ihn verstehe? Funktionieren tut er ja...

Danke für die Lösung des Problems!

EOP

@ hsrtrzh<W4

Versuch mal dein Programm mit

char test[] = "g4j";

oder

char test[] = "g4jx";

und dann test mal meins.

Fällt dir was auf?

Tw1x

Ich verstehe nicht ganz, bist du sicher dass du den

char test[]

und nicht den

char temp[]

meintest?

Ich stelle nur fest, dass es mit dem x ca. 10 mal jede Möglichkeit auflistet, also z.B.
128.
128.
128.
...

aber ich verstehe nicht ganz, was du meinst... oder meinst du die Unabhängigkeit des Input-Strings bei deinem Code? Das weiß ich schon, das ist nur für genau den String der Code von mir^^

Tw1x

So, hab die Lösung von hsrtrzh<W4 umgeschrieben, dass er mir den Output in ne *.txt schreibt, und bin vorerst befriedigt mit dem Ergebnis.

Danke für die schnelle Hilfe; hach, ich liebe Foren! xD

Beste Grüße & gn8
Tw1x

EOP

original:

char test[] = "v76tcthg4j";

und mit

char test[] = "g4j";

Ausgabe:
1. Möglichkeit "g4j"
und das war's dann schon auch.

Ihr macht's euch aber kompliziert.

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

void print_permutations_aux(char *s, size_t pos) {
  if(s[pos] == '\0') {
    puts(s);
  } else if(isalpha(s[pos])) {
    s[pos] = toupper(s[pos]);
    print_permutations_aux(s, pos + 1);
    s[pos] = tolower(s[pos]);
    print_permutations_aux(s, pos + 1);
  } else {
    print_permutations_aux(s, pos + 1);
  }
}

void print_permutations_inplace(char *s) {
  print_permutations_aux(s, 0);
}

void print_permutations(char const *s) {
  char *p = malloc(strlen(s) + 1);
  strcpy(p, s);
  print_permutations_inplace(p);
  free(p);
}

int main() {
  print_permutations("g4jx");

  return 0;
}

EOP

Dumme Frage:
Wofür ist print_permutations_inplace nötig? (Bin nicht mehr ganz nüchtern).

E#1:
Ah, wohl für free.

E#2:
Nö wohl doch nicht.