[?] Aiuto programma

[keratox]

Vorrei fare un programma, indipendentemente dal linguaggio (java,c,c++,pascal). In pratica vorrei che, data una serie di lettere, trovi ogni combinazione possibile (delle lettere) scartando quelle gia' venute.

Per dire, se io do' in input 'due' mi deve dare:

due
ude
ued
eud
deu

non so come procedere, chiedo aiuto

ciao

[anx721]

Supponiamo che le lettere siano n e siano date in input come una stringa s di lunghezza n. Tutte le combinazioni le mettiamo in un Vettore di stringhe. La mia idea è di utilizzare una procedura ricorsiva che prende in input una stringa s e ti restituisce il vettore di tutte le sue combinazioni. Se la lunghezza di s è 1, la procedura ritorna semplicemente un vettore contenete la stringa s stessa perche se ha lunghezza pari a 1 non puo avere altre combinazioni. Se no la procedura chiama ricorsivamente se stessa su una stringa più corta, ovvero su s meno il primo carattere. Sia a il primo carattere di s e indichiamo con (s/a) s meno il primo carattere a. Con la chiamata ricorsiva su (s/a) si ottengono tutte le combinazioni di (s/a); d'altro canto, data una combinazione di (s/a), se inserisco a in una qualsiasi posizione ottengo proprio una combinazione di s. Allora tutte le combinazioni di s le posso ricostruire inserendo in ogni combinazione di (s/a) il carattere a in tutte le possibili posizioni (ovvero nella prima, nella seconda, nella terza,ecc ecc). In questo modo dalle combinazion di (s/a) riesco a costruire tutte le combinazioni di s.

Un abbozzo di codice è il seguente:

Vector combination(String s){
     Vector v = new Vector();
     if(s.length == 1){
         v.add(s);
         return v;
      }
      String newString;
      //Richiamo ricorsivamente sulla sottostringa di
      //s a paritre dal 2 carattere
      Vector temp = combination(s.substring(1, n));
      //Per ogni combinazione di (s/a)...
      for(int i = 0; i < temp.size(), i++){
            //per ogni posizione...
            for(int j = 0; j <= s.lenght; j++){
                newString = stringa ottenuta da temp[i] inserendo 
                nella j° posizione il primo caratttere di s;
                v.add(newString);
            }
      }
      return v;
} 

Supponendo che il numero di lettere da costruire tute le combinazioni non sia elevato, come efficienza puo andare. In forma iterativa potrebbe essere fatto piu efficientemente, ma scrivendo piu codice, in quanto se, dato che il numero di lettere da permutare non è fissato a priori, non è semplicissimo gestire gli indici.

[Eyescream]

uppo che mi interessa,
cmq le combinazioni di tot lettere sono il fattoriale del numero di lettere ( X! = 1 * 2 * 3 * ... * X)