Άσκηση με Αντιμεταθέσεις

[evry]

Δίνεται ένας πίνακας με λογικές τιμές (Αληθής/Ψευδής) Ν θέσεων.

Να γράψετε αλγόριθμο ο οποίος να τοποθετεί όλες τις  Αληθείς πριν από τις Ψευδείς. Για παράδειγμα αν δοθεί ο παρακάτω πίνακας

  Ψευδής   Αληθής   Ψευδής   Ψευδής   Αληθής   Αληθής
     1             2             3             4             5            6

ο τελικός πίνακας θα είναι ο παρακάτω

  Αληθής   Αληθής   Αληθής   Ψευδής   Ψευδής   Ψευδής
     1             2             3            4             5            6

α) τρόπος (με διπλή επανάληψη)
β) τρόπος (με δύο σαρώσεις αλλά ουσιαστικά ξεφτιλίζει τη δυσκολία του προβλήματος)

γ) τρόπος που μας ενδιαφέρει με τους εξής περιορισμούς
     1. Θα σαρώσετε τα στοιχεία του πίνακα μόνο μια φορά. Υπόδειξη: Χρησιμοποιήστε την Αντιμετάθεσε
        (Δηλαδή εδώ ούτε δύο σαρώσεις μπορείτε να κάνετε, ούτε διπλή επανάληψη κάπου)

ΥΓ. Σε τέτοια προβλήματα η χρήση επιπλέον δομών δεδομένων πρέπει να είναι η τελευταία μας λύση. Φυσικά εδώ απαγορεύεται

[Πανάγος94]

έστω Α[Ν] ο πίνακας, και αφού θεωρείται δεδομένος θα γράψω μόνο το κομμάτι που ζητείται

πλ <- 0 ! πλήθος αντιμεταθέσεων
Για ι από 2 μέχρι Ν
Αν Α[ι] = Αληθής τότε
πλ <- πλ + 1
Αντιμετάθεσε Α[ι],Α[πλ]
τέλος_αν
Τέλος_επανάληψης

δεν ξέρω αν είναι ο πιο αποτελεσματικός τρόπος αλλά δουλεύει...άμα βρείτε κανένα λάθος ειδοποιήστε!!

[evry]

Βασικά δεν μπορώ να καταλάβω τι θέλεις να κάνεις. Το εξηγείς λίγο?

έστω Α[Ν] ο πίνακας, και αφού θεωρείται δεδομένος θα γράψω μόνο το κομμάτι που ζητείται

πλ <- 0 ! πλήθος αντιμεταθέσεων
Για ι από 2 μέχρι Ν
Αν Α[ι] = Αληθής τότε
πλ <- πλ + 1
Αντιμετάθεσε Α[ι],Α[πλ]
τέλος_αν
Τέλος_επανάληψης

δεν ξέρω αν είναι ο πιο αποτελεσματικός τρόπος αλλά δουλεύει...άμα βρείτε κανένα λάθος ειδοποιήστε!!

edit:
οκ, νομίζω ότι κατάλαβα τι πας να κάνεις, αλλά για τρέξτο για τον παρακάτω πίνακα

Α[1] ←  Αληθής
Α[2] ←  Αληθής
Α[3] ←  Αληθής
Α[4] ←  Ψευδής
Α[5] ←  Αληθής
Α[6] ←  Ψευδής

Ωστόσο η λύση σου μπορώ να πω ότι είναι πολύ έξυπνη.
Μια μικρή υπόδειξη όμως μια και το έφτασες ως εδώ. Για να κάνεις αντιμετάθεση σε 2 στοιχεία θα πρέπει να εξασφαλίσεις ότι και τα 2 είναι σε λάθος θέση.
Δηλαδή αν δεν κάνεις περιττές αντιμεταθέσεις τότε εξασφαλίζεις και την ορθότητα του αλγορίθμου σου.
Χωρίς αυτό να σημαίνει ότι δεν γίνεται αλλιώς.

[Stavros]

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

l<-1
	r<-N
	while(l<r){
		if(table[l]=false AND table[r]=true){
			antimetathese(table[l],table[r])
		}
		else if(table[l]=true AND table[r]=true){
			l=l+1
			while(table[l]=true AND l<r)
				l=l+1
                       if(l<r)
			        antimetathese(table[l], table[r])
		}else if(table[l]=false AND table[r]=false){
			r=r-1
			while(table[r]=false AND l<r)
				r=r-1
			if(l<r)
			       antimetasthese(table[l],table[r])
		}
		l<-l+1
		r<-r-1
	}

[evry]

Βασικά μια τέτοια λύση περίμενα για το γ) αλλά ο Πανάγος με κούφανε

Δηλαδή δύο δείκτες οι οποίοι κάθε φορά έχουν σαν στόχο να βρουν δύο στοιχεία που είναι σε λάθος θέση ώστε με μια αντιμετάθεση να βρεθούν και τα 2 εκεί που πρέπει.
Για δες λίγο μήπως μπορείς να απαλείψεις τις επαναλήψεις που έχεις μέσα στο if.
Δεν χρειάζονται. Σκέψου ότι κάθε φορά που ο δείκτης (ή ο πάνω ή ο κάτω) βρίσκει ένα στοιχείο στην σωστή θέση απλά προχωράει μια θέση πιο κάτω. Δεν νομίζω να χρειάζεται επανάληψη.
Φυσικά το ότι έχει διπλή επανάληψη δεν σημαίνει ότι η πολυπλοκότητα του αλγορίθμου (απόδοση) αλλάζει. Η ίδια είναι αφού οι ίδιες συγκρίσεις θα γίνουν πάνω κάτω.

Επίσης γιατί αντιμεταθέτεις και στην περίπτωση που είναι ίδια? (Αληθής,Αληθής και Ψευδής,Ψευδής)

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

l<-1
	r<-N
	while(l<r){
		if(table[l]=false AND table[r]=true){
			antimetathese(table[l],table[r])
		}
		else if(table[l]=true AND table[r]=true){
			l=l+1
			while(table[l]=true AND l<r)
				l=l+1
                       if(l<r)
			        antimetathese(table[l], table[r])
		}else if(table[l]=false AND table[r]=false){
			r=r-1
			while(table[r]=false AND l<r)
				r=r-1
			if(l<r)
			       antimetasthese(table[l],table[r])
		}
		l<-l+1
		r<-r-1
	}

[Πανάγος94]

έτσι το εννούσες??

θ ← 0
Για ι από 1 μέχρι Ν
  Αν α[ι] = Ψευδής τότε
    Αν θ = 0 τότε θ ← ι
  αλλιώς
    Αν θ > 0 τότε
      Αντιμετάθεσε α[ι], α[θ]
      θ ← ι
    Τέλος_αν
  Τέλος_αν
Τέλος_επανάληψης

[Stavros]

Βασικά μια τέτοια λύση περίμενα για το γ) αλλά ο Πανάγος με κούφανε

Δηλαδή δύο δείκτες οι οποίοι κάθε φορά έχουν σαν στόχο να βρουν δύο στοιχεία που είναι σε λάθος θέση ώστε με μια αντιμετάθεση να βρεθούν και τα 2 εκεί που πρέπει.
Για δες λίγο μήπως μπορείς να απαλείψεις τις επαναλήψεις που έχεις μέσα στο if.
Δεν χρειάζονται. Σκέψου ότι κάθε φορά που ο δείκτης (ή ο πάνω ή ο κάτω) βρίσκει ένα στοιχείο στην σωστή θέση απλά προχωράει μια θέση πιο κάτω. Δεν νομίζω να χρειάζεται επανάληψη.
Φυσικά το ότι έχει διπλή επανάληψη δεν σημαίνει ότι η πολυπλοκότητα του αλγορίθμου (απόδοση) αλλάζει. Η ίδια είναι αφού οι ίδιες συγκρίσεις θα γίνουν πάνω κάτω.

Επίσης γιατί αντιμεταθέτεις και στην περίπτωση που είναι ίδια? (Αληθής,Αληθής και Ψευδής,Ψευδής)

Μάλλον δεν καταλάβατε ακριβώς τι κάνω, τουλάχιστον αυτό υποδηλώνει η τελευταία ερώτηση...
Θα το πω περιγραφικά λοιπόν. Αρχικά να σημειώσω πως όντως η εμφωλευμένη επανάληψη θα μπρούσε να αποφευκτεί αλλα θα ήθελα κάθε φορα που θα που θα πηγαίνει στο αρχικό while να έχει να ελένξει 2 τελείως διαφορετικά στοιχεια από την προηγουμενη φορα...

Όταν 2 στοιχεια είναι ίδια δεν τα αντιμεταθέτω. Σε αυτό το while p.x.

else if(table[l]=true AND table[r]=true){
      l=l+1
     while(table[l]=true AND l<r)
     l=l+1

Όταν ελέγξω ότι δυο στοιχεια είναι ίδια ψάχνω να βρω αν υπάρχει το επόμενο στοιχειο που είναι ψευδές από τον δείκτη l, και τότε να τα αντιμεταθέσω.

θ ← 0
Για ι από 1 μέχρι Ν
  Αν α[ι] = Ψευδής τότε
    Αν θ = 0 τότε θ ← ι
  αλλιώς
    Αν θ > 0 τότε
      Αντιμετάθεσε α[ι], α[θ]
      θ ← ι
    Τέλος_αν
  Τέλος_αν
Τέλος_επανάληψης

Ωραίος αλγόριθμος αλλα νομίζω πως χρειάζεται μερικές λίγες διορθώσεις για να γίνει καλύτερος... Λίγη προσπάθεια ακόμη και θα είναι έτοιμος.
Η μονη παρατήρηση εδώ (δεν ξέρω αν υπάρχουν κι άλλες) είναι πως, ok κανεις ένα πέρασμα αλλα επίσης κανεις και παρα πολλές αντιμεταθέσεις. p.x.
Αν έχεις πινακα 1000000000 (1 dis) με το πρώτο στοιχειο ψευδές και όλα τα αλλα αληθή τότε θα κανεις 1000000000-1 αντιμεταθέσεις ενώ θα μπορούσε να γίνει με 1 μόλις αντιμετάθεση.

[evry]

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

[Stavros]

Ναι ok, είπα ότι κατά κάποιον τρόπο είναι περίρα τα 2a while, απλά δεν χάνουμε σε χρόνο (για να μην πω πως κερδίζουμε λίγο) απλά χάνουμε ας πούμε τη <<συνεχεια>> του αλγοριθμου. Εν πάση περίπτωση την ιδέα του αλγοριθμου εξετάζουμε, και πιστεύω πως λέμε ακριβώς το ίδιο. Απλά εδώ σε εμενα αυτό είναι πιο κατανοητό.

[alkisg]

και πάλι όμως δεν υπάρχει λόγος για τις εσωτερικές επαναλήψεις.

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

Αδοκίμαστα:

Κώδικας: shell

ι=1
κ=Ν
Όσο ι < κ επανάλαβε
    Αν Α[ι] = Ψευδής τότε
        ι <- ι + 1
    αλλιώς_αν Α[κ] = Αληθής τότε
        κ <- κ - 1
    αλλιώς
        Αντιμετάθεσε Α[ι], Α[κ]
        ι <- ι + 1
        κ <- κ - 1
    τέλος_αν
τέλος_επανάληψης

Κώδικας: shell

ι=1
κ=Ν
Όσο ι < κ επανάλαβε
    Όσο Α[ι] = Ψευδής επανάλαβε
        ι <- ι + 1
    τέλος_επανάληψης
    Όσο (προαιρετικά: ι < κ και) Α[κ] = Αληθής επανάλαβε
        κ <- κ - 1
    τέλος_επανάληψης
    Αν ι < κ τότε
        Αντιμετάθεσε Α[ι], Α[κ]
    τέλος_επανάληψης
τέλος_επανάληψης

...προτιμώ τη δεύτερη εκδοχή, που ελαχιστοποιεί τις φορές που το ίδιο στοιχείο του πίνακα διαβάζεται παραπάνω από μία φορά, χωρίς να βάζει την πολυπλοκότητα του caching.

[evry]

Όταν έθεσα την άσκηση είχα στο μυαλό μου την 1η λύση που είναι αρκετά απλή και θυμίζει και λίγο συγχώνευση.
Ουσιαστικά η 2η που δίνεις είναι μια βελτιστοποιημένη εκδοχή της 1ης όπως λες.
Όταν έβαζα τον περιορισμό της μιας σάρωσης ο σκοπός μου ήταν να αποτρέψω την διπλή επανάληψη, δηλαδή το O(n^2).
Για να μην πω εξαρχής O(n^2) που οι μαθητές δεν ξέρουν τι είναι, προτίμησα αυτή τη διατύπωση.