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

[masteripper]

Γεια χαρά,

Θέλω να φτιάξω μια ρουτίνα που θα εξετάζει μια ακολουθια αριθμών και θα βρίσκει αν αποτελείται απο την επανάληψη μιας υποακολουθίας...

π.χ :
123123123123 ...επανάληψη του 123

12441232124412321244123212441232 επανάληψη του 12441232

Δεν γνωρίζουμε ούτε πόσο μήκος θα έχει η ακολουθία ούτε τίποτε άλλο...

εαν μπορεί να βρεί ακόμα και αν δεν έχει την πλήρη υποακολουθία στην αρχή και στο τέλος ακόμα καλύτερα π.χ.

232124412321244123212441232124412321244

Το ψάχνω στο Internet αλλά δεν μου "πετυχαίνει" ακριβώς η περιγραφή για να το βρώ..

[Lanike71]

To 123123123123 είναι επανάληψη του 123 αλλά και του 123123.

Αν θυμάμαι καλά υπάρχει σε δυναμικό προγραμματισμό η μέγιστη κοινή υπακολουθία (longest common subsequence). Δες μήπως και πετύχεις κάτι.

Τι ακριβώς θες να κάνεις, αν επιτρέπεται;

[marios28]

 Δες εδώ: https://stackoverflow.com/questions/26549373/how-to-detect-if-a-repeating-pattern-exists  

Το πρώτο θα σε βολέψει (με τα arrays) νομίζω (από μια ματιά που έριξα). Αν όχι κοίταξε και το επόμενο.

 https://codereview.stackexchange.com/questions/1753/searching-a-sequence-for-a-pattern

[masteripper]

2 ώρες πριν, Lanike71 είπε

Τι ακριβώς θες να κάνεις, αν επιτρέπεται;

Θέλω να διαβάσω κάποια αρχεία απο βάσεις δεδομένων που ο Header έχει καταστραφεί...ενώ απ'βλέπω τα δεδομένα υπάρχουν...ουσιαστικά σκέφτομαι ότι αν βρώ την ακολουθία των πεδίων θα μπορούσα να βάλω κάποια generic (Field1,Field2...) και να τα διαβάσω

25 λεπτά πριν, marios28 είπε

 Δες εδώ: https://stackoverflow.com/questions/26549373/how-to-detect-if-a-repeating-pattern-exists  

Το πρώτο θα σε βολέψει (με τα arrays) νομίζω (από μια ματιά που έριξα). Αν όχι κοίταξε και το επόμενο.

 https://codereview.stackexchange.com/questions/1753/searching-a-sequence-for-a-pattern

Θα τα δώ

[Fortistis]

Νομίζω ότι είναι αυτό που είπε ο Lanike παραπάνω. 

Με ένα απλό search θα βρεις αρκετά και από computer science και από signal processing. 

[k33theod]

Δικό μου,😁

Μπορεί να βελτιωθεί λίγο για να βρίσκει pattern και όταν η τελευταία επανάληψη δεν είναι πλήρης.

 

>>> a="123123123123"
>>> def find_patern(a):
	i=1
	while i<len(a)//2:
		if len(a)%i==0:
			if a==a[:i]*int(len(a)/i):
				print(a[:i]+" is a pattern of "+a)
				return
		i+=1
	print("There is no substring pattern in a")

	
>>> find_patern(a)
123 is a pattern of 123123123123
>>> b='12441232124412321244123212441232'
>>> find_patern(b)
12441232 is a pattern of 12441232124412321244123212441232
>>> c='232124412321244123212441232124412321244'
>>> find_patern(c)
There is no substring pattern in a
>>> 

 

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

[bahamut_zero]

την υπακολουθια θες να την δινεις εσυ ή να την βρισκει , αν υπαρχει;

[masteripper]

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

Δικό μου,😁

Μπορεί να βελτιωθεί λίγο για να βρίσκει pattern και όταν η τελευταία επανάληψη δεν είναι πλήρης.

>>> a="123123123123"
>>> def find_patern(a):
	i=1
	while i<len(a)//2:
		if len(a)%i==0:
			if a==a[:i]*int(len(a)/i):
				print(a[:i]+" is a pattern of "+a)
				return
		i+=1
	print("There is no substring pattern in a")

	
>>> find_patern(a)
123 is a pattern of 123123123123
>>> b='12441232124412321244123212441232'
>>> find_patern(b)
12441232 is a pattern of 12441232124412321244123212441232
>>> c='232124412321244123212441232124412321244'
>>> find_patern(c)
There is no substring pattern in a
>>> 

Καλη ιδέα...βέβαια θέλει ζυγό αριθμό επαναλήψεων...

Μόλις τώρα, bahamut_zero είπε

την υπακολουθια θες να την δινεις εσυ ή να την βρισκει , αν υπαρχει;

Να την βρίσκει...

[k33theod]

3 λεπτά πριν, masteripper είπε

Καλη ιδέα...βέβαια θέλει ζυγό αριθμό επαναλήψεων...

 

Όχι

>>> d="123123123"
>>> find_patern(d)
123 is a pattern of 123123123
>>> 

 

[masteripper]

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

Όχι

>>> d="123123123"
>>> find_patern(d)
123 is a pattern of 123123123
>>> 

Μάλλον τότε θα κάνει την δουλειά.....όντως το να ελέγχεις αν η συγκεκριμένη σειρά είναι παραγωγή της υποσειράς δεν έχει περιορισμούς...καλή ιδέα..

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

[k33theod]

2 λεπτά πριν, masteripper είπε

Μάλλον τότε θα κάνει την δουλειά...

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

Άν και το μόνο δύσκολο σημείο είναι το a[:i]*n που νομίζω υποστηρίζει μονο η python

[bahamut_zero]

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

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

Άν και το μόνο δύσκολο σημείο είναι το a[:i]*n που νομίζω υποστηρίζει μονο η python

αν δεν σου ειναι κοπος, προσωπικα για εμενα θα ειχε αξια, να γραψεις σε 2-3 γραμμες το σκεπτικο σου.

[masteripper]

a[:i] Αν δεν κάνω λάθος είναι range...πιστεύω με substring να το προσεγγίσω...όντως καλή ιδέα..

[k33theod]

Ευχαρίστως

Το σκεπτικό είναι το εξής:

Η συνθήκη για να υπάρχει υποακολουθία β θα πρέπει το α να μπορεί να γραφεί σαν β+β+β+.. ν φορές, όπου ν το μήκος του α δια το μήκος του β. Αυτό με τη προυπόθεση ότι  το α είναι πλήρης και δε περισεύει κάτι.

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

μετά παίρνω τους 2 πρώτους , 3πρώτους,4 κλπ , μέχρι να ικανοποιήσω τη συνθήκη, Αυτό μέχρι μήκος α/2 δεν έχει νόημα πας παραπάνω, θα πρέπει να έχεις τουλάχιστον 2 επαναλήψεις αλιώς β=α.

 

12 ώρες πριν, masteripper είπε

a[:i] Αν δεν κάνω λάθος είναι range...πιστεύω με substring να το προσεγγίσω...όντως καλή ιδέα..

είναι το substring από την αρχή με μήκος i.Δηλαδή το a[:3] είναι η 3 πρώτοι χαρακτήρες

Το παραπάνω που έγραψα είναι ανακριβές και το διωρθώνω. Στην συγκεκριμένη περίπτωση τυχαίνει να είναι σωστό επειδή το a[:3] είναι στην ουσία το a[0:3] γενικά όμως ισχύει, a[α:β], α αρχικό index και συμπεριλαμβάνεται β τελικό index δεν συμπεριλαμβάνεται δηλαδή a[5:3] είναι πάντα κενό a[5:8] είναι a[5] εώς και a[7].

Αυτή η version λειτουργεί και όταν η τελευταία ακολουθία δεν είναι πλήρης. Δεν ξέρω αν το θες αυτό.

Δεν κοιτάμε δηλαδή όλο το α αλλά ως εκει που είναι ακέραιο πολλαπλάσσιο του μήκους του substring

def find_patern2(a):
	i=1
	while i<len(a)//2:
		lena=len(a)- len(a)% i
		if a[:lena]==a[:i]*int(len(a[:lena])/i):
			print(a[:i]+" is a pattern of "+a)
			return
		i+=1
	print("There is no substring pattern in a")
                      
>>> find_patern2(c)
23212441 is a pattern of 232124412321244123212441232124412321244

Το στέλνω τώρα και στους CLRS Introduction to algorithms μήκος και προλάβει και μπει στην 4 edition😁
Τόσα χρόνια και ακόμα να τη βγάλουν.

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

[Fortistis]

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

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