Avatar billede thomas_nj Nybegynder
15. april 2006 - 22:45 Der er 9 kommentarer og
1 løsning

Algoritme til kombinationer af string

Hej

  Jeg forsøger lidt på at lave en algoritme, der kan lave alle kombinationer af en string ud fra følgende regler:
  * Hvis strengen er x antal tegn lang skal kombinationerne også være x lang
  * Hvert tegn skal og må kun bruges en gang.

  Dvs strengen "hej" skal give:
  hej
  hje
  jeh
  jhe
  ehj
  ejh

  Jeg har tidligere leget med en algoritme, der skulle gøre næsten det samme. Her var det bare alle kombinationer uanset længden og tegnene måtte bruges lige så tosset de ville. Problemet er at hvis jeg genbruger denne skal jeg til at sortere alle de muligheder fra, der ikke lever op til kravene.



  Selv har jeg overvejet en form for bytte algoritme. Måden den fungerer på er at den starter ved de 2 bagerste tegn, og når den ikke kan lave flere kombinationer låner den et tegn fra næste plads.

  Eks

  ahej
  ahje
  ajhe <- Da den ikke kan bytte tilbage tager den h't ned i stedet for j'et
  ajeh
  aejh <- Nu er det bare e't der kommer ud så jeg kan kombinere med h og j

  Jeg kan regne ud hvor mange kombinationer jeg kan lave alt efter hvor mange pladser jeg tager i brug.
  2 pladser = 2*1 = 2 kombinationer
  3 pladser = 3*2*1 = 6 kombinationer

  På denne måde ved jeg hvornår jeg skal en plads længere ud at hente et nyt tegn.

  Først vil jeg lige høre om det er muligt at følge, hvad jeg mener. Fordi jeg synes det er halvsvært at forklare.

  Ellers er mit spørgsmål om der findes en smartere metode. For jeg synes at den måde her virker som noget, der meget hurtigt bliver noget rod.
Avatar billede erikjacobsen Ekspert
15. april 2006 - 23:02 #1
Lige for at være sikker: hvad skal der komme ud af OMO ?
Avatar billede arne_v Ekspert
15. april 2006 - 23:06 #2
du laver en rekursiv algoritme med et used array af samme dimension som tegn arrayet

jeg har postet java kode til det et par gange
Avatar billede thomas_nj Nybegynder
15. april 2006 - 23:13 #3
Ser ud til der ligger en her http://www.eksperten.dk/spm/700821

  Kigger lige på det.
Avatar billede arne_v Ekspert
15. april 2006 - 23:19 #4
jeg tror også at jeg har den i C# og VB.NET hvis du skulle have interesse

men princippet er jo såre simpelt
Avatar billede thomas_nj Nybegynder
15. april 2006 - 23:22 #5
Har leget lidt med java før, så det er nok der jeg har størst chance for at gennemskue, hvad der foregår.
Avatar billede jakoba Nybegynder
16. april 2006 - 11:48 #6
void permuter( int plads, char[] bogstaver ) {
    if ( plads < bogstaver.length() ) {
        char temp = bogstaver[plads];
        for (int i=plads; i<bogstaver.length; i++ ) { // med alle bogstaver skiftevis forrest
            bogstaver[plads] = bogstaver[i];
            bogstaver[i] = temp;
            permuter( plads+1, bogstaver );          // permuter resten af bogstaverne
            bogstaver[i] = bogstaver[plads];
        }
        bogstaver[plads] = temp;
    } else {
        // vi er færdige, skriv denne
        System.out.println( new String( bogstaver ) );
    }
}

funktionen kaldes med:
permuter( 0, "hej".toCharArray() );  // hvor "hej" er den streng der skal permuteres.
Avatar billede thomas_nj Nybegynder
16. april 2006 - 18:39 #7
Ok jeg har skrevet arne_v's kode om til C++. Det endte med:

void writePerm(const string& str, const string& prefix, const int& iX, bool used[])
{
  if(iX<str.size())
    {
      for(int i=0; i<str.size(); i++)
    {
      if(!used[i])
        {
          used[i]=true;
          writePerm(str, prefix+str[i], iX+1, used);
          used[i]=false;
        }
    }
    }
  else
    {
      cout<<prefix<<endl;
    }

}

  Hvis vi antager at programmet kaldes med strengen "hej"

  Jeg kan fint følge flowet i programmet til hvor den skriver hej (det første ord), men så begynder det at blive kludret.

  Den hopper vel tilbage til hvor i=2, hvilket gør at for-loopet slutter og den hopper igen tilbage til i=1.
  used[1] sættes til false og i øges til 2. prefix bliver så hj og da used[1] er første false tilføjes e'et og den udskriver hje

  Jeg er lidt i tvivl her. Ovenstående virker meget rodet.
Avatar billede arne_v Ekspert
16. april 2006 - 21:33 #8
første kald writePerm udfylder det første tegn med alle mulige tegn

for hver af disse muligheder kaldes writePerm for at udfylde det andet  tegn

disse kald udfylder så det andet tegn med alle mulige tegn og kalder writePerm
for at udfylde det tredie tegn

prøv og tegn et træ med alle muligheder inkl. genbrug af bogstaver

hvert niveau i træet er en niveau af rekursion

used bruges udelukkende til at forhindre genbrug
Avatar billede thomas_nj Nybegynder
17. april 2006 - 22:34 #9
Tror jeg har fat i hvordan det hele fungerer nu.

  arne_v >> Mange tak for hjælpen, den havde jeg ikke fået fundet på selv. Gider du ikke smide et svar?
Avatar billede arne_v Ekspert
17. april 2006 - 23:04 #10
gerne

Jakobs er ioevrigt smartere, men jeg synes at used arrayet er nemmere at forstaa
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester