Zählen Sie die Anzahl der zyklischen Wörter in einer Eingabe

9

Zyklische Wörter

Problemstellung

Wir können uns ein zyklisches Wort als ein Wort vorstellen, das in einem Kreis geschrieben ist. Um ein zyklisches Wort darzustellen, wählen wir eine beliebige Startposition und lesen die Zeichen im Uhrzeigersinn. "Bild" und "turepisch" sind also Darstellungen für dasselbe zyklische Wort.

Sie erhalten ein String [] -Wort, von dem jedes Element ein zyklisches Wort darstellt. Gibt die Anzahl der verschiedenen zyklischen Wörter zurück, die dargestellt werden.

Schnellste Gewinne (Big O, wobei n = Anzahl der Zeichen in einer Zeichenfolge)

Eierbeine
quelle
3
Wenn Sie Kritik an Ihrem Code suchen, ist codereview.stackexchange.com der richtige Ort.
Peter Taylor
Cool. Ich werde zur Hervorhebung der Herausforderung bearbeiten und den Kritikteil zur Codeüberprüfung verschieben. Danke Peter.
Eierbeine
1
Was sind die Gewinnkriterien? Kürzester Code (Code Golf) oder sonst etwas? Gibt es Einschränkungen hinsichtlich der Ein- und Ausgabeform? Müssen wir eine Funktion oder ein komplettes Programm schreiben? Muss es in Java sein?
Ugoren
1
@eggonlegs Du hast big-O angegeben - aber in Bezug auf welchen Parameter? Anzahl der Zeichenfolgen im Array? Ist der Stringvergleich dann O (1)? Oder Anzahl der Zeichen in der Zeichenfolge oder Gesamtzahl der Zeichen? Oder sonst noch etwas?
Howard
1
@dude, sicher ist es 4?
Peter Taylor

Antworten:

4

Python

Hier ist meine Lösung. Ich denke, es könnte immer noch O (n 2 ) sein, aber ich denke, der durchschnittliche Fall ist viel besser als das.

Grundsätzlich funktioniert es, indem jede Zeichenfolge so normalisiert wird, dass jede Drehung dieselbe Form hat. Beispielsweise:

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

Die Normalisierung erfolgt durch Suchen nach dem Mindestzeichen (durch Zeichencode) und Drehen der Zeichenfolge, sodass sich das Zeichen an der letzten Position befindet. Wenn dieses Zeichen mehrmals vorkommt, werden die Zeichen nach jedem Vorkommen verwendet. Dies gibt jedem zyklischen Wort eine kanonische Darstellung, die als Schlüssel in einer Karte verwendet werden kann.

Die Normalisierung ist im schlimmsten Fall n 2 (wobei jedes Zeichen in der Zeichenfolge gleich ist, z. B. aaaaaa), aber die meiste Zeit wird es nur wenige Vorkommen geben, und die Laufzeit wird näher sein n.

Auf meinem Laptop (Dual Core Intel Atom bei 1,66 GHz und 1 GB RAM) /usr/share/dict/wordsdauert das Ausführen (234.937 Wörter mit einer durchschnittlichen Länge von 9,5 Zeichen) etwa 7,6 Sekunden.

#!/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")
Gordon Bailey
quelle
3

Wieder Python (3)

Die Methode, die ich verwendet habe, bestand darin, einen rollierenden Hash jedes Wortes zu berechnen, beginnend mit jedem Zeichen in der Zeichenfolge. Da es sich um einen rollierenden Hash handelt, benötigt O (n) (wobei n die Wortlänge ist) Zeit, um alle n Hashes zu berechnen. Die Zeichenfolge wird als Basis-1114112-Nummer behandelt, wodurch sichergestellt wird, dass die Hashes eindeutig sind. (Dies ähnelt der Haskell-Lösung, ist jedoch effizienter, da die Zeichenfolge nur zweimal durchlaufen wird.)

Dann überprüft der Algorithmus für jedes Eingabewort seinen niedrigsten Hash, um festzustellen, ob er bereits in der Menge der gesehenen Hashes enthalten ist (eine Python-Menge, daher ist die Suche in der Größe der Menge O (1)). Wenn dies der Fall ist, wurde das Wort oder eine seiner Rotationen bereits gesehen. Andernfalls wird dieser Hash zum Set hinzugefügt.

Das Befehlszeilenargument sollte der Name einer Datei sein, die ein Wort pro Zeile enthält (wie /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])
Lowjacker
quelle
1

Haskell

Ich bin mir nicht sicher über die Effizienz, höchstwahrscheinlich ziemlich schlecht. Die Idee ist, zuerst alle möglichen Rotationen aller Wörter zu erstellen, die Werte zu zählen, die die Zeichenfolgen eindeutig darstellen, und das Minimum auszuwählen. Auf diese Weise erhalten wir eine Nummer, die für eine zyklische Gruppe eindeutig ist.
Wir können nach dieser Nummer gruppieren und die Anzahl dieser Gruppen überprüfen.

Wenn n die Anzahl der Wörter in der Liste und m die Länge eines Wortes ist, wird die 'zyklische Gruppennummer' für alle Wörter berechnet O(n*m), sortiert O(n log n)und gruppiert 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
Shiona
quelle
1

Mathematica

Beschlossen, wieder von vorne zu beginnen, jetzt, wo ich die Spielregeln verstehe (glaube ich).

Ein 10000-Wörter-Wörterbuch mit eindeutigen zufällig zusammengesetzten "Wörtern" (nur Kleinbuchstaben) der Länge 3. In ähnlicher Weise wurden andere Wörterbücher erstellt, die aus Zeichenfolgen der Länge 4, 5, 6, 7 und 8 bestehen.

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];

gnimmt die aktuelle Version des Wörterbuchs zur Überprüfung. Das oberste Wort wird mit zyklischen Varianten verbunden (falls vorhanden). Das Wort und seine Übereinstimmungen werden an die Ausgabeliste outder verarbeiteten Wörter angehängt . Die Ausgabewörter werden aus dem Wörterbuch entfernt.

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 läuft durch alle Wörter Wörterbuch.

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

Beispiel 1 : tatsächliche Wörter

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

{{"Steak", "Teaks"}, {"Hand"}, {"Töpfe", "Fleck"}, {"Schwert", "Wörter"}}
4


Beispiel 2 : Künstliche Wörter. Wörterbuch der Zeichenketten der Länge 3. Zuerst das Timing. Dann die Anzahl der Zykluswörter.

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

d3

5402


Timings als Funktion der Wortlänge . 10000 Wörter in jedem Wörterbuch.

Timings

Ich weiß nicht besonders, wie ich die Ergebnisse in Bezug auf O interpretieren soll. In einfachen Worten, das Timing verdoppelt sich ungefähr vom Drei-Zeichen-Wörterbuch zum Vier-Zeichen-Wörterbuch. Das Timing erhöht sich fast vernachlässigbar von 4 auf 8 Zeichen.

DavidC
quelle
Können Sie möglicherweise einen Link zu dem von Ihnen verwendeten Wörterbuch veröffentlichen, damit ich es mit Ihrem vergleichen kann?
Eierbeine
Der folgende Link zu dictionary.txt sollte funktionieren: bitshare.com/files/oy62qgro/dictionary.txt.html (Entschuldigung, ungefähr in der Minute, in der Sie auf den Download warten müssen.) Übrigens hat die Datei 3char, 4char ... insgesamt 8 Zeichenwörterbücher mit jeweils 10000 Wörtern. Sie werden sie trennen wollen.
DavidC
Genial. Vielen Dank :)
Eggonlegs
1

Dies kann in O (n) erfolgen, wobei eine quadratische Zeit vermieden wird. Die Idee ist, den Vollkreis zu konstruieren, der die Basiszeichenfolge zweimal durchläuft. Also konstruieren wir "Amazingamazin" als Vollkreis-String, um alle zyklischen Strings zu überprüfen, die "Amazing" entsprechen.

Unten ist die Java-Lösung:

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
Azee
quelle
0

Ich weiß nicht, ob das sehr effizient ist, aber dies ist mein erster Riss.

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;
}
Eierbeine
quelle
0

Perl

Ich bin mir nicht sicher, ob ich das Problem verstehe, aber dies entspricht zumindest dem Beispiel @dude in den Kommentaren. Bitte korrigieren Sie meine sicherlich falsche Analyse.

Für jedes Wort W in den angegebenen N Wörtern der Zeichenfolgenliste müssen Sie im schlimmsten Fall alle Zeichen von W durchlaufen. Ich muss davon ausgehen, dass die Hash-Operationen in konstanter Zeit ausgeführt werden.

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