Comment vérifier si deux listes sont circulairement identiques en Python

Par exemple, j'ai des listes:

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

Ils semblent différents, mais si l'on suppose que le début et la fin sont connectés, alors ils sont circulairement identiques.

Le problème est que chaque liste que j'ai a une longueur de 55 et ne contient que trois uns et 52 zéros. Sans condition circulaire, il existe 26 235 (55 au choix 3) listes. Cependant, si la condition `` circulaire '' existe, il existe un grand nombre de listes circulairement identiques

Actuellement, je vérifie l'identité circulaire en suivant:

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

Cette fonction nécessite 55 opérations de décalage cyclique dans le pire des cas. Et il y a 26 235 listes à comparer les unes avec les autres. En bref, j'ai besoin de 55 * 26235 * (26235 - 1) / 2 = 18 926 847 225 calculs. C'est à peu près 20 Giga!

Y a-t-il un bon moyen de le faire avec moins de calculs? Ou des types de données qui prennent en charge circulaire ?

Tout d'abord, cela peut être fait en O(n)termes de longueur de la liste. Vous pouvez remarquer que si vous dupliquez votre liste 2 fois ( [1, 2, 3]) sera [1, 2, 3, 1, 2, 3]alors votre nouvelle liste contiendra certainement toutes les listes cycliques possibles.

Il vous suffit donc de vérifier si la liste que vous recherchez se trouve à deux reprises dans votre liste de départ. En python, vous pouvez y parvenir de la manière suivante (en supposant que les longueurs sont les mêmes).

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

Quelques explications sur mon oneliner: list * 2combinera une liste avec elle-même, map(str, [1, 2])convertira tous les nombres en chaîne et ' '.join()convertira le tableau ['1', '2', '111']en chaîne '1 2 111'.

Comme l'ont souligné certaines personnes dans les commentaires, oneliner peut potentiellement donner des faux positifs, donc pour couvrir tous les cas limites possibles:

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 quand on parle de complexité temporelle, il convient de noter que cela O(n)sera réalisé si la sous-chaîne peut être trouvée dans le O(n)temps. Ce n'est pas toujours le cas et dépend de l'implémentation dans votre langage ( bien que potentiellement cela puisse être fait en temps linéaire KMP par exemple).

PS2 pour les personnes qui ont peur du fonctionnement des cordes et pensent de ce fait que la réponse n'est pas bonne. Ce qui est important, c'est la complexité et la rapidité. Cet algorithme fonctionne potentiellement dans le O(n)temps et dans l' O(n)espace, ce qui le rend bien meilleur que tout autre O(n^2)domaine. Pour voir cela par vous-même, vous pouvez exécuter un petit benchmark (crée une liste aléatoire fait apparaître le premier élément et l'ajoute à la fin, créant ainsi une liste cyclique. Vous êtes libre de faire vos propres manipulations)

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 seconde sur ma machine. Pas vraiment longtemps. Maintenant, essayez de comparer cela avec des O(n^2)solutions. Pendant qu'il le compare, vous pouvez voyager des États-Unis à l'Australie (très probablement par un bateau de croisière)

Je ne connais pas suffisamment Python pour répondre à cela dans le langage demandé, mais en C / C ++, étant donné les paramètres de votre question, je convertirais les zéros et les uns en bits et les pousserais sur les bits les moins significatifs d'un uint64_t. Cela vous permettra de comparer les 55 bits d'un seul coup - 1 horloge.

Très rapide, et le tout rentrera dans des caches sur puce (209 880 octets). La prise en charge matérielle du décalage simultané des 55 membres de la liste vers la droite n'est disponible que dans les registres d'un processeur. Il en va de même pour la comparaison des 55 membres simultanément. Cela permet un mappage 1 pour 1 du problème vers une solution logicielle. (et en utilisant les registres SIMD / SSE 256 bits, jusqu'à 256 membres si nécessaire) En conséquence, le code est immédiatement évident pour le lecteur.

Vous pourrez peut-être l'implémenter en Python, je ne le connais tout simplement pas assez bien pour savoir si c'est possible ou quelles pourraient être les performances.

Après avoir dormi dessus, certaines choses sont devenues évidentes, et tout pour le mieux.

1.) Il est si facile de faire tourner la liste circulaire en utilisant des bits que l'astuce très intelligente de Dali n'est pas nécessaire. À l'intérieur d'un registre 64 bits, le décalage de bits standard accomplira la rotation très simplement, et dans une tentative de rendre tout cela plus convivial pour Python, en utilisant l'arithmétique au lieu d'opérations sur les bits.

2.) Le décalage de bits peut être accompli facilement en utilisant la division par 2.

3.) La vérification de la fin de la liste pour 0 ou 1 peut être facilement effectuée par modulo 2.

4.) "Déplacer" un 0 à la tête de la liste à partir de la queue peut être fait en divisant par 2. Ceci parce que si le zéro était réellement déplacé, cela rendrait le 55ème bit faux, ce qu'il est déjà en ne faisant absolument rien.

5.) "Déplacer" un 1 à la tête de la liste à partir de la queue peut être fait en divisant par 2 et en ajoutant 18 014 398 509 481 984 - qui est la valeur créée en marquant le 55ème bit vrai et tout le reste faux.

6.) Si une comparaison de l'ancre et de uint64_t composé est TRUE après une rotation donnée, interrompre et retourner TRUE.

Je convertirais tout le tableau de listes en un tableau de uint64_ts dès le départ pour éviter d'avoir à faire la conversion à plusieurs reprises.

Après avoir passé quelques heures à essayer d'optimiser le code, à étudier le langage d'assemblage, j'ai pu réduire de 20% le temps d'exécution. Je dois ajouter que le compilateur O / S et MSVC a également été mis à jour en milieu de journée hier. Pour quelque raison que ce soit, la qualité du code produit par le compilateur C s'est considérablement améliorée après la mise à jour (15/11/2014). Le temps d'exécution est maintenant d'environ 70 horloges, 17 nanosecondes pour composer et comparer un anneau d'ancrage avec les 55 tours d'un anneau de test et NxN de tous les anneaux contre tous les autres se fait en 12,5 secondes .

Ce code est si serré que tous les registres sauf 4 sont assis à ne rien faire 99% du temps. Le langage d'assemblage correspond presque ligne pour ligne au code C. Très facile à lire et à comprendre. Un grand projet d'assemblage si quelqu'un apprenait cela.

Le matériel est Hazwell i7, MSVC 64 bits, optimisations complètes.

#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;
}

En lisant entre les lignes, on dirait que vous essayez d'énumérer un représentant de chaque classe d'équivalence circulaire de chaînes avec 3 uns et 52 zéros. Passons d'une représentation dense à une représentation clairsemée (ensemble de trois nombres dans range(55)). Dans cette représentation, le déplacement circulaire de spar kest donné par la compréhension set((i + k) % 55 for i in s). Le représentant lexicographique minimum dans une classe contient toujours la position 0. Étant donné un ensemble de la forme {0, i, j}avec 0 < i < j, les autres candidats au minimum dans la classe sont {0, j - i, 55 - i}et {0, 55 - j, 55 + i - j}. Par conséquent, nous avons besoin (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))que l'original soit minimal. Voici un code d'énumération.

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

Répétez le premier tableau, puis utilisez l' algorithme Z (temps O (n)) pour trouver le deuxième tableau à l'intérieur du premier.

(Remarque: vous n'êtes pas obligé de copier physiquement le premier tableau. Vous pouvez simplement boucler pendant la correspondance.)

La bonne chose à propos de l'algorithme Z est qu'il est très simple par rapport à KMP, BM, etc.
Cependant, si vous vous sentez ambitieux, vous pouvez faire une correspondance de chaînes en temps linéaire et en espace constant - strstrpar exemple, faites -le. La mettre en œuvre serait cependant plus douloureuse.

Suite à la solution très intelligente de Salvador Dali, la meilleure façon de la gérer est de s'assurer que tous les éléments sont de la même longueur, ainsi que les deux LISTES sont de la même longueur.

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

Aucun indice si cela est plus rapide ou plus lent que la solution regex recommandée par AshwiniChaudhary dans la réponse de Salvador Dali, qui se lit comme suit:

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))

Étant donné que vous devez faire autant de comparaisons, cela vaut-il la peine de parcourir vos listes pour les convertir en une sorte de forme canonique qui peut être facilement comparée?

Essayez-vous d'obtenir un ensemble de listes circulaires uniques? Si c'est le cas, vous pouvez les jeter dans un ensemble après les avoir convertis en tuples.

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)

Toutes mes excuses à David Eisenstat pour ne pas avoir repéré sa réponse similaire.

Vous pouvez rouler une liste comme ceci:

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

Tout d' abord convertir tous les éléments de votre liste (dans une copie si nécessaire) pour que la version pivotée qui est lexicalement plus grand.

Ensuite, triez la liste de listes résultante (en conservant un index dans la position de liste d'origine) et unifiez la liste triée, en marquant tous les doublons dans la liste d'origine si nécessaire.

En s'appuyant sur l'observation de @ SalvadorDali sur la recherche de correspondances de a dans n'importe quelle tranche de taille a dans b + b, voici une solution utilisant uniquement des opérations de liste.

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ème approche: [supprimé]

Pas une réponse complète et indépendante, mais sur le thème de l'optimisation en réduisant les comparaisons, je pensais moi aussi aux représentations normalisées.

À savoir, si votre alphabet d'entrée est {0, 1}, vous pouvez réduire considérablement le nombre de permutations autorisées. Faites pivoter la première liste vers une forme (pseudo-) normalisée (étant donné la distribution de votre question, je choisirais celle où l'un des 1 bits est à l'extrême gauche et l'un des 0 bits à l'extrême droite). Maintenant, avant chaque comparaison, tournez successivement l'autre liste à travers les positions possibles avec le même motif d'alignement.

Par exemple, si vous avez un total de quatre bits 1, il peut y avoir au plus 4 permutations avec cet alignement, et si vous avez des grappes de 1 bits adjacents, chaque bit supplémentaire dans un tel groupe réduit le nombre de positions.

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

Cela se généralise aux alphabets plus grands et aux différents modèles d'alignement; le principal défi est de trouver une bonne normalisation avec seulement quelques représentations possibles. Idéalement, ce serait une bonne normalisation, avec une seule représentation unique, mais étant donné le problème, je ne pense pas que ce soit possible.

S'appuyant davantage sur la réponse de RocketRoy: convertissez toutes vos listes à l'avance en nombres 64 bits non signés. Pour chaque liste, faites pivoter ces 55 bits pour trouver la plus petite valeur numérique.

Il vous reste maintenant une seule valeur 64 bits non signée pour chaque liste que vous pouvez comparer directement avec la valeur des autres listes. La fonction is_circular_identical () n'est plus nécessaire.

(En substance, vous créez une valeur d'identité pour vos listes qui n'est pas affectée par la rotation des éléments des listes) Cela fonctionnerait même si vous avez un nombre arbitraire de l'un dans vos listes.

C'est la même idée de Salvador Dali mais n'a pas besoin de la conversion de chaîne. Derrière, il y a la même idée de récupération KMP pour éviter une inspection de quart impossible. Ils appellent uniquement KMPModified (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());
        }
    }

J'espère que cette aide!

Simplifier le problème

• Le problème consiste en la liste des articles commandés
• Le domaine de valeur est binaire (0,1)
• Nous pouvons réduire le problème en mappant des 1s consécutifs dans un compte
• et 0s consécutifs dans un compte négatif

Exemple

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 ]

• Ce processus nécessite que le premier élément et le dernier élément soient différents
• Cela réduira le nombre de comparaisons dans l'ensemble

Vérification du processus

• Si nous supposons qu'ils sont en double, nous pouvons supposer ce que nous recherchons
• Fondamentalement, le premier élément de la première liste doit exister quelque part dans l'autre liste
• Suivi de ce qui est suivi dans la première liste, et de la même manière
• Les éléments précédents doivent être les derniers éléments de la première liste
• Puisqu'il est circulaire, l'ordre est le même

La prise

• La question ici est de savoir par où commencer, techniquement connu sous le nom de lookupetlook-ahead
• Nous allons simplement vérifier où se trouve le premier élément de la première liste à travers la deuxième liste
• La probabilité d'élément fréquent est plus faible étant donné que nous avons mappé les listes en histogrammes

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

Les fonctions

• MAP_LIST(LIST A):LIST CARTEZ LES ÉLÉMENTS CONSQUETIFS COMME DES COMPTES DANS UNE NOUVELLE LISTE

• LOOKUP_INDEX(LIST A, INTEGER E):LISTRETOUR LISTE DES INDICES O L'ÉLÉMENT EEXISTE DANS LA LISTEA

• COUNT_CHAR(LIST A , INTEGER E):INTEGERECOMPTEZ LE NOMBRE DE FOIS UN ÉLÉMENT SUR UNE LISTEA

• ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEANVÉRIFIEZ SI B[I]EST ÉQUIVALENT AUX A[0] N-GRAMDEUX DIRECTIONS

finalement

Si la taille de la liste va être assez énorme ou si l'élément à partir duquel nous commençons à vérifier le cycle est souvent élevé, nous pouvons faire ce qui suit:

• Recherchez l'élément le moins fréquent dans la première liste pour commencer

• augmenter le paramètre n-gramme N pour réduire la probabilité de passer par un contrôle linéaire

Une "forme canonique" efficace et rapide à calculer pour les listes en question peut être dérivée comme suit:

• Comptez le nombre de zéros entre les uns (en ignorant le bouclage), pour obtenir trois nombres.
• Faites pivoter les trois nombres pour que le plus grand nombre soit le premier.
• Le premier nombre ( a) doit être compris entre 18et 52(inclus). Recodez-le entre 0et 34.
• Le deuxième nombre ( b) doit être compris entre 0et 26, mais cela n'a pas beaucoup d'importance.
• Supprimez le troisième numéro, car il est juste 52 - (a + b)et n'ajoute aucune information

La forme canonique est l'entier b * 35 + a, qui est compris entre 0et 936(inclus), ce qui est assez compact (il y a 477des listes circulairement uniques au total).

J'ai écrit une solution simple qui compare les deux listes et augmente simplement (et entoure) l'indice de la valeur comparée pour chaque itération.

Je ne connais pas bien python donc je l'ai écrit en Java, mais c'est vraiment simple, donc il devrait être facile de l'adapter à n'importe quel autre langage.

Par cela, vous pouvez également comparer des listes d'autres types.

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

Comme d'autres l'ont mentionné, une fois que vous avez trouvé la rotation normalisée d'une liste, vous pouvez les comparer.

Voici un code de travail qui fait cela, la méthode de base consiste à trouver une rotation normalisée pour chaque liste et à comparer:

• Calculez un indice de rotation normalisé sur chaque liste.
• Faites une boucle sur les deux listes avec leurs décalages, comparez chaque élément et retournez-le s'ils ne correspondent pas.

Notez que cette méthode ne dépend pas des nombres, vous pouvez passer des listes de chaînes (toutes les valeurs qui peuvent être comparées).

Au lieu de faire une recherche de liste dans la liste, nous savons que nous voulons que la liste commence par la valeur minimale - afin que nous puissions boucler sur les valeurs minimales, en recherchant jusqu'à ce que nous trouvions laquelle a les valeurs successives les plus basses, en la stockant pour d'autres comparaisons jusqu'à ce que nous ayons le meilleur.

Il existe de nombreuses possibilités de sortir tôt lors du calcul de l'indice, des détails sur certaines optimisations.

• Ignorez la recherche de la meilleure valeur minimale lorsqu'il n'y en a qu'une.
• Ignorez la recherche des valeurs minimales lorsque la valeur précédente est également une valeur minimale (elle ne sera jamais meilleure).
• Ignorez la recherche lorsque toutes les valeurs sont identiques.
• Échouez tôt lorsque les listes ont des valeurs minimales différentes.
• Utilisez une comparaison régulière lorsque les décalages correspondent.
• Ajustez les décalages pour éviter d'encapsuler les valeurs d'index sur l'une des listes lors de la comparaison.

Notez qu'en Python, une recherche de liste dans une liste peut être plus rapide, mais j'étais intéressé par un algorithme efficace - qui pourrait également être utilisé dans d'autres langues. En outre, il y a un avantage à éviter de créer de nouvelles listes.

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)

Voir: cet extrait de code pour d'autres tests / exemples.

Vous pouvez vérifier assez facilement si une liste A est égale à un décalage cyclique de la liste B dans le temps O (N) attendu.

J'utiliserais une fonction de hachage polynomiale pour calculer le hachage de la liste A et chaque déplacement cyclique de la liste B.Lorsqu'un décalage de la liste B a le même hachage que la liste A, je comparerais les éléments réels pour voir s'ils sont égaux .

La raison pour laquelle c'est rapide est qu'avec les fonctions de hachage polynomiales (qui sont extrêmement courantes!), Vous pouvez calculer le hachage de chaque décalage cyclique par rapport au précédent en temps constant, de sorte que vous pouvez calculer les hachages pour tous les décalages cycliques dans O ( N) heure.

Cela fonctionne comme ceci:

Disons que B a N éléments, alors le hachage de B utilisant le premier P est:

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

C'est une manière optimisée d'évaluer un polynôme dans P, et équivaut à:

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

Remarquez comment chaque B [i] est multiplié par P ^ (N-1-i). Si nous décalons B vers la gauche de 1, alors chaque B [i] sera multiplié par un P supplémentaire, sauf le premier. Puisque la multiplication se distribue sur l'addition, nous pouvons multiplier tous les composants à la fois simplement en multipliant le hachage entier, puis fixer le facteur pour le premier élément.

Le hachage du décalage gauche de B est juste

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

Le deuxième décalage à gauche:

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

etc...

REMARQUE: tous les calculs ci-dessus sont effectués modulo une taille de mot machine, et vous ne devez calculer P ^ N qu'une seule fois.

Pour coller à la manière la plus pythonique de le faire, utilisez des sets!

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