So überprüfen Sie, ob zwei Listen in Python zirkulär identisch sind

Zum Beispiel habe ich Listen:

a[0] = [1, 1, 1, 0, 0]
a[1] = [1, 1, 0, 0, 1]
a[2] = [0, 1, 1, 1, 0]
# and so on

Sie scheinen unterschiedlich zu sein, aber wenn angenommen wird, dass Anfang und Ende miteinander verbunden sind, sind sie kreisförmig identisch.

Das Problem ist, dass jede Liste, die ich habe, eine Länge von 55 hat und nur drei Einsen und 52 Nullen enthält. Ohne kreisförmige Bedingung gibt es 26.235 (55 wählen 3) Listen. Wenn jedoch die Bedingung "Rundschreiben" besteht, gibt es eine große Anzahl von zirkular identischen Listen

Derzeit überprüfe ich die zirkuläre Identität wie folgt:

def is_dup(a, b):
    for i in range(len(a)):
        if a == list(numpy.roll(b, i)): # shift b circularly by i
            return True
    return False

Diese Funktion erfordert im schlimmsten Fall 55 zyklische Schaltvorgänge. Und es gibt 26.235 Listen, die miteinander verglichen werden müssen. Kurz gesagt, ich benötige 55 * 26.235 * (26.235 - 1) / 2 = 18.926.847.225 Berechnungen. Es sind ungefähr 20 Giga!

Gibt es eine gute Möglichkeit, dies mit weniger Berechnungen zu tun? Oder irgendwelche Datentypen, die Rundschreiben unterstützen ?

Zunächst einmal kann dies in O(n)Bezug auf die Länge der Liste erfolgen. Sie können feststellen, dass Ihre neue Liste definitiv alle möglichen zyklischen Listen enthält , wenn Sie Ihre Liste zweimal duplizieren ( [1, 2, 3]) [1, 2, 3, 1, 2, 3].

Sie müssen also nur überprüfen, ob sich die Liste, die Sie suchen, innerhalb Ihrer Startliste befindet. In Python können Sie dies auf folgende Weise erreichen (vorausgesetzt, die Längen sind gleich).

list1 = [1, 1, 1, 0, 0]
list2 = [1, 1, 0, 0, 1]
print ' '.join(map(str, list2)) in ' '.join(map(str, list1 * 2))

Einige Erklärungen zu meinem Oneliner: list * 2Kombiniert eine Liste mit sich selbst, map(str, [1, 2])konvertiert alle Zahlen in Zeichenfolgen und ' '.join()konvertiert das Array ['1', '2', '111']in eine Zeichenfolge '1 2 111'.

Wie von einigen Personen in den Kommentaren erwähnt, kann Oneliner möglicherweise einige falsch positive Ergebnisse liefern, um alle möglichen Randfälle abzudecken:

def isCircular(arr1, arr2):
    if len(arr1) != len(arr2):
        return False

    str1 = ' '.join(map(str, arr1))
    str2 = ' '.join(map(str, arr2))
    if len(str1) != len(str2):
        return False

    return str1 in str2 + ' ' + str2

PS1 Wenn es um Zeitkomplexität geht, ist zu beachten, dass O(n)dies erreicht wird, wenn Teilzeichenfolgen rechtzeitig gefunden werden O(n)können. Dies ist nicht immer der Fall und hängt von der Implementierung in Ihrer Sprache ab ( obwohl dies möglicherweise beispielsweise in linearer Zeit KMP erfolgen kann).

PS2 für Leute, die Angst vor einer Saitenoperation haben und aufgrund dieser Tatsache denken, dass die Antwort nicht gut ist. Was wichtig ist, ist Komplexität und Geschwindigkeit. Dieser Algorithmus läuft möglicherweise O(n)zeitlich und O(n)räumlich, was ihn viel besser macht als alles in der O(n^2)Domäne. Um dies selbst zu sehen, können Sie einen kleinen Benchmark ausführen (beim Erstellen einer zufälligen Liste wird das erste Element eingefügt und an das Ende angehängt, wodurch eine zyklische Liste erstellt wird. Sie können Ihre eigenen Manipulationen vornehmen).

from random import random
bigList = [int(1000 * random()) for i in xrange(10**6)]
bigList2 = bigList[:]
bigList2.append(bigList2.pop(0))

# then test how much time will it take to come up with an answer
from datetime import datetime
startTime = datetime.now()
print isCircular(bigList, bigList2)
print datetime.now() - startTime    # please fill free to use timeit, but it will give similar results

0,3 Sekunden auf meiner Maschine. Nicht wirklich lange. Versuchen Sie nun, dies mit O(n^2)Lösungen zu vergleichen . Während des Vergleichs können Sie von den USA nach Australien reisen (höchstwahrscheinlich mit einem Kreuzfahrtschiff).

In Python nicht gut genug informiert, um dies in der von Ihnen gewünschten Sprache zu beantworten, aber in C / C ++ würde ich angesichts der Parameter Ihrer Frage die Nullen und Einsen in Bits konvertieren und sie auf die niedrigstwertigen Bits eines uint64_t übertragen. Auf diese Weise können Sie alle 55 Bits auf einen Schlag vergleichen - 1 Uhr.

Unglaublich schnell, und das Ganze passt in On-Chip-Caches (209.880 Bytes). Die Hardwareunterstützung zum gleichzeitigen Verschieben aller 55 Listenmitglieder nach rechts ist nur in den Registern einer CPU verfügbar. Gleiches gilt für den gleichzeitigen Vergleich aller 55 Mitglieder. Dies ermöglicht eine 1-zu-1-Zuordnung des Problems zu einer Softwarelösung. (und unter Verwendung der SIMD / SSE 256-Bit-Register bis zu 256 Mitglieder, falls erforderlich) Als Ergebnis ist der Code für den Leser sofort offensichtlich.

Möglicherweise können Sie dies in Python implementieren. Ich weiß es einfach nicht gut genug, um zu wissen, ob dies möglich ist oder wie hoch die Leistung sein könnte.

Nach dem Schlafen wurden einige Dinge offensichtlich und alles zum Besseren.

1.) Es ist so einfach, die zirkulär verknüpfte Liste mit Bits zu drehen, dass Dalis sehr cleverer Trick nicht notwendig ist. Innerhalb eines 64-Bit-Registers wird die Standard-Bitverschiebung die Rotation sehr einfach durchführen und in dem Versuch, dies alles Python-freundlicher zu machen, indem Arithmetik anstelle von Bit-Ops verwendet wird.

2.) Die Bitverschiebung kann leicht durch Teilen durch 2 erreicht werden.

3.) Das Überprüfen des Listenendes auf 0 oder 1 kann mit Modulo 2 problemlos durchgeführt werden.

4.) Das "Verschieben" einer 0 vom Ende zum Ende der Liste kann durch Teilen durch 2 erfolgen. Wenn die Null tatsächlich verschoben würde, würde dies das 55. Bit falsch machen, was es bereits ist, indem absolut nichts getan wird.

5.) Das Verschieben einer 1 vom Ende zum Ende der Liste kann durch Teilen durch 2 und Addieren von 18.014.398.509.481.984 erfolgen. Dies ist der Wert, der durch Markieren des 55. Bits als wahr und aller anderen als falsch erzeugt wird.

6.) Wenn ein Vergleich des Ankers und des zusammengesetzten uint64_t nach einer bestimmten Drehung WAHR ist, brechen Sie und geben Sie WAHR zurück.

Ich würde das gesamte Array von Listen direkt vorab in ein Array von uint64_ts konvertieren, um zu vermeiden, dass die Konvertierung wiederholt durchgeführt werden muss.

Nachdem ich einige Stunden damit verbracht hatte, den Code zu optimieren und die Assemblersprache zu studieren, konnte ich 20% der Laufzeit sparen. Ich sollte hinzufügen, dass der O / S- und MSVC-Compiler gestern auch mittags aktualisiert wurde. Aus welchen Gründen auch immer, die Qualität des vom C-Compiler erstellten Codes hat sich nach dem Update (15.11.2014) dramatisch verbessert. Die Laufzeit beträgt jetzt ~ 70 Uhren, 17 Nanosekunden , um einen Ankerring mit allen 55 Windungen eines Testrings zusammenzustellen und zu vergleichen, und NxN aller Ringe gegen alle anderen ist in 12,5 Sekunden erledigt .

Dieser Code ist so eng, dass bis auf 4 Register 99% der Zeit nichts tun. Die Assemblersprache entspricht fast Zeile für Zeile dem C-Code. Sehr leicht zu lesen und zu verstehen. Ein großartiges Montageprojekt, wenn sich jemand das selbst beibringt.

Hardware ist Hazwell i7, MSVC 64-Bit, vollständige Optimierungen.

#include "stdafx.h"
#include "stdafx.h"
#include <string>
#include <memory>
#include <stdio.h>
#include <time.h>

const uint8_t  LIST_LENGTH = 55;    // uint_8 supports full witdth of SIMD and AVX2
// max left shifts is 32, so must use right shifts to create head_bit
const uint64_t head_bit = (0x8000000000000000 >> (64 - LIST_LENGTH)); 
const uint64_t CPU_FREQ = 3840000000;   // turbo-mode clock freq of my i7 chip

const uint64_t LOOP_KNT = 688275225; // 26235^2 // 1000000000;

// ----------------------------------------------------------------------------
__inline uint8_t is_circular_identical(const uint64_t anchor_ring, uint64_t test_ring)
{
    // By trial and error, try to synch 2 circular lists by holding one constant
    //   and turning the other 0 to LIST_LENGTH positions. Return compare count.

    // Return the number of tries which aligned the circularly identical rings, 
    //  where any non-zero value is treated as a bool TRUE. Return a zero/FALSE,
    //  if all tries failed to find a sequence match. 
    // If anchor_ring and test_ring are equal to start with, return one.

    for (uint8_t i = LIST_LENGTH; i;  i--)
    {
        // This function could be made bool, returning TRUE or FALSE, but
        // as a debugging tool, knowing the try_knt that got a match is nice.
        if (anchor_ring == test_ring) {  // test all 55 list members simultaneously
            return (LIST_LENGTH +1) - i;
        }

        if (test_ring % 2) {    //  ring's tail is 1 ?
            test_ring /= 2;     //  right-shift 1 bit
            // if the ring tail was 1, set head to 1 to simulate wrapping
            test_ring += head_bit;      
        }   else    {           // ring's tail must be 0
            test_ring /= 2;     // right-shift 1 bit
            // if the ring tail was 0, doing nothing leaves head a 0
        }
    }
    // if we got here, they can't be circularly identical
    return 0;
}
// ----------------------------------------------------------------------------
    int main(void)  {
        time_t start = clock();
        uint64_t anchor, test_ring, i,  milliseconds;
        uint8_t try_knt;

        anchor = 31525197391593472; // bits 55,54,53 set true, all others false
        // Anchor right-shifted LIST_LENGTH/2 represents the average search turns
        test_ring = anchor >> (1 + (LIST_LENGTH / 2)); //  117440512; 

        printf("\n\nRunning benchmarks for %llu loops.", LOOP_KNT);
        start = clock();
        for (i = LOOP_KNT; i; i--)  {
            try_knt = is_circular_identical(anchor, test_ring);
            // The shifting of test_ring below is a test fixture to prevent the 
            //  optimizer from optimizing the loop away and returning instantly
            if (i % 2) {
                test_ring /= 2;
            }   else  {
                test_ring *= 2;
            }
        }
        milliseconds = (uint64_t)(clock() - start);
        printf("\nET for is_circular_identical was %f milliseconds."
                "\n\tLast try_knt was %u for test_ring list %llu", 
                        (double)milliseconds, try_knt, test_ring);

        printf("\nConsuming %7.1f clocks per list.\n",
                (double)((milliseconds * (CPU_FREQ / 1000)) / (uint64_t)LOOP_KNT));

        getchar();
        return 0;
}

Wenn Sie zwischen den Zeilen lesen, klingt es so, als würden Sie versuchen, einen Vertreter jeder kreisförmigen Äquivalenzklasse von Zeichenfolgen mit 3 Einsen und 52 Nullen aufzulisten. Wechseln wir von einer dichten Darstellung zu einer spärlichen (Satz von drei Zahlen in range(55)). In dieser Darstellung ist die zirkuläre Verschiebung von sby kdurch das Verständnis gegeben set((i + k) % 55 for i in s). Der lexikografische Mindestrepräsentant in einer Klasse enthält immer die Position 0. Bei einem Satz des Formulars {0, i, j}mit 0 < i < jsind die anderen Kandidaten für das Minimum in der Klasse {0, j - i, 55 - i}und {0, 55 - j, 55 + i - j}. Daher muss (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))das Original minimal sein. Hier ist ein Aufzählungscode.

def makereps():
    reps = []
    for i in range(1, 55 - 1):
        for j in range(i + 1, 55):
            if (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j)):
                reps.append('1' + '0' * (i - 1) + '1' + '0' * (j - i - 1) + '1' + '0' * (55 - j - 1))
    return reps

Wiederholen Sie das erste Array und verwenden Sie dann den Z-Algorithmus (O (n) Zeit), um das zweite Array im ersten zu finden.

(Hinweis: Sie müssen das erste Array nicht physisch kopieren. Sie können es einfach während des Abgleichs umbrechen.)

Das Schöne am Z-Algorithmus ist, dass er im Vergleich zu KMP, BM usw. sehr einfach
ist. Wenn Sie sich jedoch ehrgeizig fühlen, können Sie den String-Abgleich in linearer Zeit und konstantem Raum durchführen - strstrzum Beispiel. Die Implementierung wäre jedoch schmerzhafter.

Nach der sehr intelligenten Lösung von Salvador Dali können Sie am besten sicherstellen, dass alle Elemente gleich lang sind und beide LISTEN gleich lang sind.

def is_circular_equal(lst1, lst2):
    if len(lst1) != len(lst2):
        return False
    lst1, lst2 = map(str, lst1), map(str, lst2)
    len_longest_element = max(map(len, lst1))
    template = "{{:{}}}".format(len_longest_element)
    circ_lst = " ".join([template.format(el) for el in lst1]) * 2
    return " ".join([template.format(el) for el in lst2]) in circ_lst

Keine Ahnung, ob dies schneller oder langsamer ist als die von AshwiniChaudhary empfohlene Regex-Lösung in Salvador Dalis Antwort, die lautet:

import re

def is_circular_equal(lst1, lst2):
    if len(lst2) != len(lst2):
        return False
    return bool(re.search(r"\b{}\b".format(' '.join(map(str, lst2))),
                          ' '.join(map(str, lst1)) * 2))

Angesichts der Tatsache, dass Sie so viele Vergleiche durchführen müssen, lohnt es sich möglicherweise, Ihre Listen zunächst durchzugehen, um sie in eine kanonische Form umzuwandeln, die leicht verglichen werden kann.

Versuchen Sie, eine Reihe von zirkular eindeutigen Listen zu erhalten? Wenn ja, können Sie sie nach der Konvertierung in Tupel in ein Set werfen.

def normalise(lst):
    # Pick the 'maximum' out of all cyclic options
    return max([lst[i:]+lst[:i] for i in range(len(lst))])

a_normalised = map(normalise,a)
a_tuples = map(tuple,a_normalised)
a_unique = set(a_tuples)

Entschuldigung an David Eisenstat, dass er seine ähnliche Antwort nicht entdeckt hat.

Sie können eine Liste wie folgt rollen:

list1, list2 = [0,1,1,1,0,0,1,0], [1,0,0,1,0,0,1,1]

str_list1="".join(map(str,list1))
str_list2="".join(map(str,list2))

def rotate(string_to_rotate, result=[]):
    result.append(string_to_rotate)
    for i in xrange(1,len(string_to_rotate)):
        result.append(result[-1][1:]+result[-1][0])
    return result

for x in rotate(str_list1):
    if cmp(x,str_list2)==0:
        print "lists are rotationally identical"
        break

Konvertieren Sie zuerst jedes Ihrer Listenelemente (ggf. in einer Kopie) in die gedrehte Version, die lexikalisch am größten ist.

Sortieren Sie dann die resultierende Liste der Listen (wobei ein Index an der ursprünglichen Listenposition beibehalten wird) und vereinheitlichen Sie die sortierte Liste, indem Sie alle Duplikate in der ursprünglichen Liste nach Bedarf markieren.

Huckepack auf @ SalvadorDalis Beobachtung bei der Suche nach Übereinstimmungen von a in einem beliebigen a-langen Slice in b + b, hier ist eine Lösung, die nur Listenoperationen verwendet.

def rollmatch(a,b):
    bb=b*2
    return any(not any(ax^bbx for ax,bbx in zip(a,bb[i:])) for i in range(len(a)))

l1 = [1,0,0,1]
l2 = [1,1,0,0]
l3 = [1,0,1,0]

rollmatch(l1,l2)  # True
rollmatch(l1,l3)  # False

2. Ansatz: [gelöscht]

Keine vollständige, freistehende Antwort, aber beim Thema Optimierung durch Reduzierung von Vergleichen dachte auch ich an normalisierte Darstellungen.

Wenn Ihr Eingabealphabet {0, 1} ist, können Sie die Anzahl der zulässigen Permutationen erheblich reduzieren. Drehen Sie die erste Liste in eine (pseudo-) normalisierte Form (angesichts der Verteilung in Ihrer Frage würde ich eine auswählen, bei der sich eines der 1 Bits ganz links und eines der 0 Bits ganz rechts befindet). Drehen Sie nun vor jedem Vergleich nacheinander die andere Liste durch die möglichen Positionen mit demselben Ausrichtungsmuster.

Wenn Sie beispielsweise insgesamt vier 1-Bits haben, kann es bei dieser Ausrichtung höchstens 4 Permutationen geben, und wenn Sie Cluster benachbarter 1-Bits haben, reduziert jedes zusätzliche Bit in einem solchen Cluster die Anzahl der Positionen.

List 1   1 1 1 0 1 0

List 2   1 0 1 1 1 0  1st permutation
         1 1 1 0 1 0  2nd permutation, final permutation, match, done

Dies verallgemeinert sich auf größere Alphabete und unterschiedliche Ausrichtungsmuster; Die größte Herausforderung besteht darin, eine gute Normalisierung mit nur wenigen möglichen Darstellungen zu finden. Im Idealfall wäre es eine richtige Normalisierung mit einer einzigen eindeutigen Darstellung, aber angesichts des Problems denke ich nicht, dass dies möglich ist.

Aufbauend auf der Antwort von RocketRoy: Konvertieren Sie alle Ihre Listen im Voraus in vorzeichenlose 64-Bit-Zahlen. Drehen Sie für jede Liste diese 55 Bits, um den kleinsten numerischen Wert zu finden.

Sie haben jetzt für jede Liste einen einzelnen vorzeichenlosen 64-Bit-Wert, den Sie direkt mit dem Wert der anderen Listen vergleichen können. Die Funktion is_circular_identical () ist nicht mehr erforderlich.

(Im Wesentlichen erstellen Sie einen Identitätswert für Ihre Listen, der nicht von der Rotation der Listenelemente betroffen ist.) Dies würde sogar funktionieren, wenn Sie eine beliebige Anzahl von Einsen in Ihren Listen haben.

Dies ist die gleiche Idee von Salvador Dali, benötigt aber keine String-Konvertierung. Dahinter steckt die gleiche KMP-Wiederherstellungsidee, um eine unmögliche Schichtinspektion zu vermeiden. Sie rufen nur KMPModified auf (Liste1, Liste2 + Liste2).

    public class KmpModified
    {
        public int[] CalculatePhi(int[] pattern)
        {
            var phi = new int[pattern.Length + 1];
            phi[0] = -1;
            phi[1] = 0;

            int pos = 1, cnd = 0;
            while (pos < pattern.Length)
                if (pattern[pos] == pattern[cnd])
                {
                    cnd++;
                    phi[pos + 1] = cnd;
                    pos++;
                }
                else if (cnd > 0)
                    cnd = phi[cnd];
                else
                {
                    phi[pos + 1] = 0;
                    pos++;
                }

            return phi;
        }

        public IEnumerable<int> Search(int[] pattern, int[] list)
        {
            var phi = CalculatePhi(pattern);

            int m = 0, i = 0;
            while (m < list.Length)
                if (pattern[i] == list[m])
                {
                    i++;
                    if (i == pattern.Length)
                    {
                        yield return m - i + 1;
                        i = phi[i];
                    }
                    m++;
                }
                else if (i > 0)
                {
                    i = phi[i];
                }
                else
                {
                    i = 0;
                    m++;
                }
        }

        [Fact]
        public void BasicTest()
        {
            var pattern = new[] { 1, 1, 10 };
            var list = new[] {2, 4, 1, 1, 1, 10, 1, 5, 1, 1, 10, 9};
            var matches = Search(pattern, list).ToList();

            Assert.Equal(new[] {3, 8}, matches);
        }

        [Fact]
        public void SolveProblem()
        {
            var random = new Random();
            var list = new int[10];
            for (var k = 0; k < list.Length; k++)
                list[k]= random.Next();

            var rotation = new int[list.Length];
            for (var k = 1; k < list.Length; k++)
                rotation[k - 1] = list[k];
            rotation[rotation.Length - 1] = list[0];

            Assert.True(Search(list, rotation.Concat(rotation).ToArray()).Any());
        }
    }

Ich hoffe das hilft!

Das Problem vereinfachen

• Das Problem besteht aus einer Liste der bestellten Artikel
• Die Wertdomäne ist binär (0,1)
• Wir können das Problem reduzieren, indem wir aufeinanderfolgende 1s einer Zählung zuordnen
• und aufeinanderfolgende 0s in eine negative Zählung

Beispiel

A = [ 1, 1, 1, 0, 0, 1, 1, 0 ]
B = [ 1, 1, 0, 1, 1, 1, 0, 0 ]
~
A = [ +3, -2, +2, -1 ]
B = [ +2, -1, +3, -2 ]

• Für diesen Vorgang müssen der erste und der letzte Artikel unterschiedlich sein
• Dies reduziert die Anzahl der Vergleiche insgesamt

Prozess überprüfen

• Wenn wir davon ausgehen, dass sie doppelt vorhanden sind, können wir davon ausgehen, wonach wir suchen
• Grundsätzlich muss das erste Element aus der ersten Liste irgendwo in der anderen Liste vorhanden sein
• Gefolgt von dem, was in der ersten Liste folgt, und auf die gleiche Weise
• Die vorherigen Elemente sollten die letzten Elemente aus der ersten Liste sein
• Da es sich um ein Rundschreiben handelt, ist die Reihenfolge dieselbe

Der Griff

• Die Frage hier ist, wo man anfangen soll, technisch bekannt als lookupundlook-ahead
• Wir werden nur anhand der zweiten Liste prüfen, wo das erste Element der ersten Liste vorhanden ist
• Die Wahrscheinlichkeit häufiger Elemente ist geringer, da wir die Listen in Histogramme abgebildet haben

Pseudo-Code

FUNCTION IS_DUPLICATE (LIST L1, LIST L2) : BOOLEAN

    LIST A = MAP_LIST(L1)
    LIST B = MAP_LIST(L2)

    LIST ALPHA = LOOKUP_INDEX(B, A[0])

    IF A.SIZE != B.SIZE
       OR COUNT_CHAR(A, 0) != COUNT_CHAR(B, ALPHA[0]) THEN

        RETURN FALSE

    END IF

    FOR EACH INDEX IN ALPHA

        IF ALPHA_NGRAM(A, B, INDEX, 1) THEN

            IF IS_DUPLICATE(A, B, INDEX) THEN

                RETURN TRUE

            END IF

        END IF

    END FOR

    RETURN FALSE

END FUNCTION

FUNCTION IS_DUPLICATE (LIST L1, LIST L2, INTEGER INDEX) : BOOLEAN

    INTEGER I = 0

    WHILE I < L1.SIZE DO

        IF L1[I] != L2[(INDEX+I)%L2.SIZE] THEN

            RETURN FALSE

        END IF

        I = I + 1

    END WHILE

    RETURN TRUE

END FUNCTION

Funktionen

• MAP_LIST(LIST A):LIST KARTENFOLGENDE ELEMENTE ALS ZÄHLER IN EINER NEUEN LISTE

• LOOKUP_INDEX(LIST A, INTEGER E):LISTRÜCKGABELISTE DER INDIZES, EIN DENEN DAS ELEMENT IN DER LISTE EXISTIERTA

• COUNT_CHAR(LIST A , INTEGER E):INTEGERZählen Sie, wie Eviele Male ein Element in einer Liste auftrittA

• ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEANPRÜFEN, WENN B[I]SIE A[0] N-GRAMIN BEIDEN ANWEISUNGEN ENTSPRECHEN

Schließlich

Wenn die Listengröße ziemlich groß sein wird oder wenn das Element, von dem aus wir den Zyklus überprüfen, häufig hoch ist, können wir Folgendes tun:

• Suchen Sie zunächst nach dem am wenigsten häufigen Element in der ersten Liste

• Erhöhen Sie den n-Gramm-N-Parameter, um die Wahrscheinlichkeit zu verringern, dass die lineare Prüfung durchlaufen wird

Eine effiziente, schnell zu berechnende "kanonische Form" für die betreffenden Listen kann abgeleitet werden als:

• Zählen Sie die Anzahl der Nullen zwischen den Einsen (ohne Umlauf), um drei Zahlen zu erhalten.
• Drehen Sie die drei Zahlen so, dass die größte Zahl an erster Stelle steht.
• Die erste Zahl ( a) muss zwischen 18und 52(einschließlich) liegen. Codieren Sie es neu zwischen 0und 34.
• Die zweite Zahl ( b) muss zwischen 0und stehen 26, aber es spielt keine Rolle.
• Lassen Sie die dritte Zahl fallen, da es nur ist 52 - (a + b)und keine Informationen hinzufügt

Die kanonische Form ist die Ganzzahl b * 35 + a, die zwischen 0und 936(einschließlich) liegt und ziemlich kompakt ist (insgesamt gibt es 477kreisförmig eindeutige Listen).

Ich habe eine einfache Lösung geschrieben, die beide Listen vergleicht und nur den Index des verglichenen Werts für jede Iteration erhöht (und umschließt).

Ich kenne Python nicht gut, also habe ich es in Java geschrieben, aber es ist wirklich einfach, daher sollte es einfach sein, es an jede andere Sprache anzupassen.

Auf diese Weise können Sie auch Listen anderer Typen vergleichen.

public class Main {

    public static void main(String[] args){
        int[] a = {0,1,1,1,0};
        int[] b = {1,1,0,0,1};

        System.out.println(isCircularIdentical(a, b));
    }

    public static boolean isCircularIdentical(int[] a, int[]b){
        if(a.length != b.length){
            return false;
        }

        //The outer loop is for the increase of the index of the second list
        outer:
        for(int i = 0; i < a.length; i++){
            //Loop trough the list and compare each value to the according value of the second list
            for(int k = 0; k < a.length; k++){
                // I use modulo length to wrap around the index
                if(a[k] != b[(k + i) % a.length]){
                    //If the values do not match I continue and shift the index one further
                    continue outer;
                }
            }
            return true;
        }
        return false;
    }
}

Wie bereits erwähnt, können Sie die normalisierte Rotation einer Liste vergleichen, sobald Sie sie gefunden haben.

Hier ist ein Arbeitscode, der dies tut. Die grundlegende Methode besteht darin, eine normalisierte Rotation für jede Liste zu finden und zu vergleichen:

• Berechnen Sie für jede Liste einen normalisierten Rotationsindex.
• Durchlaufen Sie beide Listen mit ihren Offsets, vergleichen Sie die einzelnen Elemente und kehren Sie zurück, wenn sie nicht übereinstimmen.

Beachten Sie, dass diese Methode nicht von Zahlen abhängt. Sie können Listen mit Zeichenfolgen übergeben (alle Werte, die verglichen werden können).

Anstatt eine Liste-in-Liste-Suche durchzuführen, möchten wir, dass die Liste mit dem Mindestwert beginnt. Daher können wir die Mindestwerte durchlaufen und suchen, bis wir den niedrigsten Wert in Folge gefunden haben, und diesen für weitere Vergleiche speichern bis wir das Beste haben.

Es gibt viele Möglichkeiten, bei der Berechnung des Index vorzeitig zu beenden, Details zu einigen Optimierungen.

• Überspringen Sie die Suche nach dem besten Mindestwert, wenn es nur einen gibt.
• Überspringen Sie die Suche nach Mindestwerten, wenn der vorherige Wert ebenfalls ein Mindestwert ist (dies wird niemals besser übereinstimmen).
• Überspringen Sie die Suche, wenn alle Werte gleich sind.
• Scheitern Sie früh, wenn Listen unterschiedliche Mindestwerte haben.
• Verwenden Sie einen regelmäßigen Vergleich, wenn die Offsets übereinstimmen.
• Passen Sie die Offsets an, um zu vermeiden, dass die Indexwerte während des Vergleichs in eine der Listen eingeschlossen werden.

Beachten Sie, dass in Python eine Liste-in-Liste-Suche möglicherweise schneller ist. Ich war jedoch daran interessiert, einen effizienten Algorithmus zu finden, der auch in anderen Sprachen verwendet werden kann. Es ist auch von Vorteil, das Erstellen neuer Listen zu vermeiden.

def normalize_rotation_index(ls, v_min_other=None):
    """ Return the index or -1 (when the minimum is above `v_min_other`) """

    if len(ls) <= 1:
        return 0

    def compare_rotations(i_a, i_b):
        """ Return True when i_a is smaller.
            Note: unless there are large duplicate sections of identical values,
            this loop will exit early on.
        """
        for offset in range(1, len(ls)):
            v_a = ls[(i_a + offset) % len(ls)]
            v_b = ls[(i_b + offset) % len(ls)]
            if v_a < v_b:
                return True
            elif v_a > v_b:
                return False
        return False

    v_min = ls[0]
    i_best_first = 0
    i_best_last = 0
    i_best_total = 1
    for i in range(1, len(ls)):
        v = ls[i]
        if v_min > v:
            v_min = v
            i_best_first = i
            i_best_last = i
            i_best_total = 1
        elif v_min == v:
            i_best_last = i
            i_best_total += 1

    # all values match
    if i_best_total == len(ls):
        return 0

    # exit early if we're not matching another lists minimum
    if v_min_other is not None:
        if v_min != v_min_other:
            return -1
    # simple case, only one minimum
    if i_best_first == i_best_last:
        return i_best_first

    # otherwise find the minimum with the lowest values compared to all others.
    # start looking after the first we've found
    i_best = i_best_first
    for i in range(i_best_first + 1, i_best_last + 1):
        if (ls[i] == v_min) and (ls[i - 1] != v_min):
            if compare_rotations(i, i_best):
                i_best = i

    return i_best


def compare_circular_lists(ls_a, ls_b):
    # sanity checks
    if len(ls_a) != len(ls_b):
        return False
    if len(ls_a) <= 1:
        return (ls_a == ls_b)

    index_a = normalize_rotation_index(ls_a)
    index_b = normalize_rotation_index(ls_b, ls_a[index_a])

    if index_b == -1:
        return False

    if index_a == index_b:
        return (ls_a == ls_b)

    # cancel out 'index_a'
    index_b = (index_b - index_a)
    if index_b < 0:
        index_b += len(ls_a)
    index_a = 0  # ignore it

    # compare rotated lists
    for i in range(len(ls_a)):
        if ls_a[i] != ls_b[(index_b + i) % len(ls_b)]:
            return False
    return True


assert(compare_circular_lists([0, 9, -1, 2, -1], [-1, 2, -1, 0, 9]) == True)
assert(compare_circular_lists([2, 9, -1, 0, -1], [-1, 2, -1, 0, 9]) == False)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["World", "Hello" "Circular"]) == True)
assert(compare_circular_lists(["Hello" "Circular", "World"], ["Circular", "Hello" "World"]) == False)

Siehe: diese Schnipsel für einige weitere Tests / Beispiele.

Sie können ganz einfach überprüfen, ob eine Liste A einer zyklischen Verschiebung von Liste B in der erwarteten O (N) -Zeit entspricht.

Ich würde eine Polynom-Hash-Funktion verwenden, um den Hash von Liste A und jede zyklische Verschiebung von Liste B zu berechnen. Wenn eine Verschiebung von Liste B denselben Hash wie Liste A hat, würde ich die tatsächlichen Elemente vergleichen, um festzustellen, ob sie gleich sind .

Der Grund dafür ist, dass Sie mit Polynom-Hash-Funktionen (die sehr häufig sind!) Den Hash jeder zyklischen Verschiebung aus der vorherigen in konstanter Zeit berechnen können, sodass Sie Hashes für alle zyklischen Verschiebungen in O ( N) Zeit.

Es funktioniert so:

Nehmen wir an, B hat N Elemente, dann ist der Hash von B unter Verwendung von Primzahl P:

Hb=0;
for (i=0; i<N ; i++)
{
    Hb = Hb*P + B[i];
}

Dies ist eine optimierte Methode zur Bewertung eines Polynoms in P und entspricht:

Hb=0;
for (i=0; i<N ; i++)
{
    Hb += B[i] * P^(N-1-i);  //^ is exponentiation, not XOR
}

Beachten Sie, wie jedes B [i] mit P ^ (N-1-i) multipliziert wird. Wenn wir B um 1 nach links verschieben, wird jedes B [i] mit einem zusätzlichen P multipliziert, mit Ausnahme des ersten. Da sich die Multiplikation über die Addition verteilt, können wir alle Komponenten gleichzeitig multiplizieren, indem wir den gesamten Hash multiplizieren und dann den Faktor für das erste Element festlegen.

Der Hash der Linksverschiebung von B ist gerecht

Hb1 = Hb*P + B[0]*(1-(P^N))

Die zweite Verschiebung nach links:

Hb2 = Hb1*P + B[1]*(1-(P^N))

und so weiter...

HINWEIS: Alle oben genannten Berechnungen werden modulo mit einer bestimmten Maschinenwortgröße durchgeführt, und Sie müssen P ^ N nur einmal berechnen.

Verwenden Sie Sets, um die pythonischste Methode zu finden!

from sets import Set
a = Set ([1, 1, 1, 0, 0])
b = Set ([0, 1, 1, 1, 0]) 
c = Set ([1, 0, 0, 1, 1])
a==b
True
a==b==c
True