Sådan løses et streng permutationsproblem ved hjælp af JavaScript

Ansvarsfraskrivelse: Dette er ikke løsningen på dette problem. Der er en million måder at løse det på.

Hurtig

Når du får en streng, skal du returnere en sorteret matrix med alle unikke permutationer for den streng. Permutationerne vil alle være af samme længde som den givne streng og behøver ikke at være faktiske ord.

Da jeg først læste dette, var jeg lidt forvirret. Hvis du er for det, skal du ikke bekymre dig! Det er hvad dette er til.

Lad os først dissekere denne prompt lidt. Hvis du husker fra matematik, er en permutation handlingen med at ændre arrangementet af sæt sæt, hvor ordren betyder noget.

eksempler

Hvis vi tager strengen 'kat', skal funktionen vende tilbage

['handle', 'atc', 'cat', 'cta', 'tac', 'tca']

** I resten af ​​dette indlæg bruger vi 'kat' som vores prøve.

Hvis strengen har et gentagende bogstav, som 'pop', skal funktionen vende tilbage

['opp', 'pop', 'ppo']

Nærme sig

Så hvordan løser vi dette? Du kan godt tænke på hvert bogstav som at have n mulige positioner i strengen, hvor n er længden af ​​den givne streng. Når vi begynder at itereere gennem strengen, kan vi indsætte hvert bogstav i en matrix på hver tilgængelige position. For eksempel, hvis vi starter med en tom matrix og indsætter 'c' i det (det første bogstav), er der kun et muligt sted, som bogstavet kan gå (indeks 0).

[ 'C']

Når du tilføjer det andet bogstav ('a'), kan det gå to steder: arr [0] eller arr [1]

'a' kan gå på hver side af 'c'
['_c'] eller ['c_']
indsætte 'a'
['ac', 'ca']

Og så videre

't' kan gå på 3 steder i hvert element i matrixen
['_ac', 'a_c', 'ac_', '_ca', 'c_a', 'ca_']
indsætte 't'
['tac', 'atc', 'act', 'tca', 'cta', 'cat']

Løsning uden rekursion

Her er en løsning uden at bruge rekursion:

function stringPermutations (str) {
    lad bogstaver = str.split ('')
      , resultater = [[letters.shift ()]]
    mens (bogstaver. længde) {
        const currLetter = letters.shift ()
        let tmpResults = []
        results.forEach (result => {
            lad rIdx = 0
            mens (rIdx <= result.length) {
                const tmp = [... resultat]
                tmp.splice (rIdx, 0, currLetter)
                tmpResults.push (tmp)
                rIdx ++
            }
        })
        resultater = tmpResultater
    }
    returnere resultater
      .map (letterArray => letterArray.join (''))
      .filter ((el, idx, self) => (self.indexOf (el) === idx))
      .sortere()
}

Lad os gennemgå denne linje for linje. Med det samme har vi brug for 2 variabler for at indeholde nogle data. Bogstaverne indeholder en matrix, hvor hvert element er et tegn i strengen.

lad bogstaver = str.split ('') // letters = ['c', 'a', 't']

Resultatvariablen vil indeholde og matrix af arrays. På første kørsel inkluderer resultaterne bare det første bogstav i strengen (i vores tilfælde 'c' fra 'kat').

results = [[letters.shift ()]] // results = [['c']]
// og bogstaver = ['a', 't']

Nu skal vi gentage resten af ​​bogstavsopstillingen. Først tager vi det næste brev fra bogstavsopstillingen.

const currLetter = letters.shift () // currLetter = 'a'
// bogstaver = ['t']

Derefter skal vi itereere gennem resultatsystemet og hvert indre array for at indsætte det aktuelle bogstav før og efter det aktuelle bogstav og skabe en indlejret dobbelt loop. For at indsætte det aktuelle bogstav i positionerne skal vi først oprette en kopi af den aktuelle resultatserie, derefter tilføjer vi brevet til den position, som vi ønsker, ved hjælp af array-metodespalten.

mens (rIdx <= result.length) {
    // opretter en kopi af resultatsystemet
    const tmp = [... resultat] // tmp = ['c']
    // Indsætter det aktuelle bogstav på position rIdx
    tmp.splice (rIdx, 0, currLetter) // tmp = ['a', 'c']
    tmpResults.push (tmp)
    rIdx ++
}

Når hvert bogstav er placeret i enhver mulig position, er vi nødt til at gøre et par ting til det resulterende array. Først må vi iterere igennem det og gå sammen med hver indre array, så vi sidder tilbage med en række strenge.

// resultater før kort
[
  ['t', 'a', 'c'],
  ['a', 't', 'c'],
  ['a', 'c', 't'],
  ['t', 'c', 'a'],
  ['c', 't', 'a'],
  ['c', 'a', 't']
]
// resultater efter kort
['tac', 'atc', 'act', 'tca', 'cta', 'cat']

Nu hvor vi har alle permutationer, skal vi sørge for, at de alle er unikke. Derfor bruger vi metoden Array.prototype.filter. I dette tilfælde var der ingen duplikater, så resultaterne forbliver de samme.

Til sidst skal vi sikre os, at resultatsystemet sorteres.

// Endelig resultat
['handle', 'atc', 'cat', 'cta', 'tac', 'tca']

Tid og rumkompleksitet

Den generelle tidskompleksitet for denne løsning er O (n!), Hvor n er antallet af unikke tegn i strengen.