Mots cycliques

Énoncé du problème

Nous pouvons considérer un mot cyclique comme un mot écrit dans un cercle. Pour représenter un mot cyclique, nous choisissons une position de départ arbitraire et lisons les caractères dans le sens des aiguilles d'une montre. Ainsi, "image" et "turepic" sont des représentations pour le même mot cyclique.

Vous obtenez une chaîne de caractères [], dont chaque élément est une représentation d'un mot cyclique. Renvoie le nombre de mots cycliques différents qui sont représentés.

Victoires les plus rapides (Big O, où n = nombre de caractères dans une chaîne)

Python

Voici ma solution. Je pense qu'il pourrait encore être O (n ² ), mais je pense que le cas est en moyenne beaucoup mieux que cela.

Fondamentalement, cela fonctionne en normalisant chaque chaîne afin que toute rotation ait la même forme. Par exemple:

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

La normalisation se fait en recherchant le caractère minimum (par code de caractère) et en faisant tourner la chaîne de sorte que le caractère soit dans la dernière position. Si ce caractère apparaît plus d'une fois, les caractères après chaque occurrence sont utilisés. Cela donne à chaque mot cyclique une représentation canonique, qui peut être utilisée comme clé dans une carte.

La normalisation est n ² dans le pire des cas (où chaque caractère de la chaîne est le même, par exemple aaaaaa), mais la plupart du temps, il n'y aura que quelques occurrences et le temps d'exécution sera plus proche n.

Sur mon ordinateur portable (Intel Atom double cœur à 1,66 GHz et 1 Go de RAM), le faire fonctionner /usr/share/dict/words(234937 mots avec une longueur moyenne de 9,5 caractères) prend environ 7,6 secondes.

#!/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")

Python (3) à nouveau

La méthode que j'ai utilisée consistait à calculer un hachage déroulant de chaque mot à partir de chaque caractère de la chaîne; comme il s'agit d'un hachage roulant, il faut O (n) (où n est la longueur du mot) pour calculer tous les n hachages. La chaîne est traitée comme un nombre de base-1114112, ce qui garantit que les hachages sont uniques. (Elle est similaire à la solution Haskell, mais plus efficace car elle ne traverse la chaîne que deux fois.)

Ensuite, pour chaque mot d'entrée, l'algorithme vérifie son hachage le plus bas pour voir s'il est déjà dans l'ensemble de hachages vus (un ensemble Python, donc la recherche est O (1) dans la taille de l'ensemble); s'il l'est, alors le mot ou l'une de ses rotations a déjà été vu. Sinon, il ajoute ce hachage à l'ensemble.

L'argument de ligne de commande doit être le nom d'un fichier qui contient un mot par ligne (comme /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

Je ne suis pas sûr de l'efficacité de cela, probablement plutôt mauvais. L'idée est de créer d'abord toutes les rotations possibles de tous les mots, de compter les valeurs qui représentent uniquement les chaînes et de sélectionner le minimum. De cette façon, nous obtenons un nombre unique à un groupe cyclique.
Nous pouvons regrouper par ce numéro et vérifier le nombre de ces groupes.

Si n est le nombre de mots dans la liste et m est la longueur d'un mot, alors le calcul du «numéro de groupe cyclique» pour tous les mots est le O(n*m)tri O(n log n)et le regroupement 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

Mathematica

Décidé de recommencer, maintenant que je comprends les règles du jeu (je pense).

Un dictionnaire de 10000 mots de "mots" uniques composés au hasard (minuscules uniquement) de longueur 3. De la même manière, d'autres dictionnaires ont été créés, composés de chaînes de longueur 4, 5, 6, 7 et 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];

gprend la version actuelle du dictionnaire pour vérifier. Le mot du haut est joint à des variantes cycliques (le cas échéant). Le mot et ses correspondances sont ajoutés à la liste de sortie outdes mots traités. Les mots de sortie sont supprimés du dictionnaire.

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 parcourt tous les mots du dictionnaire.

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

Exemple 1 : mots réels

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

{{"steak", "teaks"}, {"hand"}, {"pots", "spot"}, {"sword", "words"}}
4

Exemple 2 : Mots artificiels. Dictionnaire de chaînes de longueur 3. Tout d'abord, le calendrier. Puis le nombre de mots du cycle.

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

5402

Timings en fonction de la longueur des mots . 10000 mots dans chaque dictionnaire.

Je ne sais pas particulièrement comment interpréter les résultats en termes de O. En termes simples, le timing double à peu près du dictionnaire à trois caractères au dictionnaire à quatre caractères. Le timing augmente de façon presque négligeable de 4 à 8 caractères.

Cela peut être fait en O (n) en évitant le temps quadratique. L'idée est de construire le cercle complet traversant deux fois la chaîne de base. Nous construisons donc "amazingamazin" comme la chaîne du cercle complet pour vérifier toutes les chaînes cycliques correspondant à "amazing".

Voici la solution 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

Je ne sais pas si c'est très efficace, mais c'est ma première fissure.

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

Je ne suis pas sûr de comprendre le problème, mais cela correspond au moins à l'exemple @dude publié dans les commentaires. veuillez corriger mon analyse sûrement incorrecte.

pour chaque mot W dans les N mots donnés de la liste de chaînes, vous devez parcourir tous les caractères de W dans le pire des cas. je dois supposer que les opérations de hachage sont effectuées en temps constant.

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), $/;