Εύρεση διατάξεων 2 ανά n με επανάλυψη

[eliascm21]

Έστω ότι έχω ένα διάνυσμα μήκους 4. Έστω ότι στις θέσεις του μπορεί να μπει μόνο 0 και 1. Θέλω να αποθηκεύσω σε πίνακα όλες τις πιθανές τετράδες που μπορούν να προκύψουν. Αυτές θα είναι 2^4 και μπορούν πχ να υπολογιστούν με το Loop (σε Matlab)

 

>
for i1=0:1
for i2=0:1
for i3=0:1
for i4=0:1
    A=[i1 i2 i3 i4];
end
end
end
end

 

Αν το διάνυσμα έχει μήκος 16 τι κάνουμε; 16 for loops; Και αν θέλουμε το μήκος του διανύσματος να μπαίνει σαν όρισμα στη συνάρτηση - δηλαδή δεν είναι γνωστό από πριν ;

Με λίγα λόγια ψάχνω τρόπο να καταγράψω όλες τις πιθανές διατάξεις των 0 και 1 ανά n με επανάληψη.

Μήπως υπάρχει τίποτα έτοιμο στην matlab;

Please help...

 

Ευχαριστώ

[bookysmell2004]

Γίνεται και με μία επανάληψη, ανεξάρτητα από την τιμή του n.

 

Βλέπεις, ουσιαστικά σχηματίζεις όλους τους τετραψήφιους δυαδικούς αριθμούς. Ξεκινώντας με τον [0 0 0 0] προσθέτεις σε κάθε επανάληψη τον αριθμό [0 0 0 1] μέχρι να φτάσεις στον [1 1 1 1].

 

>A = [0 0 0 0]
Όσο ο A δεν είναι [1 1 1 1]:
    A = A + [0 0 0 1]

 

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

 

Όπως βλέπεις το n μπορεί να περαστεί και σαν παράμετρος στη μέθοδο. Matlab δε γνωρίζω αν υπάρχει κάτι έτοιμο. Απλά δίνω μια γενική ιδέα συνδυαστικής καταμέτρησης.

[macabre_sunsets]

Λίγο "κάφρική" λύση, αλλά μπορείς να κάνεις μετατροπή ενος αριθμού στον αντίστοιχο binary μέσω της dec2bin. Άρα θα έχεις ένα κώδικα σαν τον ακόλουθο (δεν γνωρίζω matlab) :

 

>for i=0 to n
{
    a[i] = dec2bin(i);
}

 

Για τους αριθμούς που έχουν λιγότερα ψηφία (πχ/ το 2 είναι 10) μπορείς μέσω sprintf να το μετατρέψεις σε 0010 (αν θέλεις 4 ψηφία).

Μειονέκτημα, αν και δεν ξέρω κατα πόσο σε ενδιαφέρει, είναι πως το αποτέλεσμα της dec2bin είναι string, οπότε θα έχεις ένα string array στο τέλος.

[eliascm21]

Σας ευχαριστώ πολύ. Η λύση του bookysmell2004 νομίζω μου κάνει - για αυτό που ρώτησα - γιατί δεν θέλω strings.

Όμως τώρα μου προέκυψε ένα άλλο πρόβλημα. Το μέγεθος του διανύσματος είναι 32, οπότε όλες οι διατάξεις είναι 2^32=4294967296 οπότε μάλλον θα έχω πρόβλημα μνήμης να τα αποθηκεύσω όλα.

Για να μη τα αποθηκεύσω, πρέπει στο loop να περνάω τις διατάξεις ως εξής: Πρώτα όλες όσες έχουν ένα άσσο, μετά όσες έχουν 2, κτλ... Το παραπάνω Loop δυστυχώς δεν τις περνάει με αυτό τον τρόπο

 

---------- Προσθήκη στις 10:50 ---------- Προηγούμενο μήνυμα στις 08:08 ----------

 

Δηλαδή το πρόβλημα που έχω τώρα:

Θέλω μία συνάρτηση η οποία να δέχεται σαν παράμετρο το πλήθος των άσσων που θα έχει ο πίνακας διάστασης 32 (και την διάσταση του πίνακα να δέχεται σαν παράμετρο ακόμα καλύτερα) και να υπολογίζει όλους τους πιθανούς συνδυασμούς ( σε πλήθος θα είναι ν!/(κ!(ν-κ)!) όπου κ το πλήθος των άσσων και ν η διάσταση του πίνακα).

[macabre_sunsets]

Για ποιο λόγο φτιάχνεις αυτό το πρόγραμμα? Δηλαδή θα κάνεις "πάσα" τον πίνακα που φτιάχνεις σε κάποιο άλλο? Θα εκτελέσεις πράξεις στα στοιχεία του? Το ρωτάω αυτό γιατί χρησιμοποιώντας string θα χρειαστείς λιγότερη μνήμη λόγο του ότι 1 char = 1 byte, ενώ 1 int = 4 byte και για float και real πάνε ακόμα πιο πολύ.

[bookysmell2004]

Όπως και να αποθηκευτούν οι πίνακες θα υπάρχει πρόβλημα μνήμης. Και αυτό επειδή ακόμα και 4 byte να ήταν ο πίνακας 32 διαστάσεων (4 είναι ο ελάχιστος αριθμός για αποθήκευση 32bit αριθμού) χρειαζόμαστε 4 * 2^32 bytes μνήμη, δηλαδή τετραπλάσιο από το θεωρητικό όριο 32bit μηχανήματος.

 

Καταλαβαίνω ότι έχεις κάποια πράγματα στο μυαλό σου και δεν θες να τα παραβιάσεις, γι' αυτό σκέφτηκες και την ύπαρξη μιας νέας μεθόδου που θα επιστρέφει μόνο μέρος των συνολικών συνδυασμών. Οφείλω όμως να σε ενημερώσω ότι αν n=32 και k=16 θα επιστρέφονται 6 * 10^8 συνδυασμοί, δηλαδή το λιγότερο 2.4GB μνήμης (υποθέτοντας πάντα 4 byte ανά πίνακα).

 

Νομίζω ότι θα πρέπει να μας πεις τι θα τροφοδοτήσεις με αυτή τη μέθοδο. Τι κάνει το πρόγραμμα; Ίσως να υπάρχει άλλος τρόπος από την κατασκευή της μεθόδου που προτείνεις.

[eliascm21]

Είναι για μία εργασία γραμμικών κωδίκων. Βασικά αυτό που θέλω να κάνω είναι να βρω 2^16 στοιχεία του διανυσματικού χώρου Ζ_2^32, τα οποία να ικανοποιούν κάποιες συνθήκες (για όσους γνωρίζουν, θέλω να βρω τους αντιπροσώπους των συμπλόκων ως προς τον κώδικα μου).

 

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

 

Από την άλλη τα στοιχεία του χώρου, πρέπει να τα εξετάσω κατά συγκεκριμένη σειρά. Πρώτα αυτά που έχουν ένα άσσο (βάρος 1) μετά αυτά που έχουν 2 κτλ. Οπότε με αυτό τον τρόπο πρέπει να σαρώνω τις διατάξεις.

 

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

 

Ευτυχώς ανακάλυψα την συνάρτηση της matlab combnk που δεν υπολογίζει διατάξεις, αλλά συνδιασμούς. Με αυτή όμως την καλώ μία φορά και υπολογίζει (αποθηκεύοντας σε πίνακα δυστηχώς) όλους τους συνδυασμούς για να έχω πχ 2 άσσους, την ξανακαλώ μετά για 3 κτλ (διαγράφοντας τα προηγούμενα). Αποθηκεύω περιττά πράγματα, αλλά την δουλειά θα την κάνει νομίζω.

 

Τα έκανα όλα αυτά, αλλά το πρόγραμμα πάει αργααααααααά. Τρέχει από τις 4 και έχει υπολογίσει 30000 από τα 65000 στοιχεία που πρέπει να υπολογίσει. Και όσο προχωράει τόσο θα επιβραδύνει ...

 

Δεν καθυστερεί η combnk που υπολογίζει τις διατάξεις, όλα τα άλλα που κάνω εγώ μετά καθηστερούν. Είναι πολλοί οι πολλαπλασιασμοί..

 

Αν γνωρίζει κανείς για γραμμικούς κώδικες, θα με βοηθούσε μάλλον

Δείτε την τελευταία παράγραφο αυτού όσοι ξέρετε, αυτό θέλω να κάνω.

 

ps. 'Ασχετο και offtpic: Έχω τον i5 750 στα 2.66, με turbo on και 1 πυρήνα σε λειτουργία μου φτάνει στα 2,81. Δεν υποτίθεται ότι πρέπει να φτάσει στα 3,00Ghz;