posoi tropoi gia combinations generator (combinatronics/sindiastiki)?

[Stilewag]

Ipothetoume oti exw ena alfavito 3 xaraktirwn kai exw sindiasmous (lekseis) twn 3 xaraktirwn.

 

Afto mas kanei 3^3=27 sindiasmous (lekseis). An thelw na vrw poia leksi antistoixei ston sindiasmo #6, tha prepei anagkastika na valw 3 "for" kai mexri na ftasw sto 6?

 

Enww kati tetoio:

 

 

#include <stdio.h>

 

int k1,k2,k3;

int Pos1;

int CurPos; //current position

 

Pos1=6; //theloume na vroume pia leksi antisoixei ston sindiasmo #6

 

for (k1=1; k1<=3; k1++)

{

for (k2=1; k2<=3; k2++)

{

for (k3=1; k3<=3; k3++)

{

CurPos++;

if (CurPos=Pos1) printf("combination/word on possition #6 is: %c%c%c", k1,k2,k3);

}

}

}

 

 

..vevaia me ton parapanw tropo telka ekana generate kai tous 27 sindiasmous, alla iparxei tropos kaneis break kai na stamatiseis tin diadikasia sto 6.

 

to thema omws einai na iparxei pio grigoros tropos (gia to mixanima). Dioti entaksei, stin panw periptwsi den thelei poly wra. Alla an i alfavitos exei 96 xaraktires kai o kathe sindiasmos exei 20 gramata... :-| Poso kanei 96^20???

 

Lavete ip'opsin sas oti eimai prwtaris stin C/C++ opote an mporeite kratiste ton kwdika aplo

[alkisg]

Αυτό που ρωτάς είναι:

"ποιος αριθμός είναι το 6 στο τριαδικό σύστημα";

 

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

 

Έτσι αν ήθελες τον 150ο συνδυασμό με αλφάβητο 16 χαρακτήρων, θα ζήταγες το δεκαεξαδικό ισοδύναμο του 150, δηλαδή 000000000096.

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

[Japan]

Loipon, to mono pou mporo na skefto pou na ligostevei tous sindyasmous einai to eksis.

(Variemai na anoikso ta persina vivlia gia tin C, so bare with me)

 

To proto for den tha ekteleitai an o arithmos tou sindyasmou pou psaxnoume einai mikroteros i isos me to tetragono ton xaraktiron.

 

Px. Stin sygkekrimeni periptosi tha to kaname mono an o syndiasmos itan megalyteros apo 9 afou ston 10o to k1 tha allaksei timi.

 

Isos na mporeseis na skefteis kati parapano, me afton ton tropo ligostevoun oi sindyasmoi pou tha ginoun sto 1/k.

 

Chryssa

[Stilewag]

Loipon' date=' to mono pou mporo na skefto pou na ligostevei tous sindyasmous einai to eksis.

(Variemai na anoikso ta persina vivlia gia tin C, so bare with me)

 

To proto for den tha ekteleitai an o arithmos tou sindyasmou pou psaxnoume einai mikroteros i isos me to tetragono ton xaraktiron.

 

Px. Stin sygkekrimeni periptosi tha to kaname mono an o syndiasmos itan megalyteros apo 9 afou ston 10o to k1 tha allaksei timi.

 

Isos na mporeseis na skefteis kati parapano, me afton ton tropo ligostevoun oi sindyasmoi pou tha ginoun sto 1/k.

 

Chryssa[/quote']

 

Nai, aftos einai enas kalos tropos. Egw eixa skeftei enan paromoio alla ligotero kalo tropo gia na meiosw tous sindiasmous.

[Stilewag]

Αυτό που ρωτάς είναι:

"ποιος αριθμός είναι το 6 στο τριαδικό σύστημα";

 

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

 

Έτσι αν ήθελες τον 150ο συνδυασμό με αλφάβητο 16 χαρακτήρων' date=' θα ζήταγες το δεκαεξαδικό ισοδύναμο του 150, δηλαδή 000000000096.

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

 

Aftos o tropos prosegkizei afto pou etoimazw twra

 

Exw idi enan algorithmo etoimo o opoios sou zitaei:

 

1. to mikos tou alfavitou

2. to mikos tis lekseis

3. tin topothesia tis lekseis pou theleis na vreis

 

kai sou vrisei tin leksi (etoimazw kai to antistrofo)

 

Den xrisimopoiw omws pinakes, oute dekaeksadiko sistima :|

 

Den to exw dokimasei akoma, alla tha prospathisw na tropopoiisw ton algorithmo wste na vriskei poia leksi antistoixei se mia topothesia... me ena alfavito 96 xaraktirwn, kai mia leksi 50 xaraktirwn. Diladi mesa se mia lista apo 96^50 pithanous sindiasmous, kai ola afta se ena logiko xroniko diastima se enan Pentium1 133MHz me 16MB RAM (... !!!)

 

An ithela na to kanw me simvatikes methodous tha prepei na valw 50 "for" to ena mesa sto allo :-|

 

An ithela omws na to kanw me pinakes opws les, pws tha to ekana? (me 96 xaraktires alfavito kai 50 xaraktires i kathe leksi)

[alkisg]

1) Ορίζεις τον πίνακα του αλφαβήτου, Α = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, H, ...} με 96 χαρακτήρες

2) Έστω ο αριθμός σου είναι ο κ

3) Ο παρακάτω κώδικας εμφανίζει το αποτέλεσμα ΑΝΑΠΟΔΑ στην οθόνη, σου μένει εργασία να το αντιστρέψεις με κάποιον τρόπο και να προσθέσεις τα υπόλοιπα μηδενικά μέχρι να γίνει 50 χαρακτήρες ;-)

 

while (k != 0) {

printf("%c", A[k % 96]);

k = k / 96;

}

 

Αυτό ήταν!

[Stilewag]

to "k" einai to location? diladi to simeio gia to opoio theloume na vroume tin "leksi"?

[EPa]

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

 

Να ένα λίγο πληρέστερο πρόγραμμα C με σχόλια για να "μιλάει" απο μόνο του, σε περίπτωση που έχεις ακόμη απορίες:

 

int main(void)

{

const int number_of_letters = 3; /* estw alfabnto 3 xaraktnrwv */

char alphabet[] = {'A', 'B', 'C'}; /* oi opoioi eivai oi A B kai C */

 

char inverted_result[1000]; /* to apotelesma 8a xreiastei avtistrofn */

int wanted, position_in_result = 0; /* elpizw milave mova tous */

 

/* eisagwgn dedomevwv */

 

printf("Number of wanted combination? ");

scanf("%d", &wanted);

 

/* upologismos */

 

do {

inverted_result[position_in_result++] = alphabet[wanted % number_of_letters];

wanted /= number_of_letters;

} while (wanted > 0);

 

/* avtistrofn apotelesmatos */

 

do {

printf("%c", inverted_result[--position_in_result]);

} while (position_in_result > 0);

 

printf("\n");

}

 

 

Να πω βέβαια ότι η πρώτη δυνατή λέξη στο παραπάνω θεωρείται ο συνδυασμός 0. Αν θέλεις να τον ονομάζεις 1, μείωσε κατά ένα το wanted μόλις το διαβάσεις (αμέσως μετά τη scanf πχ.), ή δώσε 1 λιγότερο από ότι θέλεις όταν το πρόγραμμα σε ρωτάει.

[alkisg]

1) Ναι, το k είναι το location

2) Για k=0 το αποτέλεσμα είναι κενό και πρέπει να το συμπληρώσεις με 50 μηδενικά (δηλαδή λαμβάνεται υπ' όψη και ο πρώτος συνδυασμός

3) Το πρόγραμμα του EPa είναι μια χαρά (εγώ είπα να μην στο δώσω στο "πιάτο"), μόνο που η αντιστροφή δεν χρειάζεται ξεχωριστό loop, μπορεί να γίνεται κατά την εισαγωγή

[Stilewag]

to "piato"... "serviristike" alla vrethika pro ekpliksews!

 

mallon den eksigisa kala to ti ithela kai etsi to programa mou evgaze alla apo afta pou perimena

 

vasika exw idi enan algorithmo o opoios kanei mia xara tin douleia, alla exei provlima sto oti prepei na kanw sigkekrimena "for" kai o arithmos twn loops franei to 96^100 (afti einai enas apo tous logous aftou tou thread: http://www.insomnia.gr/vb3/showthread.php?t=105358)

 

exw ena .exe pou kanei epidiksi (demonstration), alla den mporw na valw megalous arithmous sto word_length kai sto alphabet_length. to arxeio einai ena .zip apo to briefcase mou sto pathfinder: http://briefcase.pathfinder.gr/file/Stilewag/33894/406139

 

exw perielavei merika .txt pou exoun listes sindiasmwn, oi opoies dimiourgithikan me apla nested "for"

 

elpizw na min ginetai poly vareto na to koitaksete kai signwmi gia to .exe (pou den dinw source) alla isws na ginei paper opote erm... diskolevomai na doso ton kwdika :-S

[GrMikeD]

elpizw toulaxiston omws na anafereis sto paper oti gia ta for loops tis ereunas sou se boithisan atoma apo to insomnia.

 

Ade kai commercial product!

[Stilewag]

efxaristws, alla den mou xrisimefse o kwdikas :-|

 

to eides to .exe?

[alkisg]

Το output από μια εκτέλεση του προγράμματος:

>
This program is a test on combinatronics. The program finds
a combination without generating all combinations beafore
the desired one. This leads to less time consumed.

You must supply with a word length and an alphabet length.

In this version of the algorithm, there are two limitations:
(1) I used integers so don't give big number as word length
and alphabet length
(2) I used only the low-case letters as an alphabet (a-z).
This means that you can only have alphabet length 1-26.

After you supple with word length and alphabet length
the program will display the 'number of possible combinations'.
If it is negegine (e.g.: -54366), then you have given exceeded
the integer limits 

give me word length: 3
give me alphabet length: 5
INFO: number of possible combinations: 125
find the word in what location (must be smaller or equal to 125)?: 100

INFO: the word at location 100 is: dee

 

Εγώ βλέπω ότι είναι ΑΚΡΙΒΩΣ αυτό που σου είπαμε!!!

Το πρόβλημα που λύνει το .exe σου λύνεται σε Ο[Ν], όπου Ν το μήκος λέξης. ΔΕΝ μπορείς να κάνεις paper με αυτό το .exe, η λύση που σου δώσαμε υπάρχει ακόμα και στα σχολικά βιβλία του λυκείου.

 

Μάλλον κάτι δεν έχεις καταλάβει εσύ, προσπάθησε να δεις τι δεν έχεις καταλάβει και κάνε συγκεκριμένες ερωτήσεις για να σε βοηθήσουμε...

[Stilewag]

nai. to koitaw na dw pou egine to lathos.

[EPa]

Δεν υπάρχει λάθος. Το πρόγραμμα που σου έδωσα θα κάνει ακριβώς το ίδια πράγματα αρκεί να βάλεις στην 1η γραμμή τα γράμματα του αλφαβήτου (πχ. 5 αν θες να τρέξεις το παράδειγμα που έτρεξε ο alkisg, και βέβαια να συμπληρώσεις και το αλφάβητο στη 2η γραμμή). Μετά τρέξτο και δώσε ζητούμενο συνδυασμό 99 και θα πάρεις το ίδιο αποτέλεσμα: dee.

 

Πρέπει να δώσεις 99 γιατί το πρόγραμμα που έχεις θεωρεί 1ο συνδυασμό τον 1 και όχι τον 0 και όπως είπα:

 

Να πω βέβαια ότι η πρώτη δυνατή λέξη στο παραπάνω θεωρείται ο συνδυασμός 0. Αν θέλεις να τον ονομάζεις 1, μείωσε κατά ένα το wanted μόλις το διαβάσεις (αμέσως μετά τη scanf πχ.), ή δώσε 1 λιγότερο από ότι θέλεις όταν το πρόγραμμα σε ρωτάει.

 

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