Αλγόριθμος για εύρεση εαν μια ακολουθία αριθμών αποτελείται απο την επανάληψη μιας υποακολουθίας

[Lanike71]

Νομίζω ότι το καλύτερο, είναι να γράψει ο OP όλες τις περιπτώσεις που θεωρεί ότι ο αλγόριθμος πρέπει να πει ΝΑΙ και πότε ΟΧΙ, για το αν είναι υπακολουθία ή όχι.

Γράφεις για το 232124412321244123212441232124412321244 . Είναι υπακολουθία;

Αν είναι αυτό, επειδή περιέχει το 12441232 στη μέση κάποιας ακολουθίας ή επειδή είναι επαναλαμβανόμενο και συνεχόμενο;

Στο 1211211213, υπάρχει υπακολουθία ή όχι; Στο 121121333121;

Αν τώρα η απάντηση του @k33theod σε κάλυψε, πιστεύω ότι πρέπει να βρεθεί ένας εξυπνότερος τρόπος σε συνδυασμό με αυτόν για να αποφύγεις κάποιες περιπτώσεις, αλλιώς μπλέκεις με brute force και σε τεράστιες ακολουθίες θα έχεις πρόβλημα.

Το μήκος το γνωρίζεις πάνω κάτω ή όχι;

Επεξ/σία 8 Οκτωβρίου 2018 από Lanike71

[k33theod]

1 ώρα πριν, Fortistis είπε

Το είπε και ένας πιο πάνω, αλλά δεν το προσέξατε. 

Στο «123123123123», υποακολουθία είναι και το 123 αλλά και το 123123. 

Δεν ξέρω τι αξία μπορεί να έχει κάτι τέτοιο αφού είναι αυτόνόητο ότι επαναλήψεις του 123 μπορούν να είναι επίσης pattern και παράγονται εύκολα από το 1ο. Έστω 123, 12φορές

το patern είναι 123 το 2*123 μπορούμε να το θεωρήσουμε επίσης patern όπως και τα  3*123, 4*123, 6*123 και 12*123. Δεν χρειάζεσαι όμως κανένα εκτός του αρχικού για να παράγεις το τελικό σου αποτέλεσμα και όλα τα άλλα είναι εύκολα υπολογίσιμα εφόσον ξέρεις το βασικό. Είναι όπως τα background patterns στο web, παίρνεις το μικρότερο και με repeatx repeaty παράγεις το background.

[Lanike71]

9 λεπτά πριν, k33theod είπε

Δεν ξέρω τι αξία μπορεί να έχει κάτι τέτοιο αφού είναι αυτόνόητο ότι επαναλήψεις του 123 μπορούν να είναι επίσης pattern και παράγονται εύκολα από το 1ο. Έστω 123, 12φορές

το patern είναι 123 το 2*123 μπορούμε να το θεωρήσουμε επίσης patern όπως και τα  3*123, 4*123, 6*123 και 12*123. Δεν χρειάζεσαι όμως κανένα εκτός του αρχικού για να παράγεις το τελικό σου αποτέλεσμα και όλα τα άλλα είναι εύκολα υπολογίσιμα εφόσον ξέρεις το βασικό. Είναι όπως τα background patterns στο web, παίρνεις το μικρότερο και με repeatx repeaty παράγεις το background.

Σωστός έτσι όπως το λες, αλλά εγώ το έγραψα με το σκεπτικό ότι ίσως θέλει τη μέγιστη υπακολουθία αλλά και το ότι η υπακολουθία έχει κάποια σημασία.

Στο 1123, υπάρχει υπακολουθία του 1; Στο 1123456 επίσης; Ακόμα δεν έχει οριστεί το τι είναι υπακολουθία.

[k33theod]

49 λεπτά πριν, Lanike71 είπε

Νομίζω ότι το καλύτερο, είναι να γράψει ο OP όλες τις περιπτώσεις που θεωρεί ότι ο αλγόριθμος πρέπει να πει ΝΑΙ και πότε ΟΧΙ, για το αν είναι υπακολουθία ή όχι.

Γράφεις για το 232124412321244123212441232124412321244 . Είναι υπακολουθία;

Αν είναι αυτό, επειδή περιέχει το 12441232 στη μέση κάποιας ακολουθίας ή επειδή είναι επαναλαμβανόμενο και συνεχόμενο;

Στο 1211211213, υπάρχει υπακολουθία ή όχι; Στο 121121333121; 

Αν τώρα η απάντηση του @k33theod σε κάλυψε, πιστεύω ότι πρέπει να βρεθεί ένας εξυπνότερος τρόπος σε συνδυασμό με αυτόν για να αποφύγεις κάποιες περιπτώσεις, αλλιώς μπλέκεις με brute force και σε τεράστιες ακολουθίες θα έχεις πρόβλημα.

Το μήκος το γνωρίζεις πάνω κάτω ή όχι;

νομίζω κάπως μπερδεύει το θέμα χωρίς λόγο.  Για το 1ο που γράφεις εφόσον θεωρήσουμε ότι η ακολουθία αφήνει σκουπίδια στην αρχή ή στο τέλος υπάρχει patern. Η συνάρτηση βρήκε το

23212441

Αυτό όμως εφόσον υπάρχει 1 σκουπίδι στην αρχή μετατρέπεται αυτόματα σε 32124412 αν υπάρχουν 2 σκουπίδια σε 21244123, 3 σκουπίδια 12441232 και λοιπά. Μπορώ να έχω λοιπόν len(patern) paterns που είναι όλα σωστά. Ελπίζω να γίνομαι κατανοητός.  Άλλη μια φορά. Όταν κάτι επαναλαμβάνεται ασ πούε η λέξη ΑΒΓΟ και κόψω αυθαίρετα ένα κομμάτι μπορώ να θέωρησω ότι το patern είναι το το ΓΟΑΒ ή ΟΑΒΓ ή ΒΓΟΑ που είναι όλα σωστά.

Στο 2ο που λες δεν υπάρχει γιατί υπάρχει σκουπίδι στο τέλος που δεν είναι κομάτι patern.

 

32 λεπτά πριν, Lanike71 είπε

Σωστός έτσι όπως το λες, αλλά εγώ το έγραψα με το σκεπτικό ότι ίσως θέλει τη μέγιστη υπακολουθία αλλά και το ότι η υπακολουθία έχει κάποια σημασία.

Στο 1123, υπάρχει υπακολουθία του 1; Στο 1123456 επίσης; Ακόμα δεν έχει οριστεί το τι είναι υπακολουθία.

Συμφωνώ γιαυτό όταν είπε μάλλον θα κάνει δουλειά, είπα αυτό είναι άλλο θέμα.

 

Επεξ/σία 8 Οκτωβρίου 2018 από k33theod

[Fortistis]

3 ώρες πριν, k33theod είπε

Δεν ξέρω τι αξία μπορεί να έχει κάτι τέτοιο αφού είναι αυτόνόητο ότι επαναλήψεις του 123 μπορούν να είναι επίσης pattern και παράγονται εύκολα από το 1ο. Έστω 123, 12φορές

το patern είναι 123 το 2*123 μπορούμε να το θεωρήσουμε επίσης patern όπως και τα  3*123, 4*123, 6*123 και 12*123. Δεν χρειάζεσαι όμως κανένα εκτός του αρχικού για να παράγεις το τελικό σου αποτέλεσμα και όλα τα άλλα είναι εύκολα υπολογίσιμα εφόσον ξέρεις το βασικό. Είναι όπως τα background patterns στο web, παίρνεις το μικρότερο και με repeatx repeaty παράγεις το background.

Είναι διαφορετικό το πώς μπορείς να συμπίεσεις/κωδικοποιήσεις μία σειρά και διαφορετικό ποια είναι η μέγιστη κοινή υποσκολουθία της. 

[masteripper]

Πάντα ψάχνουμε για την ελάχιστη ακολουθία...περισσότερα θα ξέρω όταν το βάλω σε εφαρμογή αλλά προς το παρον έχω άλλα θέματα να επιλυσω..

Επεξ/σία 8 Οκτωβρίου 2018 από masteripper

[defacer]

Η λύση που συζητάμε είναι μια καλή πρώτη σκέψη, αλλά είναι η λεγόμενη naïve λύση: λειτουργεί μια χαρά σε μικρά προβλήματα, αλλά σε "μεγάλα" inputs είτε δεν δουλεύει (πχ εδώ είναι απαραίτητη προϋπόθεση να χωράει όλο το input σε ένα string, και δύο φορές+ όλο το input ταυτόχρονα στη μνήμη) είτε θα είναι τόσο αργή που δε θα τερματίσει.

Για τι μέγεθος input μιλάμε;

[masteripper]

5 ώρες πριν, defacer είπε

Η λύση που συζητάμε είναι μια καλή πρώτη σκέψη, αλλά είναι η λεγόμενη naïve λύση: λειτουργεί μια χαρά σε μικρά προβλήματα, αλλά σε "μεγάλα" inputs είτε δεν δουλεύει (πχ εδώ είναι απαραίτητη προϋπόθεση να χωράει όλο το input σε ένα string, και δύο φορές+ όλο το input ταυτόχρονα στη μνήμη) είτε θα είναι τόσο αργή που δε θα τερματίσει.

Για τι μέγεθος input μιλάμε;

Άγνωστο προς το παρόν το μεγαλύτερο αρχείο είναι γύρω στα 50+Kb

[defacer]

2 hours ago, masteripper said:

Άγνωστο προς το παρόν το μεγαλύτερο αρχείο είναι γύρω στα 50+Kb

Οπότε ψιλοτίποτα, προχώρα έτσι σε πρώτη φάση.