DUBBIO PROGRAMMA!

di il
5 risposte

DUBBIO PROGRAMMA!

Salve ragazzi...questo che vi posto è un programma per generare tutte le permutazioni di un vettore di caratteri...è abbastanza comprensibile da leggere...ma ho un problema..che anche se a me sembra tutto giusto...funziona solo alcune volte, ma non sempre...anzi...sn più le volte che nn lo fa!...da osservare che questo mio metodo di creare le permutazioni non le crea tutte in ordine..ma le crea mischiate insomma!....il problema è che nn riesco a trovare l'eventuale errore dove posso aver sbagliato.....se qualcuno di voi può aiutarmi per favore...o se ha una idea migliore mi risponda...vi ringrazio!:)

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

void scambia (char*, char*);
void stampa(char [], int );

int main()
{
int i,j,k,conta=0;
int len;

char parola[]={"frt"};
len=strlen(parola);


for ( i=0; i<len ; i++ )
{
for ( j=0; j<len ; j++)
{
for ( k=j+1; k<len ; k++)
{ scambia(&parola[j],&parola[k]);
stampa(parola,len);
conta++;
}
}
}

printf("\n\n");
printf("Le permutazioni possibili sono: %d\n\n",conta);
system("pause");

}

void scambia (char *a, char*b)
{
char tmp;

tmp=*a;
*a=*b;
*b=tmp;

}



void stampa(char v[], int dimensione)
{ int i;

printf("\n\n");
for (i=0;i<dimensione;i++)
printf("%c",v);

}

5 Risposte

  • Re: DUBBIO PROGRAMMA!

    Ciao...se non sbaglio, in un altro tuo 3d, un paio di giorni fa ti ho postato un codice (che capisco sia barbaro) che effettuta in modo affidabile le permutazioni. Ora, assumiamo che quel codice tu lo riesca ad utilizzare (o che tu ne trovi uno in rete, facendo una banale ricerca ho trovato questo ). Ora la cosa che, secondo me, ti conviene fare è associare al vettore iniziale di caratteri un numero. Per esempio se hai CIAO-> C==1, I==2, A==3, O==4, quindi una volta che hai le permutazioni dei numeri ti sarà facilissimo fare le "permutazioni della parola".
    Scusa se non guardo il tuo codice, ma già quando le ho divute implementare io le permutazioni mi sono rifiutato di capire/sviluppare una strategia per preservare le mie meningi
  • Re: DUBBIO PROGRAMMA!

    Anzi..usando il programma del link, ecco il programma che fa le permutazioni della parola CIAO (e di qualsiasi parola in generale)

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

    #define SIZE 4

    //Input: array of numbers, which will be permuted once
    //Output: True if permutation was performed, false if no more permutations exist

    int lex_permute(int *array, int size);

    int main() {
    int array[SIZE];
    int i;

    char A[SIZE]={'C','I','A','O'};

    for (i = 0; i < SIZE; i++)
    array = i;
    do {
    for (i = 0; i < SIZE; i++)
    printf("%c ", A[array]);
    printf("\n");
    } while (lex_permute(array, SIZE));

    return 0;
    }

    int lex_permute(int *array, int size) {
    int l, r, tmp;
    if (size < 2)
    return 0;
    l = size - 2;
    while (l >= 0 && array[l] > array[l+1])
    --l;

    if (l < 0)
    return 0;
    r = size - 1;
    while (array[r] < array[l])
    --r;
    tmp = array[l];
    array[l] = array[r];
    array[r] = tmp;
    r = size - 1;
    ++l;
    while (l < r) {
    tmp = array[l];
    array[l++] = array[r];
    array[r--] = tmp;
    }
    return 1;
    }

    buon lavoro!!
  • Re: DUBBIO PROGRAMMA!

    Ciao...sisi..t ringrazio del tuo codice dell'altro giorno...non t ho potuto rispondere xkè nn avevo tempo...cmq quel tuo programma lo ritengo utile..anche se troppi puntatori...non mi sono mai piaciuti..anche xkè non ho tanta dimestichezza cn essi:):):)..ti ringrazio anche di qst nuovo codice e di questa idea di soluzione..che vedrò e proverò a mettere in pratica:)...però avevo postato il mio algoritmo che in fase di esecuzione andava in errore...xkè ero convinto fosse giusto..ma tipo..ti faccio un esempio..se metto 3 come numero di elementi dell'array..invece di 6 permutazioni ne fa 9....oppure in altri casi ne fa un numero anche inferiore...e nn riesco a capire dv sia l'errore...xkè mi sembra tutto giusto...l'unica cosa che non le fa in modo ordinato...ma quello poco importa!:)...e quest'errore lo vorrei trovare...anche xkè ho fatto quell'algoritmo in modo piuttosto semplice e comprensibile...dovendolo poi tradurre in linguaggio assembler..e proprio x quello...ho provato a fare un algoritmo abbastanza leggibile e non impossibile da trasformare nel linguaggio assembler!...l'unica cosa è che nn riesco a capire dv sia l'errore...tutto qui...sto impazzendo!:(
  • Re: DUBBIO PROGRAMMA!

    Ciao, sinceramente ho provato a guardare i 3 cicli for incriminati ma non ci capisco molto. Una strategia è quella di studiare le regolarità che ci possono essere nelle permutazioni. Ad esempio 1 2 3
    1) 1 2 3
    2) 1 3 2
    3) 2 1 3
    4) 2 3 1
    5) 3 1 2
    6) 3 2 1

    Da come vedi ogni numero è portato in testa al vettore 2 volte, mentre scambi i restanti 2. Questo è il pezzo fondamentale che ti permetterebbe di costruire una strategia ricorsiva. Infatti 1 2 3 4
    1) 1 2 3 4
    2) 1 2 4 3
    3) 1 3 2 4
    4) 1 3 4 2
    5) 1 4 2 3
    6) 1 4 3 2
    ...
    ...
    come vedi tieni fisso l'1 e poi applichi la strategia di cui sopra. Il brutto di questa strategia è che dipende dal numero di elementi del vettore.
  • Re: DUBBIO PROGRAMMA!

    Provo a fare come mi dici tu...anche se non riesco a trovare l'errore nel mio programma e mi sto scervellando..perchè il procedimento mi sembra abbastanza giusto..ti dirò:)..ti ringrazio x il consiglio:)
Devi accedere o registrarti per scrivere nel forum
5 risposte