Cykliczne słowa

Opis problemu

Możemy myśleć o cyklicznym słowie jak o słowie wpisanym w okrąg. Aby przedstawić słowo cykliczne, wybieramy dowolną pozycję początkową i odczytujemy znaki w kolejności zgodnej z ruchem wskazówek zegara. Tak więc „obraz” i „turepik” są reprezentacjami tego samego cyklicznego słowa.

Otrzymujesz słowo String [], którego każdy element jest wyrazem słowa cyklicznego. Zwraca liczbę różnych reprezentowanych słów cyklicznych.

Najszybsze wygrane (Big O, gdzie n = liczba znaków w ciągu)

Pyton

Oto moje rozwiązanie. Myślę, że nadal może to być O (n ² ), ale myślę, że średni przypadek jest znacznie lepszy.

Zasadniczo działa to poprzez normalizację każdego łańcucha, aby każdy obrót miał tę samą formę. Na przykład:

'amazing' -> 'mazinga'
'mazinga' -> 'mazinga'
'azingam' -> 'mazinga'
'zingama' -> 'mazinga'
'ingamaz' -> 'mazinga'
'ngamazi' -> 'mazinga'
'gamazin' -> 'mazinga'

Normalizacja polega na szukaniu minimalnego znaku (według kodu char) i obracaniu łańcucha, aby znak znalazł się na ostatniej pozycji. Jeśli ten znak występuje więcej niż jeden raz, wówczas używane są znaki po każdym wystąpieniu. Daje to każdemu cyklicznemu słowu reprezentację kanoniczną, którą można wykorzystać jako klucz na mapie.

Normalizacja wynosi n ² w najgorszym przypadku (gdzie np. Każdy znak w ciągu jest taki sam aaaaaa), ale przez większość czasu będzie tylko kilka wystąpień, a czas działania będzie bliższy n.

Na moim laptopie (dwurdzeniowy Intel Atom @ 1,66 GHz i 1 GB pamięci RAM) uruchomienie tego /usr/share/dict/words(234 937 słów o średniej długości 9,5 znaków) zajmuje około 7,6 sekundy.

#!/usr/bin/python

import sys

def normalize(string):
   # the minimum character in the string
   c = min(string) # O(n) operation
   indices = [] # here we will store all the indices where c occurs
   i = -1       # initialize the search index
   while True: # finding all indexes where c occurs is again O(n)
      i = string.find(c, i+1)
      if i == -1:
         break
      else:
         indices.append(i)
   if len(indices) == 1: # if it only occurs once, then we're done
      i = indices[0]
      return string[i:] + string[:i]
   else:
      i = map(lambda x:(x,x), indices)
      for _ in range(len(string)):                       # go over the whole string O(n)
         i = map(lambda x:((x[0]+1)%len(string), x[1]), i)  # increment the indexes that walk along  O(m)
         c = min(map(lambda x: string[x[0]], i))    # get min character from current indexes         O(m)
         i = filter(lambda x: string[x[0]] == c, i) # keep only the indexes that have that character O(m)
         # if there's only one index left after filtering, we're done
         if len(i) == 1:
            break
      # either there are multiple identical runs, or
      # we found the unique best run, in either case, we start the string from that
      # index
      i = i[0][0]
      return string[i:] + string[:i]

def main(filename):
   cyclic_words = set()
   with open(filename) as words:
      for word in words.readlines():
         cyclic_words.add(normalize(word[:-1])) # normalize without the trailing newline
   print len(cyclic_words)

if __name__ == '__main__':
   if len(sys.argv) > 1:
      main(sys.argv[1])
   else:
      main("/dev/stdin")

Znowu Python (3)

Metodą, którą zastosowałem, było obliczenie wartości skrótu każdego słowa, zaczynając od każdego znaku w ciągu; ponieważ jest to ciągły skrót, obliczenie wszystkich n skrótów zajmuje O (n) (gdzie n jest długością słowa). Łańcuch jest traktowany jako liczba podstawowa 1114112, co zapewnia unikalność skrótów. (Jest to podobne do rozwiązania Haskell, ale bardziej wydajne, ponieważ przechodzi przez ciąg tylko dwa razy).

Następnie dla każdego słowa wejściowego algorytm sprawdza swój najniższy skrót, aby sprawdzić, czy jest już w zestawie widzialnych skrótów (zestaw Pythona, a zatem wyszukiwanie to O (1) w rozmiarze zestawu); jeśli tak, to słowo lub jedna z jego rotacji była już widoczna. W przeciwnym razie dodaje ten skrót do zestawu.

Argumentem wiersza polecenia powinna być nazwa pliku zawierającego jedno słowo w wierszu (np /usr/share/dict/words.).

import sys

def rollinghashes(string):
    base = 1114112
    curhash = 0
    for c in string:
        curhash = curhash * base + ord(c)
    yield curhash
    top = base ** len(string)
    for i in range(len(string) - 1):
        curhash = curhash * base % top + ord(string[i])
        yield curhash

def cycles(words, keepuniques=False):
    hashes = set()
    uniques = set()
    n = 0
    for word in words:
        h = min(rollinghashes(word))
        if h in hashes:
            continue
        else:
            n += 1
            if keepuniques:
                uniques.add(word)
            hashes.add(h)
    return n, uniques

if __name__ == "__main__":
    with open(sys.argv[1]) as words_file:
        print(cycles(line.strip() for line in words_file)[0])

Haskell

Nie jestem pewien co do skuteczności, najprawdopodobniej raczej źle. Chodzi o to, aby najpierw utworzyć wszystkie możliwe rotacje wszystkich słów, policzyć wartości, które jednoznacznie reprezentują ciągi, i wybrać minimum. W ten sposób otrzymujemy liczbę unikalną dla grupy cyklicznej.
Możemy pogrupować według tego numeru i sprawdzić liczbę tych grup.

Jeśli n jest liczbą słów na liście, a m jest długością słowa, wówczas obliczanie „cyklicznego numeru grupy” dla wszystkich słów to O(n*m)sortowanie O(n log n)i grupowanie O(n).

import Data.List
import Data.Char
import Data.Ord
import Data.Function

groupUnsortedOn f = groupBy ((==) `on` f) . sortBy(compare `on` f)
allCycles w = init $ zipWith (++) (tails w)(inits w)
wordval = foldl (\a b -> a*256 + (fromIntegral $ ord b)) 0
uniqcycle = minimumBy (comparing wordval) . allCycles
cyclicGroupCount = length . groupUnsortedOn uniqcycle

Matematyka

Postanowiłem zacząć od nowa, teraz, gdy rozumiem zasady gry (tak myślę).

Słownik o długości 10000 unikalnych, losowo skomponowanych „słów” (tylko małe litery) o długości 3. W podobny sposób utworzono inne słowniki składające się z ciągów o długości 4, 5, 6, 7 i 8.

ClearAll[dictionary]      
dictionary[chars_,nWords_]:=DeleteDuplicates[Table[FromCharacterCode@RandomInteger[{97,122},
chars],{nWords}]];
n=16000;
d3=Take[dictionary[3,n],10^4];
d4=Take[dictionary[4,n],10^4];
d5=Take[dictionary[5,n],10^4];
d6=Take[dictionary[6,n],10^4];
d7=Take[dictionary[7,n],10^4];
d8=Take[dictionary[8,n],10^4];

gpobiera bieżącą wersję słownika do sprawdzenia. Górne słowo jest połączone z cyklicznymi wariantami (jeśli istnieją). Słowo i jego dopasowania są dołączane do listy outwyników przetworzonych słów. Słowa wyjściowe są usuwane ze słownika.

g[{wds_,out_}] := 
   If[wds=={},{wds,out},
   Module[{s=wds[[1]],t,c},
   t=Table[StringRotateLeft[s, k], {k, StringLength[s]}];
   c=Intersection[wds,t];
   {Complement[wds,t],Append[out,c]}]]

f przegląda słownik wszystkich słów.

f[dict_]:=FixedPoint[g,{dict,{}}][[2]]

Przykład 1 : rzeczywiste słowa

r = f[{"teaks", "words", "spot", "pots", "sword", "steak", "hand"}]
Length[r]

{{„stek”, „teaks”}, {„ręka”}, {„garnki”, „spot”}, {„miecz”, „słowa”}}
4

Przykład 2 : Sztuczne słowa. Słownik ciągów długości 3. Po pierwsze, czas. Następnie liczba słów cyklicznych.

f[d3]//AbsoluteTiming
Length[%[[2]]]

5402

Czasy jako funkcja długości słowa . 10000 słów w każdym słowniku.

Nie wiem szczególnie, jak interpretować wyniki w kategoriach O. Mówiąc prosto, czas z grubsza podwaja się ze słownika z trzema znakami do słownika z czterema znakami. Czas rośnie prawie pomijalnie z 4 do 8 znaków.

Można to zrobić w O (n), unikając kwadratowego czasu. Chodzi o to, aby dwa razy wykonać pełny okrąg przemierzający łańcuch podstawowy. Konstruujemy więc „Amazingamazin” jako ciąg z pełnym kołem, aby sprawdzić wszystkie ciągi cykliczne odpowiadające „niesamowitemu”.

Poniżej znajduje się rozwiązanie Java:

public static void main(String[] args){
    //args[0] is the base string and following strings are assumed to be
    //cyclic strings to check 
    int arrLen = args.length;
    int cyclicWordCount = 0;
    if(arrLen<1){
        System.out.println("Invalid usage. Supply argument strings...");
        return;
    }else if(arrLen==1){
        System.out.println("Cyclic word count=0");
        return;         
    }//if

    String baseString = args[0];
    StringBuilder sb = new StringBuilder();
    // Traverse base string twice appending characters
    // Eg: construct 'amazingamazin' from 'amazing'
    for(int i=0;i<2*baseString.length()-1;i++)
        sb.append(args[0].charAt(i%baseString.length()));

    // All cyclic strings are now in the 'full circle' string
    String fullCircle = sb.toString();
    System.out.println("Constructed string= "+fullCircle);

    for(int i=1;i<arrLen;i++)
    //Do a length check in addition to contains
     if(baseString.length()==args[i].length()&&fullCircle.contains(args[i])){
        System.out.println("Found cyclic word: "+args[i]);
        cyclicWordCount++;
    }

    System.out.println("Cyclic word count= "+cyclicWordCount);
}//main

Nie wiem, czy to jest bardzo wydajne, ale to mój pierwszy crack.

private static int countCyclicWords(String[] input) {
    HashSet<String> hashSet = new HashSet<String>();
    String permutation;
    int count = 0;

    for (String s : input) {
        if (hashSet.contains(s)) {
            continue;
        } else {
            count++;
            for (int i = 0; i < s.length(); i++) {
                permutation = s.substring(1) + s.substring(0, 1);
                s = permutation;
                hashSet.add(s);
            }
        }
    }

    return count;
}

Perl

nie jestem pewien, czy rozumiem problem, ale odpowiada to przynajmniej przykładowi @dude opublikowanemu w komentarzach. popraw moją z pewnością niepoprawną analizę.

dla każdego słowa W w podanych N słowach z listy ciągów, musisz przejść przez wszystkie znaki W w najgorszym przypadku. muszę założyć, że operacje skrótu są wykonywane w stałym czasie.

use strict;
use warnings;

my @words = ( "teaks", "words", "spot", "pots", "sword", "steak", "hand" );

sub count
{
  my %h = ();

  foreach my $w (@_)
  {
    my $n = length($w);

    # concatenate the word with itself. then all substrings the
    # same length as word are rotations of word.
    my $s = $w . $w;

    # examine each rotation of word. add word to the hash if
    # no rotation already exists in the hash
    $h{$w} = undef unless
      grep { exists $h{substr $s, $_, $n} } 0 .. $n - 1;
  }

  return keys %h;
}

print scalar count(@words), $/;