Cara memeriksa apakah dua daftar identik secara melingkar dalam Python

Misalnya, saya punya daftar:

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

Mereka tampaknya berbeda, tetapi jika seharusnya bahwa awal dan akhir terhubung, maka mereka identik secara sirkuler .

Masalahnya adalah, setiap daftar yang saya miliki memiliki panjang 55 dan hanya berisi tiga dan 52 nol di dalamnya. Tanpa kondisi lingkaran, ada 26.235 (55 pilih 3) daftar. Namun, jika kondisi 'melingkar' ada, ada sejumlah besar daftar identik sirkuler

Saat ini saya memeriksa identitas sirkuler dengan mengikuti:

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

Fungsi ini membutuhkan 55 operasi pergantian siklik pada kondisi terburuk. Dan ada 26.235 daftar untuk dibandingkan satu sama lain. Singkatnya, saya perlu 55 * 26.235 * (26.235 - 1) / 2 = 18.926.847.225 perhitungan. Sekitar 20 Giga!

Apakah ada cara yang baik untuk melakukannya dengan perhitungan yang lebih sedikit? Atau tipe data apa saja yang mendukung sirkular ?

Pertama, ini dapat dilakukan dalam O(n)hal panjang daftar. Anda dapat melihat bahwa jika Anda akan menduplikasi daftar Anda 2 kali ( [1, 2, 3]) akan [1, 2, 3, 1, 2, 3]maka daftar baru Anda pasti akan menyimpan semua daftar siklik yang mungkin.

Jadi yang Anda butuhkan adalah memeriksa apakah daftar yang Anda cari ada dalam 2 kali dari daftar awal Anda. Dalam python Anda dapat mencapai ini dengan cara berikut (dengan asumsi bahwa panjangnya sama).

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

Beberapa penjelasan tentang oneliner saya: list * 2akan menggabungkan daftar dengan dirinya sendiri, map(str, [1, 2])mengubah semua angka menjadi string dan ' '.join()akan mengubah array ['1', '2', '111']menjadi string'1 2 111' .

Seperti yang ditunjukkan oleh beberapa orang di komentar, oneliner berpotensi memberikan beberapa hal positif yang salah, sehingga untuk mencakup semua kemungkinan kasus tepi:

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 ketika berbicara tentang kompleksitas waktu, perlu diperhatikan bahwa O(n)akan tercapai jika substring dapat ditemukan dalam O(n)waktu. Tidak selalu demikian dan tergantung pada implementasi dalam bahasa Anda ( meskipun berpotensi dapat dilakukan secara linear waktu KMP misalnya).

PS2 untuk orang-orang yang takut operasi string dan karena fakta ini berpikir bahwa jawabannya tidak baik. Yang penting adalah kompleksitas dan kecepatan. Algoritma ini berpotensi berjalan dalam ruang O(n)dan waktu O(n)yang membuatnya jauh lebih baik daripada apa pun di O(n^2)domain. Untuk melihatnya sendiri, Anda dapat menjalankan tolok ukur kecil (membuat daftar acak muncul elemen pertama dan menambahkannya sampai akhir sehingga membuat daftar siklik. Anda bebas melakukan manipulasi Anda sendiri)

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 detik di mesin saya. Tidak terlalu lama. Sekarang coba bandingkan ini dengan O(n^2)solusi. Saat membandingkannya, Anda dapat melakukan perjalanan dari AS ke Australia (kemungkinan besar dengan kapal pesiar)

Tidak cukup berpengetahuan luas dalam Python untuk menjawab ini dalam bahasa yang Anda minta, tetapi dalam C / C ++, mengingat parameter pertanyaan Anda, saya akan mengonversi nol dan yang menjadi bit dan mendorong mereka ke bit paling tidak signifikan dari sebuah uint64_t. Ini akan memungkinkan Anda untuk membandingkan semua 55 bit dalam sekali gerakan - 1 jam.

Sangat cepat, dan semuanya akan sesuai dengan cache on-chip (209.880 byte). Dukungan perangkat keras untuk menggeser semua 55 daftar anggota secara bersamaan hanya tersedia di register CPU. Hal yang sama berlaku untuk membandingkan semua 55 anggota secara bersamaan. Ini memungkinkan pemetaan 1-untuk-1 masalah ke solusi perangkat lunak. (dan menggunakan register 256 bit SIMD / SSE, hingga 256 anggota jika diperlukan). Akibatnya, kode ini segera jelas bagi pembaca.

Anda mungkin dapat mengimplementasikan ini dengan Python, saya hanya tidak tahu cukup baik untuk mengetahui apakah itu mungkin atau bagaimana kinerjanya.

Setelah tidur di atasnya beberapa hal menjadi jelas, dan semuanya menjadi lebih baik.

1.) Sangat mudah untuk memutar daftar yang terhubung secara melingkar menggunakan bit sehingga trik Dali yang sangat pintar tidak diperlukan. Di dalam register 64-bit, penggeseran bit standar akan menyelesaikan rotasi dengan sangat sederhana, dan dalam upaya menjadikan ini lebih ramah Python, dengan menggunakan aritmatika alih-alih bit ops.

2.) Penggeseran bit dapat dilakukan dengan mudah menggunakan membagi dengan 2.

3.) Memeriksa akhir daftar untuk 0 atau 1 dapat dengan mudah dilakukan oleh modulo 2.

4.) "Memindahkan" a 0 ke kepala daftar dari ekor dapat dilakukan dengan membagi dengan 2. Ini karena jika nol benar-benar dipindahkan itu akan membuat bit ke-55 salah, yang sudah dengan tidak melakukan apa-apa sama sekali.

5.) "Memindahkan" 1 ke kepala daftar dari ekor dapat dilakukan dengan membaginya dengan 2 dan menambahkan 18.014.398.509.481.984 - yang merupakan nilai yang dibuat dengan menandai bit ke-55 true dan sisanya salah.

6.) Jika perbandingan jangkar dan terdiri uint64_t BENAR setelah setiap rotasi yang diberikan, istirahat dan kembali BENAR.

Saya akan mengonversi seluruh array daftar ke dalam array uint64_ts tepat di depan untuk menghindari harus melakukan konversi berulang kali.

Setelah menghabiskan beberapa jam mencoba mengoptimalkan kode, mempelajari bahasa rakitan saya bisa mencukur 20% dari runtime. Saya harus menambahkan bahwa kompiler O / S dan MSVC mendapat pembaruan tengah hari kemarin juga. Untuk alasan apa pun, kualitas kode yang dihasilkan oleh kompiler C meningkat secara dramatis setelah pembaruan (15/11/2014). Run-time sekarang ~ 70 jam, 17 nanodetik untuk menyusun dan membandingkan cincin jangkar dengan semua 55 putaran cincin tes dan NxN dari semua cincin terhadap yang lainnya dilakukan dalam 12,5 detik .

Kode ini sangat ketat, kecuali 4 register yang tidak melakukan 99% dari waktu. Bahasa assembly cocok dengan kode C hampir baris untuk baris. Sangat mudah dibaca dan dimengerti. Proyek perakitan yang bagus jika seseorang mengajari mereka sendiri.

Perangkat kerasnya adalah Hazwell i7, MSVC 64-bit, optimisasi penuh.

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

Membaca yang tersirat, sepertinya Anda mencoba untuk menghitung satu perwakilan dari setiap kelas string ekivalen lingkaran dengan 3 yang dan 52 nol. Mari beralih dari representasi padat untuk satu jarang (set tiga angka di range(55)). Dalam representasi ini, pergeseran lingkaran soleh kdiberikan oleh pemahaman set((i + k) % 55 for i in s). Perwakilan minimum leksikografi di kelas selalu berisi posisi 0. Mengingat satu set bentuk {0, i, j}dengan 0 < i < j, kandidat lainnya untuk minimum di kelas yang {0, j - i, 55 - i}dan {0, 55 - j, 55 + i - j}. Oleh karena itu, kita perlu (i, j) <= min((j - i, 55 - i), (55 - j, 55 + i - j))minimum untuk yang asli. Ini beberapa kode enumerasi.

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

Ulangi array pertama, lalu gunakan algoritma Z (O (n) waktu) untuk menemukan array kedua di dalam array pertama.

(Catatan: Anda tidak perlu menyalin secara fisik array pertama. Anda hanya dapat membungkus selama pencocokan.)

Yang menyenangkan tentang algoritma Z adalah sangat sederhana dibandingkan dengan KMP, BM, dll.
Namun, jika Anda merasa ambisius, Anda dapat melakukan pencocokan string dalam waktu linier dan ruang konstan - strstr, misalnya, melakukan ini. Menerapkannya akan lebih menyakitkan.

Menindaklanjuti solusi yang sangat cerdas dari Salvador Dali, cara terbaik untuk menanganinya adalah memastikan semua elemen memiliki panjang yang sama, serta kedua LISTS memiliki panjang yang sama.

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

Tidak ada petunjuk apakah ini lebih cepat atau lebih lambat dari solusi regex yang direkomendasikan AshwiniChaudhary dalam jawaban Salvador Dali, yang berbunyi:

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

Mengingat bahwa Anda perlu melakukan begitu banyak perbandingan, mungkinkah ini layak untuk Anda saat mengambil langkah awal melalui daftar Anda untuk mengubahnya menjadi semacam bentuk kanonik yang dapat dengan mudah dibandingkan?

Apakah Anda mencoba mendapatkan daftar unik yang melingkar? Jika demikian, Anda dapat membuangnya ke dalam set setelah mengonversi ke tupel.

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)

Permintaan maaf kepada David Eisenstat karena tidak menemukan jawaban yang sama.

Anda dapat menggulung satu daftar seperti ini:

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

Konversi terlebih dahulu setiap elemen daftar Anda (dalam salinan jika perlu) untuk itu versi diputar yang leksikal terbesar.

Kemudian urutkan daftar daftar yang dihasilkan (mempertahankan indeks ke posisi daftar asli) dan menyatukan daftar diurutkan, menandai semua duplikat dalam daftar asli sesuai kebutuhan.

Membonceng pengamatan @ SalvadorDali tentang mencari kecocokan dalam setiap irisan berukuran panjang dalam b + b, berikut adalah solusi menggunakan operasi daftar saja.

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

Pendekatan 2: [dihapus]

Bukan jawaban yang lengkap dan berdiri bebas, tetapi pada topik optimisasi dengan mengurangi perbandingan, saya juga memikirkan representasi yang dinormalisasi.

Yaitu, jika alfabet input Anda adalah {0, 1}, Anda dapat mengurangi jumlah permutasi yang diizinkan secara signifikan. Putar daftar pertama ke bentuk (pseudo-) yang dinormalisasi (mengingat distribusi dalam pertanyaan Anda, saya akan memilih satu di mana salah satu dari 1 bit berada di paling kiri, dan salah satu dari 0 bit ada di paling kanan). Sekarang sebelum setiap perbandingan, berturut-turut putar daftar lainnya melalui posisi yang mungkin dengan pola penyelarasan yang sama.

Sebagai contoh, jika Anda memiliki total empat 1 bit, bisa ada paling banyak 4 permutasi dengan penyelarasan ini, dan jika Anda memiliki kelompok 1 bit yang berdekatan, setiap bit tambahan dalam sebuah cluster mengurangi jumlah posisi.

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

Ini digeneralisasikan ke huruf yang lebih besar dan pola penyelarasan yang berbeda; tantangan utamanya adalah menemukan normalisasi yang baik dengan hanya beberapa kemungkinan representasi. Idealnya, itu akan menjadi normalisasi yang tepat, dengan satu representasi unik, tetapi mengingat masalahnya, saya pikir itu tidak mungkin.

Membangun lebih jauh jawaban RocketRoy: Konversi semua daftar Anda di muka menjadi angka 64 bit yang tidak ditandatangani. Untuk setiap daftar, putar 55 bit itu di sekitar untuk menemukan nilai numerik terkecil.

Anda sekarang dibiarkan dengan nilai 64 bit tak bertanda tunggal untuk setiap daftar yang dapat Anda bandingkan langsung dengan nilai daftar lainnya. Fungsi is_circular_identical () tidak diperlukan lagi.

(Pada intinya, Anda membuat nilai identitas untuk daftar Anda yang tidak terpengaruh oleh rotasi elemen daftar) Itu bahkan akan berfungsi jika Anda memiliki nomor sewenang-wenang di dalam daftar Anda.

Ini adalah ide yang sama dari Salvador Dali tetapi tidak perlu konversi string. Di belakang adalah ide pemulihan KMP yang sama untuk menghindari inspeksi shift yang tidak mungkin. Mereka hanya memanggil KMPModified (list1, list2 + list2).

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

Semoga bantuan ini!

Menyederhanakan Masalah

• Masalahnya terdiri dari daftar barang yang dipesan
• Domain nilai adalah biner (0,1)
• Kami dapat mengurangi masalah dengan memetakan secara berurutan 1 menjadi hitungan
• dan berturut-turut 0menjadi hitungan negatif

Contoh

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 ]

• Proses ini mengharuskan item pertama dan item terakhir harus berbeda
• Ini akan mengurangi jumlah perbandingan secara keseluruhan

Memeriksa proses

• Jika kita menganggap itu duplikat, maka kita dapat mengasumsikan apa yang kita cari
• Pada dasarnya item pertama dari daftar pertama harus ada di suatu tempat di daftar lainnya
• Diikuti oleh apa yang diikuti di daftar pertama, dan dengan cara yang sama
• Item sebelumnya harus menjadi item terakhir dari daftar pertama
• Karena bentuknya bundar, urutannya sama

Pegangan

• Pertanyaannya di sini adalah di mana untuk memulai, secara teknis dikenal sebagai lookupdanlook-ahead
• Kami hanya akan memeriksa di mana elemen pertama dari daftar pertama ada melalui daftar kedua
• Probabilitas elemen yang sering lebih rendah mengingat bahwa kami memetakan daftar ke dalam histogram

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

Fungsi

• MAP_LIST(LIST A):LIST PETA UNSUR KONSQUETIF SEBAGAI NEGARA DALAM DAFTAR BARU

• LOOKUP_INDEX(LIST A, INTEGER E):LISTKEMBALI DAFTAR INDIKASI DI MANA UNSUR-UNSUR EDI DALAM DAFTARA

• COUNT_CHAR(LIST A , INTEGER E):INTEGERCOUNT BAGAIMANA BANYAK KALI SEBUAH UNSUR ETERJADI DALAM DAFTARA

• ALPHA_NGRAM(LIST A,LIST B,INTEGER I,INTEGER N):BOOLEANPERIKSA JIKA B[I]SETIAP DENGAN A[0] N-GRAMDALAM KEDUA ARAH

Akhirnya

Jika ukuran daftar akan sangat besar atau jika elemen yang kita mulai periksa siklusnya sering tinggi, maka kita dapat melakukan hal berikut:

• Cari item yang paling jarang di daftar pertama untuk memulai

• meningkatkan parameter n-gram N untuk menurunkan kemungkinan melalui pemeriksaan linear

"Bentuk kanonik" yang efisien, cepat untuk dihitung untuk daftar yang dimaksud dapat diturunkan sebagai:

• Hitung jumlah nol di antara yang (mengabaikan wrap-around), untuk mendapatkan tiga angka.
• Putar ketiga angka sehingga angka terbesar adalah yang pertama.
• Angka pertama ( a) harus antara 18dan 52(inklusif). Encode ulang sebagai antara 0dan34 .
• Angka kedua ( b) harus antara 0dan 26, tetapi tidak masalah.
• Jatuhkan nomor ketiga, karena ini adil 52 - (a + b)dan tidak menambah informasi

Bentuk kanonik adalah bilangan bulat b * 35 + a, yang berada di antara 0dan 936(inklusif), yang cukup kompak (ada daftar 477melingkar-unik total).

Saya menulis solusi langsung yang membandingkan daftar dan hanya meningkatkan (dan membungkus) indeks dari nilai yang dibandingkan untuk setiap iterasi.

Saya tidak tahu python dengan baik, jadi saya menulisnya di Jawa, tapi itu sangat sederhana sehingga harus mudah untuk beradaptasi dengan bahasa lain

Dengan ini, Anda juga dapat membandingkan daftar jenis lainnya.

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

Seperti yang disebutkan orang lain, setelah Anda menemukan rotasi daftar yang dinormalisasi, Anda dapat membandingkannya.

Berikut ini beberapa kode kerja yang melakukan ini, Metode dasar adalah menemukan rotasi yang dinormalisasi untuk setiap daftar dan membandingkan:

• Hitung indeks rotasi yang dinormalisasi pada setiap daftar.
• Ulangi kedua daftar dengan offset mereka, membandingkan setiap item, kembali jika salah cocok.

Perhatikan bahwa metode ini tidak bergantung pada angka, Anda dapat mengirimkan daftar string (nilai apa pun yang dapat dibandingkan).

Alih-alih melakukan pencarian daftar-dalam-daftar, kami tahu kami ingin daftar dimulai dengan nilai minimum - sehingga kami dapat mengulangi nilai-nilai minimum, mencari sampai kami menemukan mana yang memiliki nilai berturut-turut terendah, menyimpannya untuk perbandingan lebih lanjut sampai kita mendapatkan yang terbaik.

Ada banyak peluang untuk keluar lebih awal saat menghitung indeks, detail beberapa optimasi.

• Lewati mencari nilai minimum terbaik saat hanya ada satu.
• Melewati pencarian nilai minimum ketika yang sebelumnya juga merupakan nilai minimum (itu tidak akan pernah menjadi kecocokan yang lebih baik).
• Lewati pencarian ketika semua nilai sama.
• Gagal lebih awal ketika daftar memiliki nilai minimum yang berbeda.
• Gunakan perbandingan reguler saat offset cocok.
• Sesuaikan offset untuk menghindari membungkus nilai indeks pada salah satu daftar selama perbandingan.

Perhatikan bahwa dalam Python pencarian daftar-dalam-daftar mungkin lebih cepat, namun saya tertarik untuk menemukan algoritma yang efisien - yang dapat digunakan dalam bahasa lain juga. Juga, ada beberapa keuntungan untuk menghindari membuat daftar baru.

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)

Lihat: cuplikan ini untuk beberapa tes / contoh lainnya.

Anda dapat memeriksa untuk melihat apakah daftar A sama dengan perubahan siklik daftar B dalam waktu O (N) yang diharapkan dengan cukup mudah.

Saya akan menggunakan fungsi hash polinomial untuk menghitung hash dari daftar A, dan setiap perubahan siklik daftar B. Di mana pergeseran daftar B memiliki hash yang sama dengan daftar A, saya akan membandingkan elemen aktual untuk melihat apakah mereka sama. .

Alasan ini cepat adalah bahwa dengan fungsi hash polinomial (yang sangat umum!), Anda dapat menghitung hash dari setiap perubahan siklik dari sebelumnya dalam waktu yang konstan, sehingga Anda dapat menghitung hash untuk semua pergeseran siklik di O ( N) waktu.

Ini berfungsi seperti ini:

Katakanlah B memiliki elemen N, maka hash B menggunakan prime P adalah:

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

Ini adalah cara yang dioptimalkan untuk mengevaluasi polinomial dalam P, dan setara dengan:

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

Perhatikan bagaimana setiap B [i] dikalikan dengan P ^ (N-1-i). Jika kita menggeser B ke kiri dengan 1, maka setiap setiap B [i] akan dikalikan dengan P tambahan, kecuali yang pertama. Karena multiplikasi mendistribusikan lebih dari tambahan, kita dapat melipatgandakan semua komponen sekaligus hanya dengan mengalikan seluruh hash, dan kemudian memperbaiki faktor untuk elemen pertama.

Hash dari shift kiri B hanya

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

Pergeseran kiri kedua:

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

dan seterusnya...

CATATAN: semua matematika di atas dilakukan modulo beberapa ukuran kata mesin, dan Anda hanya perlu menghitung P ^ N satu kali.

Untuk merekatkan cara paling pythonic untuk melakukannya, gunakan set!

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