alle Reihenfolgen durchgehen

MisterVista

Hallo,

ich steh vor einem Problem und weiß nicht wie ich es lösen kann.
Wenn ich zum Beispiel ein x beliebiges Array oder einen String habe, und alle möglichen Reihengolgen durchgehen möchte, wie kann ich das realisiere?

Beispiel:

int A [] = {1, 2, 3}
// Alle mögliche Reihenfolgen
// 1, 2, 3
// 1, 3, 2
// 2, 1, 3
// 3, 1, 2
// 2, 3, 1
// 3, 2, 1

Wie könnte man dies lösen?

Mfg, MisterVista

Probier das mal, hab ich laut Filedatum irgendwann 1996 mal verbrochen:

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

char ein [21];        // Zeiger auf den Eingabestring max. 20 zeichen + \0
char *aus;            // Zeiger auf den Ausgabestring
int  leng;            // Anzahl der Zeichen im Eingabestring
int  anzz = 0;        // Anzahl ausgegebener Zeilen  

void rek (char *x)
/***********************************************/
/*  Rekursive Funktion zur Ermittlung s„mtli-  */
/*  cher Kombinationen der Zeichen im Eingabe- */
/*  string                                     */
/*  Eingabe:  Zeiger auf das erste Zeichen im  */
/*            Eingabestring (global definiert) */
/*  Ausgabe:  šber den Zeiger <aus> (global)   */
/*  Vorbereitung:                              */
/*            Globale Variable (int) leng      */
/*            enth„lt Anzahl der Zeichen im    */
/*            Eingabestring                    */
/***********************************************/
{
  int i;                           // Laufvariable

  if (*x != '\0')
  {
    for (i=0; i < leng; i++)       // Zeichen auf allen Positionen einsetzen
    {
      if (aus[i] == ' ')           // wenn Position unbesetzt,      
      {                            // Zeichen einsetzen und mit n„chstem
        aus [i] = *x   ;           // Zeichen weitermachen
        rek (x+1)     ;
        aus [i] = ' '  ;           // Position wieder l”schen
      }
    }
  }       
  else
  {
    printf ("\n%s", aus) ;
    anzz++               ;
    if (anzz == 24)
    {
      printf ("\n               --- Weiter mit Tastendruck ---") ;
      getch ()     ;
      anzz = 0     ;
    }
  }
}  

void getein (void)
/***********************************************/    
/*  Eingabestring holen und L„nge ermitteln    */
/***********************************************/
{
  clrscr ()        ;           // Bildschirm l”schen

  printf ("Bitte geben Sie den Eingabestring ein ...\n") ;

  scanf ("%20s", ein)  ;       // Eingabe entgegennehmen max. 20 Zeichen

  leng = strlen (ein)  ;       // Tats„chliche L„nge ermitteln 
}     

void getmem (void)
/***********************************************/
/*  Speicher fr Ausgabestring reservieren und */
/*  initialisieren                             */
/***********************************************/
{
  aus = malloc (leng + 1) ;    // Speicher (Anzahl Zeichen + \0 reservieren

  aus [leng] = '\0'       ;    // Ausgabestring mit Space + \0 
  memset (aus, ' ', leng) ;    // initialisieren
}

void main (void)
/***********************************************/
/*        H A U P T F U N K T I O N            */
/***********************************************/
{  
  getein ()           ;       // hol Eingabe
  getmem ()           ;       // Speicher fr den Ausgabestring besorgen

  rek (ein)           ;       // Los gehts

  free (aus)          ;       // Speicher fr Ausgabestring wieder freigeben
}

_matze

Na Belly, du trennst deine Semikola aber strikt vom restlichen Code!

Hehe, wie gesagt, ist uralt ...
Ich kann mich noch erinnern, es gab ein Kreuzworträtsel mit 8 Lösungsbuchstaben, die das richtige Lösungswort ergaben - man mußte sie halt in die richtige Reihenfolge bringen.
Das Programm hat mich nicht wirklich weitergebracht, da es rund 42000 Zeilen ausspuckt.
Ich habe noch eine Version, die doppelte Lösungen - wenn ein oder mehr Buchstaben mehr als einmal vorkommen - eliminiert, aber das war dann nur noch so eine Spielerei ...

MisterVista

Danke, klappt!
Die abgewandelte Version für merhrfach vorhandene Charaktere würde mich auch interessieren. Könntest du sie reinstellen?

A votre service:

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

char ein [21];        // Zeiger auf den Eingabestring max. 20 zeichen + \0
char *aus;            // Zeiger auf den Ausgabestring
int  leng;            // Anzahl der Zeichen im Eingabestring

int biswert [21];     // hier wird je Zeichen im Eingabestring festgehalten,
                      // wieweit es im Zielstring nach rechts geschoben
                      // werden soll - abh„ngig von der H„ufigkeit des 
                      // Zeichens

void rek (int pos, int von, int bis)
/***********************************************/
/*  Rekursive Funktion zur Ermittlung s„mtli-  */
/*  cher Kombinationen der Zeichen im Eingabe- */
/*  string                                     */
/*  Eingabe:  Zeiger auf das erste Zeichen im  */
/*            Eingabestring (global definiert) */
/*  Ausgabe:  šber den Zeiger <aus> (global)   */
/*  Vorbereitung:                              */
/*            Globale Variable (int) leng      */
/*            enth„lt Anzahl der Zeichen im    */
/*            Eingabestring                    */
/***********************************************/
{
  int i ;                           // Laufvariable

  if (ein[pos] != '\0')
  {
    for (i=von; i < bis; i++)       // Zeichen auf allen Positionen          
    {                               // von bis einsetzen
      if (aus[i] == ' ')            // wenn Position unbesetzt,      
      {                             // Zeichen einsetzen und mit n„chstem
        aus [i] = ein[pos]   ;      // Zeichen weitermachen
        rek (pos+1, ein[pos] == ein[pos+1] ? i+1 : 0, biswert[pos+1])  ;
        aus [i] = ' '  ;           // Position wieder l”schen
      }
    }
  }       
  else
  {
    printf ("\n%s", aus) ;
  }
}  

void getein (void)
/***********************************************/    
/*  Eingabestring holen und L„nge ermitteln    */
/***********************************************/
{
  clrscr ()        ;           // Bildschirm l”schen

  printf ("Bitte geben Sie den Eingabestring ein ...\n") ;

  scanf ("%20s", ein)  ;       // Eingabe entgegennehmen max. 20 Zeichen

  leng = strlen (ein)  ;       // Tats„chliche L„nge ermitteln 
}     

void getmem (void)
/***********************************************/
/*  Speicher fr Ausgabestring reservieren und */
/*  initialisieren                             */
/***********************************************/
{
  aus = malloc (leng + 1) ;    // Speicher (Anzahl Zeichen + \0 reservieren

  aus [leng] = '\0'       ;    // Ausgabestring mit Space + \0 
  memset (aus, ' ', leng) ;    // initialisieren
}

int sort (char *a, char *b)
/***********************************************/
/*  Vergleichsfunktion fr die Sortierung      */
/***********************************************/
{                                        
  return (*a - *b) ;
}

void fillbis (void)
/***********************************************/
/*  Fr mehrfach vorkommende Zeichen wird ab-  */
/*  h„ngig von ihrer Position bestimmt, wie    */
/*  weit sie nach rechts geschoben werden      */
/***********************************************/
{
  int i ;

  biswert [leng] = leng  ;

  for (i = leng - 1; i >= 0; i--)
  {
    if (ein [i] == ein [i+1])
       biswert [i] = biswert [i+1] - 1  ;
    else
       biswert [i] = leng           ;
  }
}

void main (void)
/***********************************************/
/*        H A U P T F U N K T I O N            */
/***********************************************/
{  
  getein ()           ;       // hol Eingabe
  getmem ()           ;       // Speicher fr den Ausgabestring besorgen
  qsort (ein, leng, 1, (int (*) ()) sort); // sortieren des Eingabestrings

  fillbis ()          ;       // Endposition je Zeichen festlegen

  rek (0,0,biswert[0])           ;       // Los gehts

  free (aus)          ;       // Speicher fr Ausgabestring wieder freigeben
}