Vold
Πολύ δραστήριο μέλος
Ο Vold αυτή τη στιγμή δεν είναι συνδεδεμένος. Είναι 28 ετών, Φοιτητής και μας γράφει απο Ηράκλειο (Κρήτη). Έχει γράψει 1,629 μηνύματα.
16-05-16
15:02
2η -και τελευταία- απόπειρα
Δυστυχώς κάπου έχω κάνει κάποιο λάθος οπότε και αναγκάστηκα να το "καλύψω" με ένα trick.
Μέσω του οποίου διαπίστωσα πως ακόμη πιο εύκολα μπορεί να λυθεί η άσκηση απλά καλύπτοντας όλες τις δυνατές περιπτώσεις και "ξεφορτώνοντας" τις μη-έγκυρες.
Δυστυχώς κάπου έχω κάνει κάποιο λάθος οπότε και αναγκάστηκα να το "καλύψω" με ένα trick.
Μέσω του οποίου διαπίστωσα πως ακόμη πιο εύκολα μπορεί να λυθεί η άσκηση απλά καλύπτοντας όλες τις δυνατές περιπτώσεις και "ξεφορτώνοντας" τις μη-έγκυρες.
Code:
public class Subsets {
public static void main(String[] args) {
System.out.println("{}");
// Call the recursive function with different size of the subsets
for( int i = 0; i < args[0].length(); i++) {
findSubsets(args[0], args[0].toCharArray(), i + 1, 0);
}
}
public static void findSubsets(String firstStr, char[] string, int sz, int elem) {
if(elem == sz) {
// Get off the illigal subsets
for(int k = 1; k < sz; k++) {
if(findIndex(firstStr, string[k]) <= findIndex(firstStr, string[k - 1])) return;
}
// Print the next subset
System.out.print("{");
for(int k = 0; k < sz; k++) {
System.out.print(string[k] + (k < sz - 1?",":"}\n"));
}
return;
}
// Find the next subsets
for(int i = 0; i < string.length - sz + 1; i++) {
string[elem] = firstStr.charAt(elem + i);
for(int k = elem + 1; k < sz; k++) {
string[k] = firstStr.charAt(findIndex(firstStr, string[k - 1]) + 1);
}
findSubsets(firstStr, string, sz, elem + 1);
}
}
// Find the index of a char to the original string
public static int findIndex(String str, char c) {
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i)== c) return i;
}
return -1;
}
}
Σημείωση: Το μήνυμα αυτό γράφτηκε 7 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.
Vold
Πολύ δραστήριο μέλος
Ο Vold αυτή τη στιγμή δεν είναι συνδεδεμένος. Είναι 28 ετών, Φοιτητής και μας γράφει απο Ηράκλειο (Κρήτη). Έχει γράψει 1,629 μηνύματα.
15-05-16
17:18
Έτοιμο και το πρόγραμμα, μου πήρε λίγο παραπάνω απ' όσο περίμενα αλλά χαλάλι. Φαίνεται πως η θεωρία απέχει αρκετά από την πράξη, ορισμένες φορές.
Ακολουθώ τον αλγόριθμο που παρέθεσα προηγουμένως εκτός από την προσθήκη των μονό-συνόλων όπου και τα προσθέτω ξεχωριστά για λόγους διευκόλυνσης.
Η αναδρομική συνάρτηση είναι κάπως πολύπλοκη αλλά αν κατάλαβες το σκεπτικό μου, τότε μπορείς να το καταλάβεις και στο πρόγραμμα πολύ εύκολα.
Ακολουθώ τον αλγόριθμο που παρέθεσα προηγουμένως εκτός από την προσθήκη των μονό-συνόλων όπου και τα προσθέτω ξεχωριστά για λόγους διευκόλυνσης.
Η αναδρομική συνάρτηση είναι κάπως πολύπλοκη αλλά αν κατάλαβες το σκεπτικό μου, τότε μπορείς να το καταλάβεις και στο πρόγραμμα πολύ εύκολα.
Code:
public class Subsets {
static String[] Subsets;
static String string;
static int[] Elems;
static int counter = 1;
static int inputSize;
static int i, j;
public static void main(String[] args) {
string = args[0];
inputSize = args[0].length();
Subsets = new String[(int)Math.pow(2, inputSize)];
// Empty Subsets
for(i = 0; i < Subsets.length; i++) {
Subsets[i] = "";
}
// Initialize the one-element Subsets
for(i = 0; i < string.length(); i++) {
Subsets[counter] += string.charAt(i);
counter++;
}
findSubsets(2);
// Print Subsets
for(i = 0; i < Subsets.length; i++) {
System.out.print('{');
for(j = 0; j < Subsets[i].length(); j++) {
System.out.print(Subsets[i].charAt(j) + (j<Subsets[i].length() - 1?",":""));
}
System.out.println('}');
}
}
public static void findSubsets(int sz) {
if(sz > inputSize) return;
Elems = new int[sz];
for(i = 0; i < sz; i++) {
Elems[i] = i;
}
for(j = sz - 1; j > 0; j--) {
while(Elems[sz - 1] < inputSize) {
for(int k = 0; k < sz; k++) {
Subsets[counter] += string.charAt(Elems[k]);
}
counter++;
Elems[sz - 1]++;
}
if(Elems[j - 1] != inputSize - sz + j - 1) {
Elems[j - 1]++;
for(i = j; i < sz; i++) {
Elems[i] = Elems[i - 1] + 1;
}
j = sz;
}
}
findSubsets(++sz);
}
}
Σημείωση: Το μήνυμα αυτό γράφτηκε 7 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.