Συνδυασμοι αριθμων με Java

[m@Raki37]

Γεια σας, πριν λιγες μερες ξεκινησα να μαθαινω Java. Θελω να φτιαξω ενα προγραμμα στο οποιο να υπαρχουν οι συνδιασμοι απο 85 αριθμων ανα 4, χωρις, αν ειναι δυνατον, να εμφανιζονται 2 φορες οιι αριθμοι

Για παραδειγμα (συνδιασμοι 9 αριθμων ανα 4)

1  2  3  4    
1  2  3  5    
1  2  3  6    
1  2  3  7    
1  2  3  8    
1  2  3  9    
1  2  4  5    
1  2  4  6    
1  2  4  7    
1  2  4  8    
1  2  4  9    
1  2  5  6    
1  2  5  7    
1  2  5  8    
1  2  5  9    
1  2  6  7    
1  2  6  8    
1  2  6  9    
1  2  7  8    
1  2  7  9    
1  2  8  9 

...
...
...

...
...
...
...
5  6  7  8    
5  6  7  9    
5  6  8  9    
5  7  8  9    
6  7  8  9

 

Ξερει κανεις πως μπορει να γινει αυτο? Εγω μεχρι τωρα το μονο που καταφερα ειναι να  βγαινουν ασχετοι συνδιασμοι και μαλιστα καποιοι αριθμοι εμφανιζονται 2 φορες.

[Bspus]

Καταρχην θα αλλαζα το προβλημα απο 85 αριθμους σε 85 συμβολα γιατι με βοηθαει στη σκεψη. Δεν παιζει ρολο να ειναι αριθμοι αφου δεν τους χρησιμοποιεις για πραξεις

 

Αν επιτρεψεις πολλαπλες εμφανισεις συμβολου στην τετραδα, εχεις συνολο 85^4 τετραδες, δηλαδη 52200625

Με μοναδικα συμβολα σε καθε τετραδα εχεις 85*84*83*82 δηλαδη 48594840. Δεν ειναι και πολυ μεγαλη διαφορα

 

Η πρωτη περιπτωση ειναι ευκολο να λυθει. Εχεις τα 85 συμβολα σε ενα array (μαλλον string, η αμα δεν σου αρεσει να το κανεις με συμβολα, καντο array με int)

 

Κανεις 4 for loops το ενα μεσα στο αλλο, το καθενα με διαφορετικο iterator φυσικα αλλα ολα απο 0 μεχρι 84 (για τα 85 μελη του array).

Στο τελευταιο εχεις προσβαση και στους 4 iterators και ο καθενας αντιπροσωπευει μια θεση του array, οποτε εχεις 4 μελη της τετραδας. Οταν τελειωσει το τετραπλο nested for loop θα εχεις εξαντλησει ολους τους συνδυασμους.

 

Μπορεις να τους βαζεις σε ενα αλλο array ως string ολους μαζι, σε αρχειο, στην οθονη, οπως θες

Μεσα στο ιδιο τελευταιο inner loop μπορεις αν θες να βαλεις και εναν ελεγχο με if που να κοιταει αν και οι 4 iterators ειναι διαφορετικοι μεταξυ τους. Αν ναι, προχωραει στην καταγραφη της τετραδας, διαφορετικα οχι.

 

Δεν ξερω αν μου εχει ξεφυγει κατι, η αν υπαρχει πιο αποτελεσματικος τροπος, αλλα αυτη η προχειρη λυση θα πρεπει να δουλεψει θεωρητικα. Δεν εχω ιδεα τι γινεται απο αποψη ταχυτητας

[bird]

Για να αποφύγεις τους ελέγχους κάθε εσωτερικό loop βάλε το να ξεκινάει από το iterator του προηγούμενου συν 1 και να σταματάει αντίστοιχα...

 

π.χ

max = 85;
for ( i = 0; i < max-3; i++ )
   for ( j = i+1; j < max-2; j++ )
      for ( k = j+1; k < max-1; k++)
         for( l = k+1; l < max; l++)
             // Η τετράδα που θέλεις είναι η: (i+1),(j+1),(k+1),(l+1)

.

[albNik]

Αν έχεις πάντα k=4 σε καλύπτουν 4 loops.

Για μεταβλητό k η γενικά μεγάλο k πρέπει να φτιάξεις μια συναρτηση που σου επιστρεφει τον επόμενο συνδυασμό.

 

int[] next( int[] indices)

{

}

 

π.x  αν ο indices εχει τιμες 

1  5  9  8  

θα επιστέφει 

1  6  0  2

 

Κατι σαν το δεκαδικο σύστημα αρίθμησης.

Google  "next combination"

[Bspus]

Δεν καταλαβα καλα στην αρχη. Εμενα μετραει πχ τις τετραδες 1 2 3 4 και 4 3 2 1 ως διαφορετικες. Μαλλον δεν ειναι το επιθυμητο αποτελεσμα. Οποτε οι αποδεκτες τετραδες ειναι πολυ λιγοτερες

[albNik]

Μια αλλη μέθοδος ειναι ο αλγόριθος για να βρεις όλα τα subsets ενος set.

Π.χ set  {1 2 3   }

 

Ξεκινας με το αδειο 

{}

προσθετεις το 1  

{}

{1}

Προσθετεις το 2

{}

{1}

{2}

{1 2}

 

προσθετεις το 3 και εχεις 

{}

{1}

{2}

{1 2}

{3}

{1 3}

{2 3}

{1 2 3}

 

Εσυ θα κρατας μόνο όσα έχουν μήκος k.

[m@Raki37]

Γεια την ακριβεια οι συνδιασμοι δεν ειναι  48594840 οπως ειπε Bspus αλλα 2024785

(συμφωνα με αυτο το site http://www.calcfun.com/calc-56-syndyasmos-n-arithmon.html ).

Bspus μηπως θα ηταν ευκολο να μου εξηγησεις τι ακριβως εννοεις γιατι οπως ειπα δεν εχω καιρο που ξεκινησα και δεν ξερω αυτους τους ορους

[bird]

Γεια την ακριβεια οι συνδιασμοι δεν ειναι  48594840 οπως ειπε Bspus αλλα 2024785

(συμφωνα με αυτο το site http://www.calcfun.com/calc-56-syndyasmos-n-arithmon.html ).

 

Bspus μηπως θα ηταν ευκολο να μου εξηγησεις τι ακριβως εννοεις γιατι οπως ειπα δεν εχω καιρο που ξεκινησα και δεν ξερω αυτους τους ορους

Οι αριθμοί είναι όντως 2024785 αφού θέλεις συνδιασμό 85 ανα 4 κι όχι όλες τις πιθανές 4αδες γιατί δεν σε ενδιαφέρει η σειρά εμφάνισης...

Θέλεις να φτιάξεις γενικό πρόγραμμα που να βρίσκει συνδυασμό ν αριθμών ανα κ ή συγκεκριμένς 85 από 4;

[m@Raki37]

Συγκεκριμένα 85 από 4. Αλλα και αν εβρισκα καποιο γενικό πρόγραμμα θα το προσαρμοζα.

[bird]

Συγκεκριμένα 85 από 4. Αλλα και αν εβρισκα καποιο γενικό πρόγραμμα θα το προσαρμοζα.

Για 85 ανα 4 σου κάνει κι αυτό που έδωσα παραπάνω με τα 4 loops...

[albNik]

Συγκεκριμένα 85 από 4. Αλλα και αν εβρισκα καποιο γενικό πρόγραμμα θα το προσαρμοζα.

 

Αυτο μου θυμίζει ascii85 , περιπου 85 ειναι οι printable chars. 

Καπου 2 εκατομμύρια passwords με 4 γραμματα ... brutte force στο δευτερολεπτο 

παει το wifi ... 

[Bspus]

Γεια την ακριβεια οι συνδιασμοι δεν ειναι  48594840 οπως ειπε Bspus αλλα 2024785

(συμφωνα με αυτο το site http://www.calcfun.com/calc-56-syndyasmos-n-arithmon.html ).

 

Bspus μηπως θα ηταν ευκολο να μου εξηγησεις τι ακριβως εννοεις γιατι οπως ειπα δεν εχω καιρο που ξεκινησα και δεν ξερω αυτους τους ορους

 

Ναι οπως ειπα στο προηγουμενο ποστ δεν καταλαβα σωστα τι ζητουσε. Νομιζα οτι ο ιδιος αριθμος δεν πρεπει να εμφανιζεται 2 φορες στην τετραδα αλλα οτι οι ιδιοι αριθμοι σε διαφορετικες θεσεις μετρανε σαν αλλη τετραδα. Εφοσον αυτο δεν ισχυει, οι συνδυασμοι ειναι οντως πολυ λιγοτεροι.

Μην κοιτας το δικο μου. Αυτο που γραφει ο bird νομιζω κανει αυτο που ζητας

[m@Raki37]

Λοιπον Οκ το βρηκα........με την βοηθεια του bird βεβαια

 

albNik

τι ακριβως ειναι αυτο που ειπες(ξερω ειναι ασχετο με αυτο που ζηταω αλλα μου ακουγεται ενδιαφερων)

[albNik]

Απο 85 συμβολα μπορεις να φτιάξεις 2024785 τετράδες (passwords) όπου καμια τετραδα να μην έχει τα ιδια συμβολα( με οποιαδήποτε σειρα) με άλλη.

Brutte force σημαίνει εξαντλητική δοκιμή όλων των συνδυασμών μεχρι να "σπάσει" ο κωδικός. 

[m@Raki37]

και το Wifi Τι σχεση εχει?