Newsgroup: it.comp.lang.c
Titolo: [lungo] Permutare le lettere di una stringa

Salve a tutti
Ho fatto un piccolo programma che prende in input una stringa di quattro
lettere e restituisce in output tutte le ventiquattro possibili
combinazioni della stringa. Dopo un paio d'ore di bestemmie il programma
sembra funzionare. Il fatto e' che mi sembra un mostro dal punto di
vista dello stile. Possibile che in C non sia possibile fare qualcosa di
piu' compatto e leggibile? Mi son rotto la testa un altro paio d'ore ma
non mi viene in mente niente. Ma sono sicuro che il problema e' mio.
Allora mi son detto proviamo a vedere cosa ne pensano su ICLC.
Segue il codice completo, notare che con questo approccio non e' facile
passare una stringa di piu' di quattro caratteri. Insomma credo di aver
fatto un pasticcio, funzionante, ma pur sempre un pasticcio.
Mi basta solo un piccolo faro che mi indichi la via da seguire.
Grazie a tutti per l'attenzione.
-------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
int
main ()
{
  printf ("inserisci una parola di quattro lettere:  ");
 
  char stringa[5];
  fgets (stringa, 5, stdin);
  int i, n, y, m = 0;
  int count = 0;
  for (i = 0; i <= 3; i++)
    {
      for (n = 0; n <= 3; n++)
	{
	  if ((n == i) && (n != 3))
	    n++;
	  if ((n == 3) && (i == 3))
	    {
	      n--;
	      break;
	    }
	  for (y = 0; y <= 3; ++y)
	    {
	      if ((y == i) && (y != 3))
		++y;
	      if ((y == 3) && (i == 3))
		{
		  y--;
		  break;
		}
	      if ((y == n) && (y != 3))
		++y;
	      if ((y == 3) && (n == 3))
		{
		  y--;
		  break;
		}
	      if ((y == n) || (y == i))
		y++;
	      if (y == 4)
		break;
	      m = (6 - (i + n + y));
	      count++;
	      printf ("%d\t %c%c%c%c\n", count, stringa[i], stringa[n],
		      stringa[y], stringa[m]);
	    }
	}
    }
  return 0;
}
-----------------------------------------------------------------------
P.S. 
Indovinate che romanzo sto leggendo ;-)
-- 
 [Legge degli affitti cittadini] --> Chi non puo' permettersi di
 pagare l'affitto e' in affitto. Chi puo' permettersi di pagare
 l'affitto e' proprietario.

 fatto un pasticcio, funzionante, ma pur sempre un pasticcio.
In effetti il flusso del codice e la sua stessa logica sono stesso
difficili da comprendere o da modificare :)
Perchè non tentare un approccio ricorsivo? Il main potrebbe leggere la
stringa di caratteri di lunghezza arbitraria da processare e poi
passarla ad una funzione che sceglierebbe una lettera per volta,
attraverso un ciclo, e richiamerebbe se stessa passandosi il vettore
originale (o una sua copia), privato però della lettera scelta.
Non so se sono stato chiaro :)
Main riceve "abc"
|
-> funzione riceve "abc"
   |
   :ciclo:
   sceglie e stampa "a",
     richiama se stessa passando "bc"
     |
     ->:ciclo:
       sceglie e stampa "b"
         richiama se stessa passando "c"
         |
         ->:ciclo:
           sceglie e stampa "c"
           :fine ciclo:
       <----
       sceglie e stampa "c"
         richiama se stessa passando "b"
       [...]
       :fine ciclo:
   <----
   sceglie e stampa "b",
     richiama se stessa passando "ac"
   [...]
   sceglie e stampa "c",
     richiama se stessa passando "ab"
   [...]
   :fine ciclo:
   |
<---
Spero il disegno migliori (e non peggiori) la situazione :)
Un approccio del genere sarebbe (credo) abbastanza dispendioso se si
scegliesse di copiare ogni volta il vettore ricevuto, da passare alla
funzione di livello più interno, ma magari con qualche ottimizzazione... ;)
Detta 'n' la lunghezza della stringa, la profondità massima delle
chiamate di funzione sarebbe n, per un totale di n! chiamate.
Magari qualcuno ha un'idea migliore...
Ciao
Dark_Knight

 Dark_Knight
Ciao
Mre`

piu' compatto e leggibile?[...]
Prendi spunto dal seguente codice C++, che ho scritto tempo fa.
Prescinde dalla lunghezza della stringa ed è facile tradurlo in C:
#include <iostream>
#include <string>
using namespace std;
void anagramma(string radice, string s, int livello)
{
     for (int i = 0; i < s.size(); i++){
         string t = radice + s[i];
         if (t.size() == livello)
            cout << t << endl;
 
         anagramma(t, s.substr(0, i) +
                      s.substr(i + 1), 
                      livello);
     }
}
int main()
{
    string my_string;
    cout << "Inserire la stringa da anagrammare : ";
    cin  >> my_string;
    anagramma("", my_string, my_string.size());
    return 0;
}

 te descritto quindi lo posto lo stesso :))
Sicuramente un ottimo punto di partenza.
Ho aggiunto 
#include <stdio.h>
#include <string.h> 
Si compila, ma purtroppo mi ritorna un "Segmentation fault", non sono
ancora padrone dell'arte del debug e non ho capito perche' non funziona.
Ringrazio per l'interessamento.
-- 
 War is NOT the answer, war is the question. The answer is "NO!"

 Prescinde dalla lunghezza della stringa ed è facile tradurlo in C:
Grazie mille anche a te. Datemi un po' di tempo e vediamo cosa riesco a
tirare fuori. La cosa di fa interessante ;-)
-- 
 If God had intended man to use the metric system, Jesus would have
 only had ten disciples.

}
Chiamando la funzione cosi`:
int main(void) {
        char post = "abcd";
        ricurs("", post);
        return 0;
}
Dovrebbe andare. Tra parentesi in C++ il compilatore avrebbe segnalato
la cosa a compile time, perche` le costanti stringa hanno tipo <char
const *>.
Quanto al debug, anche senza essere esperti, ecco cosa si potrebbe fare
con il gcc (o derivati) e gdb:
kronos:/tmp$ gcc -W -Wall -g -o test test.c
test.c: In function 'main':
test.c:29: warning: control reaches end of non-void function
Compilare sempre con tutti i warning attivi (che ci segnala che manda la
return sulla main) e simboli di debug (-g).
kronos:/tmp$ gdb test
Using host libthread_db library "/lib/tls/libthread_db.so.1".
(gdb) run
Starting program: /tmp/test
abcd
Program received signal SIGSEGV, Segmentation fault.
0x080484a6 in ricurs (pre=0xbf9dc970 "abc", post=0x8048640 "d") at test.c:19
19              post[j] = buf[l1];
gdb ci dice dove e` avvenuto il sigsegv, e visto che il programma e`
compilato con -g ci fa vedere anche la linea di codice incriminata.
(gdb) print j
$1 = 0
(gdb) print l1
$2 = 3
(gdb) print buf
$3 = 0xbfb736b0 "abcd"
(gdb) print post
$4 = 0x8048640 "d"
Magari a te non dice nulla, ma l'indirizzo di post (0x8...) mi fa
gridare qualcosa del tipo "ZOMG! Segmento text![1]" ;)
(gdb) bt
#0  0x080484a6 in ricurs (pre=0xbf9dc970 "abc", post=0x8048640 "d") at test.c:19
#1  0x08048469 in ricurs (pre=0xbf9dc9e0 "ab", post=0x804863f "cd") at test.c:15
#2  0x08048469 in ricurs (pre=0xbf9dca50 "a", post=0x804863e "bcd") at test.c:15
#3  0x08048469 in ricurs (pre=0x8048642 "", post=0x804863d "abcd") at test.c:15
#4  0x08048502 in main () at test.c:28
Luca
[1] Ok, tecnicamente .rodata... ma sempre in quella zona ;)
-- 
Home: 
http://kronoz.cjb.net
You and me baby ain't nothin' but mammals
So let's do it like they do on the Discovery Channel

 gridare qualcosa del tipo "ZOMG! Segmento text![1]" ;)
Esatto non dice proprio niente.
Ti ringrazio per l'ottima introduzione al debug.
-- 
 Computer science is no more about computers than astronomy is about
 telescopes <Edsger W. Dijkstra>

 Prescinde dalla lunghezza della stringa ed è facile tradurlo in C:
Questo l'hai postato il primo febbraio, oggi 19 febbraio non sono piu`
tanto convinto di quel "facile". Certo la colpa e` mia. Sono un
ultra-niubbo alle primissime armi. Di C ne so poco di c++ nulla. Ho
dovuto guardare un po` di cose sul c++ per capire il tuo codice. Adesso
mi sembra abbastanza chiaro. Ma quanto al tradurlo in C sono in alto
mare. In special modo mi trovo completamente spiazzato di fronte alle
stringhe. In c++ gestire le stringhe e` decisamente piu` umano. Ma
ripeto l'ignoramza e` la mia. Comunque non demordo, mi son dato come
scadenza la fine di marzo. Il NG mi e` testimone. ;^)
P.S. 
Lo so in C non c'e` la variabile stringa.
P.S.S.
Niente flame sul confronto C e c++, e` solo il parere di un profano.
-- 
 "There is no path to peace. Peace is the path." <Mahatma Gandhi>

stringhe.
Non capisco che cosa ci sia di tanto complicato.  Quando si crea una
stringa, in C, si alloca memoria sufficiente, la si riempie e ci si
assicura che ci sia un terminatore nullo finale.  Piů semplice di cosě
si muore.  D'altronde, cosa ci vuole a scrivere la propria piccola
libreria di metodi che lavorino sulle stringhe alla stregua di quanto
avviene in C++ ?...  Il seguente codice č scritto al volo...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
   char *c_str;
} string_t, *pstring_t;
pstring_t string_new0(void) {
    pstring_t self = malloc(sizeof *self);
    if (self) self->c_str = NULL;
    return self;      
}
pstring_t string_new1(const char *s) {
   pstring_t self = string_new0();
   if (self) {
      self->c_str = malloc(strlen(s)+1);
      if (self->c_str) 
        strcpy(self->c_str, s);
   }
   return self;
}
int string_size(pstring_t self) {
    int result=0;
    if (self && self->c_str) 
      result = strlen(self->c_str);
    return result;
}
pstring_t string_substr(pstring_t self, int start_idx, int end_idx) {
    pstring_t result = NULL;
    if (self) {
       result = string_new0();
       if (result) {
         result->c_str = calloc(end_idx-start_idx+2, 1);
         if (result->c_str) {
           int i;
           for (i=start_idx; i<=end_idx; i++)
              result->c_str[i-start_idx] = self->c_str[i]; 
         }
       }
    }
    return result;
}
pstring_t string_add(pstring_t self, pstring_t s) {
   pstring_t result = NULL;
   if (self) {
      result = string_new0();
      if (result) {
         result->c_str = calloc(string_size(self)+string_size(s)+1,
1);
         sprintf(result->c_str, "%s%s", self->c_str, s->c_str);
      }       
   }
   return result;
}
void string_delete(pstring_t self) {
   if (self && self->c_str) free(self->c_str);
}
int main()
{
    pstring_t s = string_new1("paperino");
    pstring_t substr1, substr2, sum;
 
    printf("s=\"%s\" (size=%d)\n", s->c_str, string_size(s));
    substr1 = string_substr(s, 1, 3);
    substr2 = string_substr(s, 2, 5);
    printf("substr1 = substr(s, 1, 3)=\"%s\" (size=%d)\n",
substr1->c_str, string_size(substr1));    
    printf("substr2 = substr(s, 2, 5)=\"%s\" (size=%d)\n",
substr2->c_str, string_size(substr2));        
    sum = string_add(substr1, substr2);
    printf("substr1+substr2 = \"%s\" (size=%d)\n", sum->c_str,
string_size(sum));
 
    string_delete(s);
    string_delete(substr1);
    string_delete(substr2);
    string_delete(sum);
 
    system("PAUSE");	
    return 0;
}

}
ovviamente questa č:
void string_delete(pstring_t self) {
    if (self) {
       if (self->c_str) free(self->c_str);
       free(self);
    }
}

Giapur ha scritto:

Allora, prima pensiamo all'algoritmo delle permutazioni che piu' o meno
dice:
1) Mantieni la testa e permuta la coda
2) Scambia la testa con ciascun elemento della coda e permuta la coda.
detto questo, in C si traduce grosso modo cosi':
<code>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void swapChar(char* str, int p1, int p2)
{
  char v = str[p1];
  str[p1] = str[p2];
  str[p2] = v;
}
void perm(char* str, int pos)
{
  int len = strlen(str);
  if(pos == len - 1) {
    printf("%s\n", str);
    return;
    }
  perm(str, pos + 1);
  for(int i = pos + 1; i < len; ++i) {
    swapChar(str, pos, i);
    perm(str, pos + 1);
    swapChar(str, pos, i);
    }
}
int main(void)
{
  char* str = "ciao";
  perm(str, 0);
  system("pause");
  return (0);
}
</code>
Ciao

detto questo, in C si traduce grosso modo cosi':
A parte che il tuo codice non è C, ha pure qualche problema ;-)

Andrea Laforgia ha scritto:

forse per l'uso dell'indice [i] nel for? puo' darsi.
L'avevo definito all'inizio della funzione, ma, mentre lo testavo, con
il vecchio Borland 5.02, il suo valore cambiava inaspettatamente, come
se fosse static.
Non ho approfondito perche' non mi interessava piu' di tanto.
Invece di dire che ha qualche problema, perche' non lo espliciti?
Sicuramente non c'è un controllo sull'input, ma negli esempi non ci si
mette mai.
Saluti

logicMind ha scritto:

Mi sono ricordato dov'era il problema dell'indice, era semplicemente
una svista.
Nella parte di confronto del ciclo for, anziche' mettere [i < len], mi
era scappata una [pos < len]. Quindi logico che [i] andasse fuori
range. Dopo aver sistemato, mi e' rimasta la dichiarazione/definizione
di [i] al'interno del for.
Comunque, il vecchio BC 5.02 accetta quel costrutto (ed il file l'avevo
nominato con estensione .C, non .CPP).
Ciao

Invece di dire che ha qualche problema, perche' non lo espliciti?
Tu prima di postare perché non ti accerti di scrivere codice corretto?
Io ho solo provato a eseguirlo con Dev C++ e, bang!, crolla tutto.

 Io ho solo provato a eseguirlo con Dev C++ e, bang!, crolla tutto.
ok, avevo detto di averlo testato col Borland.
Ho riprovato col Dev C++ ed in effetti va in crash. Probabilmente vede
la dichiarazione di str come costante e la mette in memoria non
modificabile.
Basta sostituire:
char* str = "ciao";
con
char str[10];
strcpy(str, "ciao");
non e' comunque un problema dell'algoritmo.
Saluti

 libreria di metodi che lavorino sulle stringhe
Un po' di esperienza, due dita di cervello, e molta pazienza. Tutto
questo IMHO. 
Voglio peraltro dire che ti sono grato per i tuoi post. Gia` solo il
codice che hai postato mi terra` impegnato settimane.
Ma adesso basta con le chiacchere. Ho parlato troppo. Il prossimo post
che invio ci volgio mettere un po' di codice. ;-)
Saluti
-- 
 Principio di Shaw: Fai un programma che anche un idiota puo` usare, e
 soltanto un idiota vorra` usarlo.