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

[groot]

Θέλεις όλα τα ελάχιστα υποσύνολα; Ή μόνο ένα από αυτά; Εάν είναι μόνο ένα, τότε όταν λες υποσύνολο; Γιατί το (ΑΑΑ) είναι το υποσύνολο των strings που έχουν την ιδιότητα που θέλεις. Ακόμα, από το σύνολο ΑΑΑ, θέλεις όλα τα strings ή έστω μόνο ένα; 

 

Τέλος στο παράδειγμα... εάν πάμε σε Java και έστω ότι έχεις ένα sorted ArrayList με String:

String initialString = "AAA";
for ( String templString : myStringList ) {
    if (initialString.charAt(1) == templString.charAt(1)) {
        // Add stirng to subset

αυτή είναι η λογική... από εκεί και πέρα, αναλόγως τι θες μπορεί να αλλάξει. Π.χ., το απλό παράδειγμα είναι error prone στην περίπτωση που έχεις (ΑΑΑΑ, ΑΑΒΑ, ΑΒΑΑ) και κοιτάς το n-1. Αλλά και αυτό μπορείς να το κοιτάξεις.. το σίγουρο είναι πως εάν είναι sorted επιταχύνεις τα πράματα πολύ. 

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

 

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

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

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

 

 

Επίσης, αδερφέ... δεν το εξηγείς καλά. 

 

Λες: 

 

ικανοποιούν την απαίτηση ΟΠΟΙΟΔΗΠΟΤΕ στοιχείο του Α να έχει τουλάχιστον n-1 ίδια 

 

 

Το Α τι είναι; Το σύνολο; Το υποσύνολο; Ποιο από τα υποσύνολα; Των strings που έχουν ίδια n-1 στοιχεία; Των strings που είναι τα base για τις συγκρίσεις των n-1; Τι ;

 

 

Ίσως εάν δώσεις μία καλή και πλήρη περιγραφή να πάρεις βοήθεια και από αλλού

[Lanike71]

Θέλεις όλα τα ελάχιστα υποσύνολα; Ή μόνο ένα από αυτά; Εάν είναι μόνο ένα, τότε όταν λες υποσύνολο; Γιατί το (ΑΑΑ) είναι το υποσύνολο των strings που έχουν την ιδιότητα που θέλεις. Ακόμα, από το σύνολο ΑΑΑ, θέλεις όλα τα strings ή έστω μόνο ένα; 

 

Τέλος στο παράδειγμα... εάν πάμε σε Java και έστω ότι έχεις ένα sorted ArrayList με String:

String initialString = "AAA";
for ( String templString : myStringList ) {
    if (initialString.charAt(1) == templString.charAt(1)) {
        // Add stirng to subset

αυτή είναι η λογική... από εκεί και πέρα, αναλόγως τι θες μπορεί να αλλάξει. Π.χ., το απλό παράδειγμα είναι error prone στην περίπτωση που έχεις (ΑΑΑΑ, ΑΑΒΑ, ΑΒΑΑ) και κοιτάς το n-1. Αλλά και αυτό μπορείς να το κοιτάξεις.. το σίγουρο είναι πως εάν είναι sorted επιταχύνεις τα πράματα πολύ. 

 

 

Επίσης, αδερφέ... δεν το εξηγείς καλά. 

 

Λες: 

 

ικανοποιούν την απαίτηση ΟΠΟΙΟΔΗΠΟΤΕ στοιχείο του Α να έχει τουλάχιστον n-1 ίδια 

 

 

Το Α τι είναι; Το σύνολο; Το υποσύνολο; Ποιο από τα υποσύνολα; Των strings που έχουν ίδια n-1 στοιχεία; Των strings που είναι τα base για τις συγκρίσεις των n-1; Τι ;

 

 

Ίσως εάν δώσεις μία καλή και πλήρη περιγραφή να πάρεις βοήθεια και από αλλού

 

Ένα ελάχιστο υποσύνολο αρκεί.

Δες το ποστ 7 : Α είναι ο πίνακας λέξεων, strings, όπως θες πες το.

 

Πιο απλά δε γίνεται αλλά το ξαναλέω:

 

Έχω πίνακα Α.Θα πρέπει να επιλέξω όσο πιο λίγα στοιχεία γίνεται από αυτό, τα οποία θα σχηματίσουν ένα υποσύνολο, ας πουμε S.

Σε οποιαδήποτε τυχαία επιλογή κάποιου στοιχείου από τον Α, θα πρέπει να υπάρχει ένα στοιχείο στον S που συγκρινόμενα να έχουν τουλάχιστον n-1 κοινά στοιχεία στις ίδιες θέσεις.Πάμε παράδειγμα:

 

A = {AAA,AAB,ABA,BAA,BBA,BAB,ABB,BBB}

S = {AAA,BBB}.

 

Τυχαία παίρνω το ΒΑΑ.Έχει 2 κοινά με το ΑΑΑ στις θέσεις 2,3.

Επίσης : ΒΒΑ, έχει 2 κοινά με το ΒΒΒ στις θέσεις 1,2.

 

Μπορώ να έχω μικρότερο S ; Όχι δε μπορώ, γιατί θα υπάρχει στοιχείο του Α που θα έχει n-2 κοινά, άρα απορρίπτεται.

 

Σε ευχαριστώ για το χρόνο σου φίλε.

[Lanike71]

Έφτιαξα ένα πίνακα που δείχνει όλους τους συνδυασμούς και το πόσα κοινά έχουν.

 

 

Εύκολα βλέπουμε ότι ανά row, μας ενδιαφέρουν τα κελιά με >=2 τιμές.Στόχος πρέπει να είναι να συνδυάσουμε οριζόντια τόσες λέξεις ώστε να καλύψουν το σύνολο των λέξεων, εδώ 8.

Ας πάρουμε τυχαία τη λέξη ΑΑΒ. Βλέπουμε ότι έχει τιμές >=2 στις κολώνες 1,2,7,8.Άρα ψάχνουμε λέξη ή λέξεις με τιμές >=2 στις κολώνες 3,4,5,6.Εύκολα βλέπουμε ότι είναι η λέξη ΒΒΑ.Άρα το υποσύνολο {ΑΑΒ,ΒΒΑ} είναι ένα ελάχιστο.

Δεν ξέρω τι κόστος έχουν αυτοί οι υπολογισμοί, πρώτα θες n^2 για τον πίνακα.Ψάχνω να βρω πώς να συνεχίσω.

[albNik]

Αρα θες τα ελάχιστα rows που αν τα συνδυασεις και κρατήσεις τα max θα εχεις τιμες>=2.

Δλδ στο Max(row3 , row7) ειναι ολα >=2. 

 

Η εισοδος θα εχει μονο Α και Β?

Αν ειναι π.χ. μηκους 5 θα υπαρχουν όλοι οι 32 συνδυασμοί (ΑΑΑΒΒ, ΑΒΑΒΑ, κλπ)?

[Lanike71]

 

 

 

Αρα θες τα ελάχιστα rows που αν τα συνδυασεις και κρατήσεις τα max θα εχεις τιμες>=2.

Δλδ στο Max(row3 , row7) ειναι ολα >=2. 

 

Η εισοδος θα εχει μονο Α και Β?

Αν ειναι π.χ. μηκους 5 θα υπαρχουν όλοι οι 32 συνδυασμοί (ΑΑΑΒΒ, ΑΒΑΒΑ, κλπ)?

 

Όχι albnik.

Ο πίνακας μπορεί να περιέχει οτιδήποτε.Το μόνο στάνταρ είναι ότι ο πίνακας θα έχει λέξεις συγκεκριμένου μήκους (ίδιο για όλες) και οι λέξεις είναι μοναδικές.

 

[albNik]

Οκ

Φτιαξε τον πίνακα σου πρώτα

Βάλε 0 σε οσα κελια που ειναι <2 και 1 σε οσα ειναι >=2  (αντι για 2 βαζεις n-1)

Θες τα ελάχιστα rows που αν τα προσθέσεις (binary OR 1+1=1) θα εχεις τελικο row με όλα 1.

[Lanike71]

 

Οκ

Φτιαξε τον πίνακα σου πρώτα

Βάλε 0 σε οσα κελια που ειναι <2 και 1 σε οσα ειναι >=2  (αντι για 2 βαζεις n-1)

Θες τα ελάχιστα rows που αν τα προσθέσεις (binary OR 1+1=1) θα εχεις τελικο row με όλα 1.

 

 

Επειδή είναι τεράστιος ο αριθμός συνδυασμών, μπορείς να δώσεις κανένα hint για τη συνέχεια;

 

Άπληστος ίσως;Έχω και καιρό να ασχοληθώ...

[albNik]

Δυστυχώς μεταφράζεται στο minimum set cover το οποιο είναι NP-complete.

 

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

 

the set cover problem is to identify the smallest subset of  whose union equals the universe

Εσυ θες το ελάχιστο σύνολο από rows. 

[Lanike71]

 

 

 

Δυστυχώς μεταφράζεται στο minimum set cover το οποιο είναι NP-complete.

 

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

 

Εσυ θες το ελάχιστο σύνολο από rows. 

 

Το φαντάστηκα...Μου θύμισε το subset sum και το έψαχνα μόλις τώρα...

 

Μάλλον θα πάω με άπληστο, θα βρίσκει λύση αλλά δε θα είναι η βέλτιστη.Θα το τρέχω 5-6 φορές και θα επιλέγω το καλύτερο.

Ευχαριστώ για τις βοήθειες όλους.

[albNik]

Επελεξες τα row3=[1,2,7,8] και row7=[3,4,5,6] που μας κανουν [1,2,3,4,5,6,7,8]

Δεν ξερω αν ετυχε τα row3 και row7 να μην εχουν κοινα στοιχεία ή ετσι πρέπει

 

Αν ετσι πρεπει τοτε ειναι το "Exact cover problem" παλι NP-complete. 

Ενας σχετικά γρηγορος αλγόριθμος για exact cover ειναι ο παρακάτω

https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

[Lanike71]

 

 

 

Επελεξες τα row3=[1,2,7,8] και row7=[3,4,5,6] που μας κανουν [1,2,3,4,5,6,7,8]

Δεν ξερω αν ετυχε τα row3 και row7 να μην εχουν κοινα στοιχεία ή ετσι πρέπει

 

Αν ετσι πρεπει τοτε ειναι το "Exact cover problem" παλι NP-complete. 

Ενας σχετικά γρηγορος αλγόριθμος για exact cover ειναι ο παρακάτω

https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

 

Όχι, έτσι έτυχε.Θα μπορούσε να έχουν επικαλυπτόμενα κελιά, δηλ. να έχουν στην ίδια κολώνα 2άρι ή 3άρι.

Αν το δοκιμάσεις με 2 θέσεις και 3 χαρακτήρες ανά θέση, πχ λέξεις ΑΒ,BC,CC,BB κλπ οι συνδυασμοί είναι 81 (αφού οι λέξεις είναι 9).Ελάχιστο υποσύνολο είναι με 3 λέξεις (ένα από αυτά είναι το ΑΑ,ΒΒ,CC) και πολλά κελιά επικαλύπτονται.

[albNik]

Μαλιστα.

Δεν ξερω κατα πόσο βοηθάει το οτι ο πινακας ειναι συμμετρικός (δλδ τα subsets δεν ειναι εντελώς τυχαία). 

Ισως να υπάρχει αποδοτικος τρόπος.