w ايجاد power set

اقتباس

يجب أن لا يوجد تكرار لنفس العنصر في الصف الواحد

هذا سيسهل العديد من الأمور.

1- نقوم بتجميع محتويات كل سطر على حدى.

2- نقوم بالحصول على الأرقام الموجوده بكل السطور بدون تكرار و ذلك لإنشاء التحليل بين الأرقام المستخدمه فقط.

3- نبدأ فى إجراء التحليل بالإعتماد على الأرقام التى حصلنا عليها من 1 و 2.

الخطوه الأولي ذات مستوى متوسط الصعوبة، و فيها نقوم بفتح الملف و قراءة كل محتوياته ثم تحليلها داخل مصفوفة من نوع struct و الذى يحتوى على معلومات السطر.

// line information
typedef struct _row
{
    // number of elements in row
    int  count;
    // each element will have 1 if it is present, 0 if missing
    char value[10];
} row;

// get lines information from disk file
row* read_file(const char* file_name, int* line_count);

التركيب row يمثل السطر و يحتوى على المتغير count و هو عدد الأرقام الموجوده بالسطر و المصفوفه value هى العناصر الموجوده بالسطر و قيمة العنصر هى موقعه بالمصفوفة و إذا كان حاضرا فقيمته 1 و إذا كان غائبا فقيمته 0، مثال:

5 7 3 9 2 5

row.count = 5;
row.value[0] = 0;
row.value[1] = 0;
row.value[2] = 1;
row.value[3] = 1;
row.value[4] = 0;
row.value[5] = 1;
row.value[6] = 0;
row.value[7] = 1;
row.value[8] = 0;
row.value[9] = 1;

هذا الإسلوب يتيح الوصول للعنصر بشكل سريع. التركيب row يتعامل فقط مع الأرقام فى المدى من صفر و حتى 9 فإذا حدث و أن تم تغيير المدى فلابد من تغيير عدد عناصر المصفوفة value.

الدالة read_file تقوم بتنفيذ الخطوة الأولي حيث تستقبل مسار الملف داخل file_name و تقوم بالعودة بمصفوفة من نوع row و عدد عناصرها يتم الرجوع به من خلال مؤشر يتم تمرير كمعامل ثاني للدالة و إسمه line_count.

بالنسبة لي فقد قمت بتقسيم الخطوة الأولي لدالتين الأولي هى read_file تقوم بفتح الملف و الحصول على محتوياته و تمريرها لدالة أخرى ثم تقوم بتحرير الذاكرة و غلق الملف و إعادة القيمة المعادة من الدالة الثانية. الدالة الثانية read_string تقوم بتحليل النص و حجز الذاكرة لمصفوفة row. هذه الدالة تأخذ الشكل التالي:

row* read_text(const char* string, int size, int* line_count)

المعامل الأول هو النص المراد تحليله و المعامل الثاني هو حجم النص و المعامل الثالث سيحتوى على عدد عناصر المصفوفة row التى سيتم العودة بها.

سبب فصل كود تحليل النص عن كود التعامل مع الملف لتسهيل تنقيح الكود و ايضا لإتاحة فرصة تمرير نص بدلا من ملف.

الكود الخاص بالخطوه الأولي:

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define VALUES_COUNT 10

// line information
typedef struct _row
{
    // number of elements in row
    int  count;
    // each element will have 1 if it is present, 0 if missing
    char value[VALUES_COUNT];
} row;

// get lines information from disk file
row* read_file(const char* file_name, int* line_count);
// get line information from in-memory string
row* read_text(const char* string, int size, int* line_count);


int main(int count, char** args)
{
    row* nums = NULL;
    int line_count = 0;

    if (count != 2) return 1;

    // get data-sets
    nums = read_file(args[1], &line_count);
}

row* read_file(const char* file_name, int* line_count)
{
    // result line information array
    row* res = NULL;
    // file size
    int size = 0;
    // file data
    char* string = NULL;

    // open file
    FILE* file = fopen(file_name, "rb");
    if (file == NULL) return NULL;

    // get file size and allocate temp buffer
    fseek(file, 0, SEEK_END);
    size = ftell(file);
    string = (char*)malloc(ftell(file)+1);

    // get data
    fseek(file, 0, SEEK_SET);
    fread((void*)string, 1, size, file);
    string[size] = 0;
    fclose(file);

    // get result
    res = read_text(string, size, line_count);
    free(string);

    return res;
}

row* read_text(const char* string, int size, int* line_count)
{
    // used to track a position in array 
    int index = 0;
    // index of currently scanning line
    int cur_line = 0;
    // temporary counter
    int i = 0;
    // line information
    row* rows = NULL;
    // string contains at least one line
    *line_count = 1;

    // get number of lines
    for(; index<size; ++index)
    {
        if (string[index] == '\n') ++*line_count;
    }

    // allocate buffer
    rows = (row*)malloc(sizeof(row) * *line_count);
    if (rows == NULL) return NULL;
    rows[0].count = 0;

    // zero data-set
    memset((void*)rows, 0, sizeof(row) * *line_count);

    // scan line content
    for(index=0; index<size; ++index)
    {
        // if new line mark
        if (string[index] == '\n')
        {
            // update current line index, and skip
            ++cur_line;
            continue;
        }

        // skip carriage-return
        if (string[index] == '\r') continue;

        // get number of digits in line
        rows[cur_line].count = string[index] - '0';

        // number of digits scanned in this line
        i = 0;

        // get row digits
        while (i<rows[cur_line].count)
        {
            // skip character if it's whitespace
            if (isspace(string[++index])) continue;

            // update information
            rows[cur_line].value[ string[index] - '0' ] = 1;

            // update number of scanned digits
            ++i;
        }
    }

    return rows;
}

الدالة main يتم تمرير مسار الملف عن طريق الـ debugger.

المتغير nums سيتم وضع محتويات السكور به بعد تحليلها و المتغير line_count سيحتوى على عدد السطور.

الخطوة الثانية مستواها سهل حيث سنقوم بالمرور على كل عناصر المصفوفة row لكل السطور و تحديد الأرقام الموجوده بدون تكرار.

الدالة get_present_nums تقوم بهذه العملية و شكلها كالتالي:

// get present numbers in all rowsvoid get_present_nums(row* rows, int count, row* present_nums){    // temporary counters    int i=0, j=0;    // zero result-set    memset((void*)present_nums, 0, sizeof(row));    for (i=0; i<count; ++i)    {        for (j=0; j<VALUES_COUNT; ++j)        {            // if current element is not present, skip it            if (rows.value[j] != 1) continue;            // if current digit already counted, skip it            if (present_nums->value[j] == 1) continue;            present_nums->value[j] = 1;            ++present_nums->count;        }    }}

يتم تمرير مصفوفة من نوع row كأول معامل و عدد عناصرها كمعامل ثاني و المعامل الثالث هو مؤشر لمتغير من نوع row ليتم تحديث قيمته بالعناصر الموجوده.

الأكواد السابقه يمكن إضافة العديد من التحسينات عليها و لكنه أمر غير محبذ لأن البرنامج بأكمله لم ينتهي.

الخطوه الثالثة الخاصة بالإحصاء من المفترض ان تكون يسيرة لأنك الأن لديك المتغير من نوع row الذى يحتوى على كافة الأرقام الموجوده بكل السطور بدون تكرار لذا بإستخدام عددهم (row.count) سيتم عمل حلقة تكرار خارجية و بداخلها سيتم عمل حلقة تكرار أخرى و هى التي ستقوم بتنقيح الـ data-set.

حاولي تقسيم هذه الخطوه على مجموعة من الدوال و كل واحدة تقوم بأمر محدد لأنه بغير ذلك سيصبح الأمر شاق و صعب، أيضا لا تدمجي كود الطباعة مع كود الإحصاء لأن هذا سيصعب من تنقيح الكود.

التركيب الخاص بالإحصاء قد يأخذ الشكل التالي:

// statistics about data-set
typedef struct _state
{
    // the set of number that represent this statistics
    row num;
    // number of times num existed
    int count;
} state;

حيث المتغير num هو الرقم أو الأرقام التى يتم إحصاءها معا مثل {1} أو {1,9} و حيث ان محتويات row مرتبه و معلوم عدد العناصر بهم فلن توجد مشكلة فى طباعتهم.

المتغير count هو عدد مرات تكرار قيمة row داخل مصفوفة من row.

يوجد أمر أخير يستوجب الذكر و هو عدد عناصر مصفوفة state النهائية و يمكن حسابه بإستخدام المعادلة التالية:

n * (n-1) + 1

حيث n هو عدد العناصر التى سيتم حساب التابدل لهم بدون تكرار و الواحد الأخير لأنه سيتم إضافة كل العناصر الموجوده داخل الإحصاء النهائي، مثال:

{1}

set_size    = 1
state_count = 1 * (1 - 1) + 1 = 1 * 0 + 1 = 0 + 1 = 1

[1] = 1

*********************
{1, 2}

set_size    = 2
state_count = 2 * (2 - 1) + 1 = 2 * 1 + 1 = 2 + 1 = 3

[1] = 1
[2] = 2
[3] = 1 2

*********************
{1, 2, 3}

set_size    = 3
state_count = 3 * (3 - 1) + 1 = 3 * 2 + 1 = 6 + 1 = 7

[1] = 1
[2] = 2
[3] = 3
[4] = 1 2
[5] = 1 3
[6] = 2 3
[7] = 1 2 3

*********************
{1, 2, 3, 4}

set_size    = 4
state_count = 4 * (4 - 1) + 1 = 4 * 3 + 1 = 12 + 1 = 13

[ 1] = 1
[ 2] = 2
[ 3] = 3
[ 4] = 4
[ 5] = 1 2
[ 6] = 1 3
[ 7] = 1 4
[ 8] = 2 3
[ 9] = 2 4
[10] = 3 4
[11] = 1 2 3
[12] = 1 2 4
[13] = 1 2 3 4

و الله ولي التوفيق