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

Εχω μια σειρά από διαφορετικούς αριθμούς (γραμματα, αντικείμενα, οτιδήποτε - μην το "δέσετε" με strings όπως κάνουν συνήθως - hint: είτε αριθμούς θα έχω είτε αντικείμενα).

Π.χ.
Α. 121
Β. 57
Γ. 83

Θέλω όλους τους δυνατούς ΜΟΝΑΔΙΚΟΥΣ συνδυασμούς, ανεξαρτήτως θέσεως. Ητοι ο αλγόριθμος θα πρέπει να υπολογίζει permutations (ετσι δεν τα λενε; ) αλλά μοναδικά (δεν ξέρω πως τα λένε). Οι συνδυασμοί δεν είναι ανάγκη να είναι τριών θέσεων.

Στο παράδειγμα, θα έπρεπε να προκύπτουν τα εξής:
121
57
83
121, 57
121, 57, 83
121, 83
57, 83

(για να γινει πιο κατανοητο, "121,57,83" και "83,121,57" δεν αποτελούν διαφορετικούς συνδυασμούς)

In real life, αυτά θα είναι objects που θα έχουν ένα αριθμητικό property και θα πρέπει να συνδυαστούν κατά όλους τους δυνατούς τρόπους με τους ανωτέρω περιορισμούς.

Ζητούμενα:
1. Εχει όνομα ο αλγόριθμος που κάνει αυτό το πράγμα; (Combinatorial? Permutation? Αλλο?)
2. Υπάρχει αλγόριθμος που κάνει αυτό το πράγμα;
3. Μηηηηπως υπάρχει παράδειγμα σε VB.NET; (I'm pushing my luck, I know :) )

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

Υ.Γ. Ευτυχώς δηλαδή που έκανα και Συνδυαστική στο Πανεπιστήμιο...:) :) :)

 

---

Σωτήρης Φιλιππίδης

DotSee Web Services

Πρέπει να ψάξεις για combinations, όχι permutations. Θα βρεις μια υλοποίηση στο http://msdn.microsoft.com/msdnmag/issues/04/07/TestRun/ αλλά φυσικά είναι σε C#!

---

Παναγιώτης Καναβός, Freelancer
Twitter: http://www.twitter.com/pkanavos

Wow! Υπερ-ταχύς και υπέρ-ακριβής!

Τωρα που βρήκα τα λογικά μου, να ορίσω ακριβέστερα (γιατι ο ορισμός που έδωσα πριν ήταν του δημοτικού), οτι αυτό που έψαχνα είναι συνδυασμοί n (οπου n>1) αντικειμένων σε k πλήθος οπου k Ε (1,n). (Για να μην ξεχνάμε και τα λιγοστά μαθηματικά που ακόμα θυμόμαστε).

Θα το εξετάσω διεξοδικώς και θα επανέλθω!

---

Σωτήρης Φιλιππίδης

DotSee Web Services

Λοιπόν για απλά strings:

string[] list=new string[] {"a","b","c","d"};


int n=list.Length;


int permutations= (int)Math.Pow(2,n)-1;


string[] allList=new string[permutations];


int m= 0;


for(int j=n-1; j>=0; j--)


{


    allList[m]=list[j];


    m++;


    for(int k=0; k < (int)Math.Pow(2,(n-(j+1)))-1; k++)


    {


        allList[m]=list[j]+allList[k];


        i++;


    }


}
τωρα για objects θα πρέπει το allList να ειίναι πίνακας απο ArrayList δηλαδή:
ArrayList[] allList=new ArrayList[permutations];
και σε καθε allList[m]=list[j]+allList[k];θα πρέπει να αντιγράφεις όλα τα objects της λίστας allList[k]; + το list[j] object στην νέα λίστα allList[m].

Το πώς καταλύγεις σε αυτόν τον αλγόριθμο σε επόμενο post γιατί τώρα με μαστιγώνει το boss :(

Πολύ γρήγορα, από το κείμενο, χωρίς να τρέξω τον κώδικα είδα τη λέξη "permutations".

Αν δεις ομως πιο πανω, αυτό που χρειάζομαι είναι "combinations". Δεν θέλω δηλαδή να έχω το "abc" ΚΑΙ το "bac" γιατί ως συνδυασμοί είναι ισοδύναμοι.

---

Σωτήρης Φιλιππίδης

DotSee Web Services

:) το permutations το εβαλα απλα για να καταλαβεις οτι εκει υπολογιζεται το πληθος των συνδιαζμών (combinations, permutations what ever....) κατα τα αλλα κάνει αυτό που θέλεις, "abc" και "bac" δεν υπολογίζονται.

Μια λύση που θα πρότεινα, είναι η ύπαρξη ισοδύναμων for, nested, όπου τα βαφτίζουμε 1 ως n, και το n είναι το πιο nested.

Κάθε for, μπορεί να πάρει τιμές από χ ως το πλήθος των ψηφίων. Αν X είναι ένα συγκεκριμένο for το οποίο είναι nested X επίπεδα, και X-1 το "container" του, τότε το χ είναι η τιμή έναρξης του for X-1 για το for X.

Ούτε ο ίδιος δεν είμαι ευχαριστημένος με τη διατύπωσή μου, αλλά ένα χοντροκομμένο παράδειγμα, θα ήταν το εξής:


char[] letters = new char[]{'a','b','c'};
StringCollection combinations = new StringCollection();
string tmpString = "";

for (int i=0; i < letters.Length; i++) {
tmpString += letters<img src="/cs/emoticons/emotion-55.gif" alt="Idea [I]" />;

for (int j=i; j < letters.Length; j++) {
tmpString += letters<img src="/cs/emoticons/emotion-55.gif" alt="Idea [I]" />;

for (int k=k; k < letters.Length; k++) {
combinations.Add(tmpString + letters<img src="/cs/emoticons/emotion-55.gif" alt="Idea [I]" />);
tmpString = "";
}
}
}


Φυσικά, το παραπάνω καλό (=απαραίτητο) είναι να γίνει με recursion, αλλά δεν έχω χρόνο τώρα να το ψάξω.

---

Μην αφήνετε τα media να σας "ταΐζουν"!

Σας ευχαριστώ όλους! Η βοήθειά σας ήταν πραγματικά πολύτιμη. Να σχολιάσω για την πρόταση του Παναγιώτη (pkanavos) οτι αποτελεί μια καλά υλοποιημένη λύση υπολογισμού συνδυασμών ΚΑΙ εκτίμησης πλήθους συνδυασμών πριν τον υπολογισμό, σε C#. Με την ίδια library που υπάρχει στο link που έδωσε ο Παναγιώτης μπορεί κάποιος να κάνει και συνδυασμούς objects αν αυτά έχουν μια GUID property.

---

Σωτήρης Φιλιππίδης

DotSee Web Services