n-Tupel, Anzahl der Möglichkeiten auflisten

[seth]

gudn tach!

wie sieht denn das ganze aus, wenn ich anstatt die ziffern 0-9 die elemente a-z haben möchte?
geht das auch damit?

nicht ganz so einfach, aber fast.
wenn du rekursionen vermeiden willst, dann gibt es u.a. folgende moeglichkeit:
bei einer laenge von insg. n zeichen eines alphabetes mit m zeichen, also z.b. n=5 (laenge) und m=26 (anzahl der zeichen im alphabet), koenntest du eine bijektion zwischen den zahlen von 0 bis (m^n)-1, hier also 0 bis (26^5)-1, und den worten aaaaa bis zzzzz erstellen. "bijektion" heisst, dass du jeder zahl von 0 bis (26^5)-1 genau ein "wort" aus aaaaa bis zzzzz zuweist.
das geht z.b. indem du die zahl ganzzahlig durch 26 teilst, dann das ergebnis durch 26, dann dessen ergebnis usw. insg. n mal. der jeweilge rest wird einem zeichen zugeordnet. 0 fuer a, 1 fuer b, ... 25 fuer z.
allgemein:
gegeben sei die zahl x:
  x/m = a_1 rest r_1 (merke r_1 fuer die n-te stelle)
a_1/m = a_2 rest r_2 (merke r_2 fuer die (n-1)-te stelle)
a_2/m = a_3 rest r_3 (merke r_3 fuer die (n-2)-te stelle)
...
a_{n-2}/m = a_{n-1} rest r_{n-1} (merke r_{n-1} fuer die zweite stelle)
a_{n-1}/m = a_n rest r_n (merke r_n fuer die erste stelle)

r_1, r_2, ..., r_{n-1}, r_n muss nun nur noch zeichenweise uebersetzen und ist fertig.

ein paar beispiele sollen das verdeutlichen:
die zahl 0:
0/26 = 0 rest 0 (merke 0 fuer die fuenfte stelle)
0/26 = 0 rest 0 (merke 0 fuer die vierte stelle)
0/26 = 0 rest 0 (merke 0 fuer die dritte stelle)
0/26 = 0 rest 0 (merke 0 fuer die zweite stelle)
0/26 = 0 rest 0 (merke 0 fuer die erste stelle)
0,0,0,0,0 -> aaaaa
fertig.

die zahl 1:
1/26 = 0 rest 1 (merke 1 fuer die fuenfte stelle)
0/26 = 0 rest 0 (merke 0 fuer die vierte stelle)
0/26 = 0 rest 0 (merke 0 fuer die dritte stelle)
0/26 = 0 rest 0 (merke 0 fuer die zweite stelle)
0/26 = 0 rest 0 (merke 0 fuer die erste stelle)
0,0,0,0,1 -> aaaab

die zahl 26:
26/26 = 1 rest 0 (merke 0 fuer die fuenfte stelle)
 1/26 = 0 rest 1 (merke 1 fuer die vierte stelle)
 0/26 = 0 rest 0 (merke 0 fuer die dritte stelle)
 0/26 = 0 rest 0 (merke 0 fuer die zweite stelle)
 0/26 = 0 rest 0 (merke 0 fuer die erste stelle)
0,0,0,1,0 -> aaaba

die zahl 123456:
123456/26 = 4748 rest  8 (merke  8 fuer die fuenfte stelle)
  4748/26 =  182 rest 16 (merke 16 fuer die vierte stelle)
   182/26 =    7 rest  0 (merke  0 fuer die dritte stelle)
     7/26 =    0 rest  7 (merke  7 fuer die zweite stelle)
     0/26 =    0 rest  0 (merke  0 fuer die erste stelle)
0,7,0,16,8 -> ahaqi

hilfsmittel hierfuer sind:
modulo-operator (fuer den jeweiligen rest), ganzzahlige division.

falls die kombinationen die anzahl der verfuegbaren zahlen uebersteigt, so sollte man sich aber besser ein eigenes zahlen-system basteln, das die eigenschaften des dezimalsystems imitiert, bis auf die tatsache, dass es nicht zehn sondern eben m verschiedene "ziffern" gibt. z.b. so: (ich verwende abkuerzende pseudo-code-schreibweisen)

max_ziffer = 26-1;             // (anzahl der alphabet-zeichen)-1, weil man in c-aehnlichen sprachen normalerweise bei 0 anfaengt zu zaehlen.
anz_ziffern = 5;               // laenge des wortes
zahl[0..(anz_ziffern-1)] = 0;  // die zahl werde durch ein array repraesentiert
while(incr(zahl, max_ziffer)){ // erhoehe wert in array jeweils um 1
  print zahl2wort(zahl);       // gebe zur zahl gehoerendes zeichen aus
}

function incr(&zahl, max_ziffer){ // call-by-reference: "erhoehe" zahl
  last = length(zahl);            // letzte ziffer
  ++zahl(last);                   // erhoehe letzte ziffer
  for i=last backto 1{            // laufe rueckwaerts durchs array
    if(zahl[i]>max_ziffer){       // uebertrag?
      zahl[i]=0;
      if(i>0) ++zahl[i-1];
      else return false;          // falls zahl groesser als erlaubt
    }
  }
  return true;
}

function zahl2wort(z){            // ersetze zahl durch buchstaben
  return_char='';
  for i=1 to length(z){
    return_char.=ascii(z[i]+97);// 97='a'
  }
  return return_char;
}

alles ungetestet, aber die idee sollte klar sein.

prost
seth