Αλγόριθμος με strings

[Lanike71]

Τη βοήθεια σας παιδιά,

 

Έστω πίνακας strings ίδιου μήκους, πχ αββ,αβγ,βγδ,βγγ.Ψάχνουμε τον ελάχιστο αριθμό ομάδων με κοινούς χαρακτήρες στις ίδιες θέσεις όμως τουλάχιστον n-1.Εδώ, θέλω τις ομάδες να έχουν τουλ. 2 χαρακτήρες ίδιους.Με το μάτι γρήγορα βλέπω 2 ομάδες,αββ-αβγ και βγδ-βγγ.

Με το μάτι καλά είναι, όταν οι πίνακες είναι χιλιάδες strings τι γίνεται;

Ανήκει αυτό το πρόβλημα σε κάποιο γνωστό πρόβλημα της πληροφορικής;

[gon1332]

Δηλαδή θες όλες τις ομάδες που έχουν τουλάχιστον n-1 (όπου n το μέγεθος των strings μέσα στον πίνακα φαντάζομαι) ίδιους χαρακτήρες; Δε μπορώ να καταλάβω τί σημαίνει το ελάχιστο σε αυτό το πρόβλημα. Αν δηλαδή το παράδειγμα που έδωσες είχε και strings με 3 κοινούς χαρακτήρες θα τη δεχόμασταν την ομάδα στο τελικό αποτέλεσμα; Ή θα παίρναμε μόνο αυτές με 2 κοινούς χαρακτήρες; Αν δε βρίσκαμε ας πούμε ομάδες των 2, δε θα βρίσκαμε και ομάδες των 3.

 

Δοκίμασες να το προγραμματίσεις αρχικά παίρνοντας όλους τους συνδυασμούς (μεταξύ strings) εξετάζοντας n-1 χαρακτήρες τη φορά; Βέβαια δε θα εξετάζεις ζευγάρια που ήδη έχεις εξετάσει. Επίσης αν αποτύχει ο έλεγχος για n-1 χαρακτήρες, τότε δε θα πετύχε για παραπάνω από n-1.

 

 

EDIT: Η περίπτωση ένα string να ταιριάζει με ένα άλλο στους 2 χαρακτήρες και με ένα άλλο στου 3, αλλά όχι τα άλλα μεταξύ τους, πχ αβγ, αβγ, εβγ πως πρέπει να τη διαχειριστείς; Θα φτιάξεις δύο διαφορετικές ομάδες: {αβγ, αβγ}3, {αβγ, αβγ, εβγ}2;

Επεξ/σία 12 Οκτωβρίου 2015 από gon1332

[tr3quart1sta]

https://en.wikipedia.org/wiki/Edit_distance

[gon1332]

Ο αλγόριθμος για edit distance θα μπορούσε να χρησιμοποιηθεί ανάποδα φαντάζομαι. Δηλαδή, να βρεθούν οι ομάδες των οποίων τα strings έχουν edit distance το πολύ 1 (n - (n-1)).

[Lanike71]

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

 

Ζητήθηκε αλγόριθμος από γνωστό μου με είσοδο πίνακα Α με strings ίδιου μήκους n.Η έξοδος θα είναι ένα (υπάρχουν πολλά πιστεύω) ελάχιστο υποσύνολο αυτού του πίνακα το οποίο θα έχει την εξής ιδιότητα : Αν s τυχαίο string που να ανήκει στον πίνακα Α, τότε αυτό το s έχει τουλάχιστον n-1 κοινά στοιχεία με κάποιο από τα στοιχεία του ελαχίστου υποσυνόλου.

Η λύση που δούλεψα : σκέφτηκα ότι κάθε στοιχείο του υποσυνόλου θα πρέπει να έχει αυτήν την ιδιότητα, δηλ να έχει τουλάχιστον n-1 κοινά στοιχεία.Οπότε πήρα το πρώτο string του πίνακα και έφτιαξα την ομάδα του με n-1 κοινά.

Αφαίρεσα όλα τα στοιχεία από τον πίνακα (τον αντιπρόσωπο και την ομάδα 1) και συνέχισα στο επόμενο τυχαίο στοιχείο,δημιουργήθηκε η επόμενη ομάδα  κλπ μέχρι που δημιουργήθηκε το ελάχιστο υποσύνολο που ζητείται.Σε δοκιμές με το χέρι (μάτι), δείχνει ότι είναι σωστός ως αλγόριθμος.

Το θέμα είναι πώς μπορώ να αποδείξω ότι είναι το ελάχιστο όταν έχω κάποιες χιλιάδες strings;

[albNik]

Ελάχιστο υποσύνολο με τις ιδιότητες που ζητάς κανει μονο το ζευγάρι. Π.χ. αν βρήκες τριαδα πετας το ενα και πάλι ισχύουν οι ιδιότητες.

Μήπως ζηταει να βρεις μέγιστο υποσυνολο; 

 

*Οκ το ιδιο ρωταει και ο gon1332

[Lanike71]

Πίνακας Α = {ΑΑΑ,ΑΑΒ,ΑΒΑ,ΒΑΑ,ΒΒΑ,ΒΑΒ,ΑΒΒ,ΒΒΒ}

 

Ελάχιστο υποσύνολο που να έχει τουλάχιστον n-1 κοινά με τυχαίο στοιχείο του Α είναι το {ΑΑΑ,ΒΒΒ}.Δυστυχώς απορρίφθηκε ο αλγόριθμος γιατί τρέχοντάς τον θα έβγαζε μεγαλύτερο υποσύνολο.Οπότε μάλον θα πρέπει να εξετάζονται κάποια κριτήρια πριν επιλεγεί το υποψήφιο στοιχείο για να μπει στο ελάχιστο υποσύνολο.

[Lanike71]

Επίσης στο παραπάνω παράδειγμα μου ελάχιστο υποσύνολο μπορεί να είναι και το {ΑΑΒ,ΒΒΑ}.Γι' αυτό είπα ότι υπάρχουν πολλά υποσύνολα που είναι ελάχιστα.

Νομίζω ότι με κάποιες τροποποιήσεις του edit distance μάλλον θα βρω άκρη.

 

*Αν έχει κάποιος ιδέες, ας τις ρίξει.Δεν πρόκειται για εργασία σχολής...

[defacer]

Όταν λες κοινά στοιχεία εννοείς και στις ίδιες θέσεις; In other words το ΑΒΓ και το ΒΓΑ πόσα κοινά έχουν;

[groot]

Εάν θέλεις n-X για την ισότητα (στο δικό σου παράδειγμα είχες X = 1), τότε εάν κάνεις sort τα strings (υπάρχουν πολλοί τρόποι... ) και κοιτάς στο n-X θέση σε όλα τα strings μέχρι να βρεις διαφορετικό χαρακτήρα; 

[Lanike71]

Όταν λες κοινά στοιχεία εννοείς και στις ίδιες θέσεις; In other words το ΑΒΓ και το ΒΓΑ πόσα κοινά έχουν;

 

Κανένα.Ναι αυτό εννοώ.

[groot]

Και το sort μπορεί να γίνει μία φορά... μετά αποθηκεύεις sorted το dataset σου και απλά ψάχνεις. 

[Lanike71]

Εάν θέλεις n-X για την ισότητα (στο δικό σου παράδειγμα είχες X = 1), τότε εάν κάνεις sort τα strings (υπάρχουν πολλοί τρόποι... ) και κοιτάς στο n-X θέση σε όλα τα strings μέχρι να βρεις διαφορετικό χαρακτήρα; 

 

Το δύσκολο είναι να βρεις το ελάχιστο υποσύνολο.Πχ στον πίνακα που έφερα ως παράδειγμα, έστω διαπερνάω τον πίνακα

Α = {ΑΑΑ,ΑΑΒ,ΑΒΑ,ΒΑΑ,ΒΒΑ,ΒΑΒ,ΑΒΒ,ΒΒΒ} .Επιλέγω το ΑΑΑ και αρχίζω συγκρίσεις, πχ ΑΑΑ με 2ο στοιχείο, ΟΚ είναι n-1, ΑΑΑ με 3ο στοιχείο ΟΚ, είναι n-1 όπως και με το 4 και στοπ.Οπότε μία ομάδα με "αντιπρόσωπο" το ΑΑΑ.Επόμενο που επιλέγεται είναι το 5 (ΒΒΑ) και έχει κοινά μόνο με το ΒΒΒ, άρα ομάδα {ΒΒΑ,ΒΒΒ) και απομένουν άλλα 2 (ΒΑΒ,ΑΒΒ) που δε γίνονται ομάδα, άρα το καθένα ειναι ομάδα από μόνο του.Οπότε 4 ομάδες και υποσύνολο το (ΑΑΑ,ΒΒΑ,ΒΑΒ,ΑΒΒ).Δεν είναι όμως το ελάχιστο, καθώς υπάρχει το (ΑΑΑ,ΒΒΒ).Οπότε απλή διαπέραση δε "δουλεύει".  

[groot]

Αδερφέ... κάτι χάνεις ή κάτι χάνω.. help me please  

 

Εάν λέμε για το ελάχιστο υποσύνολο, τότε αρκεί να βρεις ένα. Π.χ. το (ΑΑΑ). Είναι το ελάχιστο. Τελείωσε. 

 

 

Από εκεί και πέρα, εγώ αυτό που είπα είναι:

 

Στο Α = {ΑΑΑ,ΑΑΒ,ΑΒΑ,ΒΑΑ,ΒΒΑ,ΒΑΒ,ΑΒΒ,ΒΒΒ}, παίρνεις το 2ο στοιχείο από το πρώτο string και συγκρίνεις μόνο αυτό με τα άλλα 2α στοιχεία από τα άλλα strings. 

 

Εφόσον είναι sorted, τότε για όσα αρχικά γράμματα έχεις μία καταχώρηση είσαι σίγουρος ότι δεν ανήκουν στο ελάχιστο υποσύνολο. 

Για την ακρίβεια, για το ελάχιστο υποσύνολο και σε sorted strings θα έψαχνα πρώτα σε όσα strings αρχίζουν από το ίδιο γράμμα και για το γράμμα αυτό υπάρχουν τουλάχιστον (n-X) +1 entries. 

[Lanike71]

Αδερφέ... κάτι χάνεις ή κάτι χάνω.. help me please

 

Εάν λέμε για το ελάχιστο υποσύνολο, τότε αρκεί να βρεις ένα. Π.χ. το (ΑΑΑ). Είναι το ελάχιστο. Τελείωσε. 

 

 

Από εκεί και πέρα, εγώ αυτό που είπα είναι:

 

Στο Α = {ΑΑΑ,ΑΑΒ,ΑΒΑ,ΒΑΑ,ΒΒΑ,ΒΑΒ,ΑΒΒ,ΒΒΒ}, παίρνεις το 2ο στοιχείο από το πρώτο string και συγκρίνεις μόνο αυτό με τα άλλα 2α στοιχεία από τα άλλα strings. 

 

Εφόσον είναι sorted, τότε για όσα αρχικά γράμματα έχεις μία καταχώρηση είσαι σίγουρος ότι δεν ανήκουν στο ελάχιστο υποσύνολο. 

Για την ακρίβεια, για το ελάχιστο υποσύνολο και σε sorted strings θα έψαχνα πρώτα σε όσα strings αρχίζουν από το ίδιο γράμμα και για το γράμμα αυτό υπάρχουν τουλάχιστον (n-X) +1 entries. 

 

Όχι δε σε καταλαβαίνω, να πω την αλήθεια.

 

Δηλ. λες ότι συγκρίνω τα πάντα με τα πάντα και κάνω sort ανάλογα με το πόσα n-1 έχει το καθένα;Και πώς ξέρω ποιά στοιχεία ικανοποιούν όλο τον πίνακα;

Κοίτα στο παράδειγμα : Το {ΑΑΑ,ΒΒΒ} κάνει την ίδια δουλειά με το {ΑΒΑ,ΒΑΒ} όπως και με το {ΑΑΒ,ΒΒΑ} όπως και με το {ΒΑΑ,ΑΒΒ}!!!Δηλαδή είναι όλα ελάχιστα υποσύνολα (ελάχιστο γιατί δε μπορεί να υπάρξει < 2) και ικανοποιούν την απαίτηση ΟΠΟΙΟΔΗΠΟΤΕ στοιχείο του Α να έχει τουλάχιστον n-1 ίδια στοιχεία στις ίδιες θέσεις).

Αν δε σου κάνει κόπο, κάνε ένα παράδειγμα να δω φως...