Programmering problem [C++]

Jag hade en liknande uppgift en gång. Det jag (och alla andra tror jag) gjorde var att sortera ordet, två anagram är lika efter sortering. (mao "bac" och "cba" är "abc" efter sortering, då vet man att de är anagram)

Jag fick en idé!
Ett annat sätt, inte lika briljant som att sortera, men ändå ett väldigt optimerat sätt för datorn är att utnyttja associativiteten och kommutativiteten vid addition och multiplikation.

Förklaring:
strängarna "bac" och "abc" representeras internt av siffror, ANSI c++ kör med ASCII tecken, (int k = static_cast<int>('a') //ta reda på numret)
vi vet att:
b+a+c=a+b+c
samt att:
b*a*c=a*b*c

Algoritm:
1. kontrollera att längden är samma
2. kontrollera att summan av bokstäverna är samma
3. kontrollera att produkten av bokstäverna är samma
Stämmer alla 3 är strängarna anagram

Bevis:
Jag provade att slänga ihop ett bevis för två termer:

x+y=ax+by (1)
x*y=ax*by (2)

a och b är alltså våra falska modifierarkonstanter (?)
(2) => ab=1 => a=1/b (3)
(1) => ax-x+by-y=0 => (a-1)x+(b-1)y=0 (4)

(3) och (4) ger oss:
(1/b-1)x+(b-1)y=0 vilket har lösningen b=1 (5)

(5) och (2) ger oss:
a=1

Alltså kan man inte modifiera talen och få samma produkt och summa.

Kommentar:
Jag har som sagt bara bevisat (försökt i alla fall) att det gäller för två termer, hur gör man sådana här bevis för "n" antal termer? Eller får vi inte tillräckligt med ekvationer för att lösa problemet?

Givetvis är oftast den bästa lösningen i praktiken att sortera. Jag säger inte att man skall göra som jag sa, det skulle inte ens jag göra. Jag filurade bara lite på en teoretisk algoritm som har potentialen att vara snabbare. Men min fråga kvarstår, hur bevisar man det för "n" antal termer?

EDIT:
Sedan kan man ju justera så att 'a' blir 1, 'b' = 2 o.s.v. Det hjälper ju oss en liten bit i alla fall...
'ö'=29
29^x=2^64
log(2^64)/log(29) = x
x=13,17....

Jaja, 13 bokstäver i alla fall

EDIT2:
Oh, ett annat intressant sätt (tämligen obevisat) skulle vara att transformera bokstäverna till y=2^x (där x är bokstavs id i naturlig följd med början på 0)...
vi får då:
a=1
b=2
c=4
d=8
...
ö=268435456

vi kan sedan endast utnyttja kommutativa lagen för addition.

algoritm:
1. spara orden på formen y=2^x
2. kontrollera att längden är samma
3. kontrollera att summan är samma

vi kan då i alla fall på ett 64 bitars system hantera upp till 68719476736 bokstäver... vilket borde vara tillräckligt.

EDIT3:
kod:
Jag försöker mig på lite kod här också...

bool isAnagram(string str1, string str2)
{
    unsigned int trans[58] = {1, 2, 4, 8, 16, mycket siffror, 134217728, 268435456, 0, 0, 0, 0, 0, 0, 1, 2, 4, 8, 16, mycket siffror , 134217728, 268435456}; //A-Z och a-z ascii konverterar hash


    unsigned int summa1 = 0;
    unsigned int summa2 = 0;

    if (str1.length() == str2.length()) {
        for (size_t i = 0; i < str1.length(); ++i) {
            summa1 += trans[static_cast<int>(str1[i])-65];
            summa2 += trans[static_cast<int>(str2[i])-65];
        }
        return summa1==summa2;
    }
    return false;
}

Det är säkert flera fel i koden men den ger ju ett humm om hur jag tänker

Briljant, så enkelt det var när man såg svaret! Tack så mycket!
Just det, hur kunde jag glömma att x måste vara skillt från 0... missade det totalt

En väldigt intressant tanke! En look up table borde ta hand om själva log(x) prestanda problemet. Nu sitter vi bara med en massa flyttal som skall summeras.

bool isAnagram(string str1, string str2)
{
    uint64 summa1 = 0;
    uint64 summa2 = 0;
    if (str1.length() == str2.length()) {
        for (size_t i = 0; i < str1.length(); ++i) {
            summa1 |= 1 << (static_cast<int>(str1[i])-65);
            summa2 |= 1 << (static_cast<int>(str2[i])-65);
        }
        return summa1==summa2;
    }
    return false;
}

Aush, nu kom jag ju på flera kollisions, (8+1+1=4+4+2 o.s.v.). Vi får väl utöka denna tes med en till ekvation:
a1+a2+...+an
och 2^a1+2^a2+...+2^an

Detta är ju ytterst obevisat av mig att det inte inträffar kollisioner.

lite kod:

bool isAnagram(string str1, string str2)
{
    uint64 bas2_summa1 = 0;
    uint64 bas2_summa2 = 0;
    uint64 vanlig_summa1 = 0;
    uint64 vanlig_summa2 = 0;
    
    if (str1.length() == str2.length()) {
        for (size_t i = 0; i < str1.length(); ++i) {
            vanlig_summa1 += str1[i];
            vanlig_summa2 += str2[i];
            bas2_summa1 |= 1 << (static_cast<int>(str1[i])-65);
            bas2_summa2 |= 1 << (static_cast<int>(str2[i])-65);
        }
        return bas2_summa1 == bas2_summa2 && vanlig_summa1 == vanlig_summ2;
    }
    return false;
}

Jag kommer inte på några kollisions längre, men jag vet inte hur jag ska bevisa att det inte blir några :/

En annan tanke är att använda multiplikation och primtal:
a=2
b=3
c=5
d=7
...

bool isAnagram(string str1, string str2)
{
    uint64 primtal[29] = {2, 3, 5, 7, 11, 13 ... };
    uint64 produkt1 = 0;
    uint64 produkt2 = 0;
    
    for (size_t i = 0; i < str1.length(); ++i) {
        produkt1 *= primtal[static_cast<int>(str1[i])-65];
        produkt2 *= primtal[static_cast<int>(str2[i])-65];
    }
    return produkt1 == produkt2;

}

Fördelar:
Vi behöver inte kolla längden (fast det är ju ganska dumt att inte göra det i optimeringssynpunkt)

Nackdelar:
overflow

En ganska dålig idé, men ändå en ganska intressant lösning i ett teoretiskt perspektiv.

"bb" => 1+1 = 2, 2^1+2^1 = 4
"c" => 2 = 2, 2^2 = 4

men längden på "c" är väl inte samma som på "bb" ? hur menar du nu?

Det ni försöker få fram är en perfekt hash-funktion, men som ni upptäckt så är det omöjligt att konstruera en sådan för indata som kan vara obegränsad i storlek. Man skulle ju däremot kunna hasha hela ordlistan för att snabbt kunna hitta strängar som potentiellt är anagram, och sedan jämföra matchande strängar med en noggrannare metod. Om man bygger upp t.ex. ett binärt träd av hash-värdena där löven pekar på en lista med alla ord som har det hashet så kan man ju kolla upp alla strängar som potentiellt är anagram på O(log n) tid. Kanske lite overkill i det här fallet, men en bra nybörjar-uppgift för att lära sig pekare

En metod att verifiera att två strängar faktiskt är anagram skulle kunna vara att använda t.ex. en variant av bucket-sort där man först räknar hur många gånger varje symbol finns i den första strängen, och sedan räknar man ner när man går igenom den andra strängen och kollar att den innehåller lika många av varje symbol. En liten nackdel är att det krävs lite extra minne för symboltabellen. En fördel är att algoritmen är linjär och man kan sluta så fort man hittar en symbol i den andra strängen som inte finns i den första. Det finns inte heller något praktisk maxgräns för storleken på strängarna man jämför.

Jag är inte så vass på algoritmer.. än mindre avancerad matte... Skulle det fungera med en XOR-algoritm?

bool isAnagram(string str1, string str2)
{
    int len = str1.length();
    if (len == str2.length()) {
        uint32 bits = 0; // lagom för a-z..
        for (int i = 0; i<len; ++i) {
            bits ^= 1 << (str1[i] | 32) - 'a';
            bits ^= 1 << (str2[i] | 32) - 'a';
        }
        return bits == 0;
    }
    return false;
}

Tanken är att två strängar str1 och str2 innehåller samma bokstäver, ej nödvändigtvis i samma ordning. Om detta är sant är strängarna varandras palindromer – med andra ord, varje bokstav i str1 har sin dublett någonstans i str2. Detta innebär att antalet bokstäver av en viss typ alltid är jämnt, så länge som strängarna är varandras palindromer..

Ja det stämmer ju faktiskt.
Min första algoritm såg ut så här, sen fick jag för mig att x var meningslös och tog bort den. Borde fungera bättre:

bool isAnagram(string str1, string str2)
{
    int len = str1.length();
    if (len == str2.length()) {
        uint32 bits = 0; // lagom för a-z..
        int x = 0;
        for (int i = 0; i<len; ++i) {
            x += str1[i] - str2[i];
            bits ^= 1 << (str1[i] | 32) - 'a';
            bits ^= 1 << (str2[i] | 32) - 'a';
        }
        return x == 0 && bits == 0;
    }
    return false;
}

edit: nej det gör det naturligtvis inte.. :\

Hmm...
Menar du något åt det här hållet?

bool isAnagram(string str1, string str2)
{
    const int ascii_offset = 65;
    //Skapa tabellerl som håller reda på antalet tecken av varje sort i vardera sträng
    const int antal_bokstaver = 26;
    uint64 tabellen1[antal_bokstaver];
    uint64 tabellen2[antal_bokstaver];

    //Nolla tabellen
    for (int i = 0; i < antal_bokstaver; ++i) {
        tabellen1[i] = 0;
        tabellen2[i] = 0;
    }

    //Räkna antalet tecken av varje sort
    if (str1.length() == str2.length()) {
        for (size_t i = 0; i < str1.length(); ++i) {
            ++tabellen1[static_cast<int>(str1[i])-ascii_offset];
            ++tabellen2[static_cast<int>(str2[i])-ascii_offset];
        }
        return memcmp(tabellen1, tabellen2, antal_bokstaver) == 0; //Är de lika?
    }
    return false; //inte samma längd
}

Tjau, den har ju faktiskt ingen praktisk övre gräns. Om man nu vill räkna ut vilken av alla dessa algoritmerna presterar/skalar bäst, hur gör man då?

EDIT: kortade ner citatet.

...

Nja, det går att göra det lite smartare. Här är lite pseudo-kod:

isAnagram(string str1, string str2):
    SymbolTable symbols;

    for each symbol in str1:
        symbols[symbol].increase();

    for each symbol in str2:
        if st[symbol] == 0 then return false;
        symbols[symbol].decrease();

    for each symbol in symbols:
        if st[symbol] != 0 then return false;

    return true;

Dvs. man behöver endast en tabell, och man kan sluta så fort man ser att den andra strängen skiljer sig från den första.

Dagens intressanta/underliga C++-detalj är förrresten att man kan skriva

uint64 tabellen1[antal_bokstaver] = {0};

för att initialisera en array med nollor. I C++ så kan man nämligen ange en initialiseringslista som är kortare än arrayen, och resten av arrayen fylls helt enkelt med nollor (se här).

uint64 tabellen1[antal_bokstaver] = {0};

Just det! Jo, detta vet jag om, den stora frågan är väl varför jag inte gjorde så... förmycket tentaplugg kanske... hehe... men hur räknar du fram hur algoritmer skalar? T.ex. O(log n) ?

EDIT:
Kan ju bidra med min dagens intressant/underliga C detalj, nämligen fält.

struct {
    falt1 : 3;
          : 2;
    falt2 : 1;
          : 0;
    falt3 : 1;
};

falt1 är 3 bitar stor, sedan är det 2 bitars glapp till falt2. falt2 är i sin tur 1 bit stor. Vid "namnlöst med 0" så går den till nästa int. falt3 befinner sig alltså på en intilliggande integer och är 1 bit stor.

Tja, det är ju komplexitetsteori, vilket brukar tas upp i de flesta kurser om algoritmer på högskolenivå. Men t.ex. min algoritm går ju igenom varje sträng en gång, så om strängarna har storlek n så går det som mest åt 2*k1*n + k2 operationer för att utföra algoritmen, där k1 och k2 är konstanter. k1 står för antalet operationer som krävs för varje symbol, och k2 är antalet operationer som krävs för att initalisera och kontrollera symboltabellen. Man säger därför att algoritmen har komplexiteten O(n), dvs. man räknar inte med konstanter. Man kan också säga att algoritmen har linjär komplexitet eftersom tiden att utföra den ökar linjärt med storleken på indatan.

På samma sätt så går det enkelt att visa att din algoritm har komplexitet O(n), så från komplexitetsteorins synvinkel så är algoritmerna lika bra. I praktiken så beror det på indatan vilken av dem som är bäst. Min algoritm har fördelen att den kan sluta tidigare om strängarna är olika, men har å andra sidan lite overhead p.g.a. symboltabellen. Din algoritm lämpar sig med andra ord för små strängar, medan min är bättre på att hantera stora strängar.