#include <iostream>
#include <cstdlib>
#include <string.h>
using namespace std;
char* subString(char* str,int index,int strlength);
int subSet(char* Set,int length);
/*
Για να κρατήσω τον κώδικα όσο πιο απλό γίνεται, ώστε να είναι εύκολα κατανοητός το παρακάτω
πρόγραμμα δεν είναι το βέλτιστο. Ναι μεν θα παράγει όλα τα δυνατά υποσύνολα, αλλά θα παράγει
μερικά πάνω από μία φορά. Το να μειώσουμε την παραγωγή αυτή είναι σχετικά εύκολο καθώς απλά
θα πρέπει να περνάμε τα παραχθέντα υποσύνολα σε ένα πίνακα στοιχείων και προτού εισάγουμε ένα
νέο να ελέγχουμε αν ήδη υπάρχει. Αν και εύκολο στην σύλληψη η υλοποίηση έχει πολλές γραμμές
κώδικα και τεχνικές λεπτομέρειες της C++ γι'αυτό και θα την παραλείψω.
*/
int main()
{
char str[] = "abc";
subSet(str,3);
return 0;
}
/*
Η subSet είναι η αναδρομική συνάρτηση που θα παράγει όλα τα υποσύνολα. Ως παραμέτρους
δέχεται έναν πίνακα χαρακτήρων Set όπου περιέχεται το αρχικό σύνολο, καθώς και μία
μεταβλητή int όπου περιέχεται των πλήθος των διαφορετικών στοιχείων του συνόλου.
Για παράδειγμα αν Set = "αβγ" και length = 3 έχουμε το σύνολο {α,β,γ}.
*/
int subSet(char* Set,int length){
/*
Επειδή η συνάρτηση είναι αναδρομική, καλεί δηλαδή τον εαυτό της, για να μην έχουμε
μια ατέρμονη επανάληψη χρειαζόμαστε ένα if τερματισμού, όπως το παρακάτω. Στην
περίπτωση που η παράμετρος length είναι 0 τότε σημαίνει πως ως είσοδος μας δόθηκε
το κενό σύνολο, συνεπώς το βάζουμε σε μια προσωρινή μεταβλητή temp και του τυπώνουμε,
ενώ στην συνέχεια η αναδρομική συνάρτηση τερματίζει.
*/
if(length == 0)
{
char* temp = (char*)malloc(3);
temp[0] = '{';
temp[1] = '}';
temp[2] = '\0';
cout << temp << endl;
free(temp);
return 0;
}
/*
Αντιθέτως, αν το length είναι μεγαλύτερο του 0, τότε το αρχικό μας σύνολο δεν είναι το
κενό και επομένως πρέπει να παράγουμε υποσύνολα. Θα ξεκινήσουμε παράγοντας υποσύνολα τα
οποία έχουν βαθμό μικρότερο κατά 1 του αρχικού συνόλου. Δηλαδή αν το αρχικό μας σύνολο
είναι "αβγ" βαθμού 3 καθώς περιέχει 3 στοιχεία, τα πρώτα υποσύνολα που θα παράγουμε θα
είναι τα "αβ","αγ" και "βγ", όλα βαθμού 2.
*/
else
{
cout << Set << endl; // Πρώτα τυπώνουμε το παρόν σύνολο, δηλαδή το "αβγ".
/*
Η παρακάτω for υλοποιεί την αναδρομή που θα παράγει όλα τα υποσύνολα. Κάθε σύνολο βαθμού
Ν έχει Ν άμεσα υποσύνολα. Για παράδειγμα το σύνολο "αβγ" βαθμού 3 έχει 3 άμεσα υποσύνολα
βαθμού 2. Συνεπώς με την παρακάτω for, καλούμε 3 φορές την συνάρτηση subSet. Ως παραμέτρους
τώρα θα της περάσουμε ένα σύνολο χαρακτήρων και ένα μήκος ή βαθμό συνόλου. Ο βαθμός του
επόμενου συνόλου θα είναι προφανώς κατά 1 μικρότερος από τον τωρινό βαθμό άρα length-1.
Η συνάρτηση subString δέχεται τρεις παραμέτρους. Ένα σύνολο, ένα δείκτη και το μήκος του
συνόλου (ή βαθμό). Αυτό που θα επιστρέψει θα είναι ένα υποσύνολο του συνόλου που δέχθηκε
μικρότερο κατά 1 βαθμό και δίχως το στοιχείο στο οποίο δείχνει ο δείκτης i. Για παράδειγμα
αν περάσουμε τις παραμέτρους "αβγ",1,3 θα μας επιστραφεί το σύνολο "αγ" καθώς θα αφαιρεθεί
το στοιχείο του "αβγ" που βρίσκεται στη θέση 1 δηλαδή το "β". (Στην C++ οι πίνακες αρχίζουν
από το 0, άρα η δεύτερη θέση του πίνακα έχει τον δείκτη 1.)
Επόμένως η παρακάτω for θα τροφοδοτήσει την συνάρτη με τα σύνολα "αβ","αγ" και "βγ" και θα
ξεκινήσει έτσι μια νέα αναδρομή.
*/
for (int i=0;i<length;i++)
{
subSet(subString(Set,i,length),length-1);
}
}
return 0;
}
/*
Αυτή είναι η συνάρτηση που "κόβει" το σύνολο που δέχεται ανάλογα με τον δείκτη.
Δεν θα την εξηγήσω περαιτέρω καθώς είναι απλά τεχνική υλοποίηση και δεν έχει
άμεση σχέση με την λογική του αλγορίθμου.
*/
char* subString(char* str, int index, int strlength) {
char* temp;
int j = 0;
if (strlength == 1)
{
temp = (char*)malloc(3);
temp[0] = '\0';
return temp;
}
temp = (char*)malloc(strlength);
for (int i = 0; i<strlength; i++)
{
if (i != index)
{
temp[j] = str[i];
j++;
}
}
temp[j] = '\0';
return temp;
}
