هل يمكنك إيجاد جميع الإحتمالات !؟

لقد قمت بدراسة مرة هده الخوارزمية ولكني لم أقم بالمواصلة ووجدت أن:

أي خانة من الخانات سوف تتكرر حسب عدد الخانات وادا كانت عدد الخانات هي 2 فان أي عدد سوف يتكرر 1 مرة يعني متلا لدينا 12 عدد الخانات هو 2 لدينا 1 و 2 ويمكن أن يصبح 12 أو 21 يعني 1 يكون في اليمين مرة واحد تم اتنان كدلك وأما ادا كانت عدد الخانات 3 فان عدد مرات ضهور كل رقم في كل خانة هو 2.وهكدا

أنضر الي هدا الجدول الدي توصلت اليه تحصل علي النتيجة القادمة انطلاققا من النتيجة السابقة:

أتمني أن تفهموا ما أقصده.

اقتباس

إذاً فلنبدأ ..

أشكرك على متابعة الموضوع أخي الفاضل :)

بانتظار آراء بقية الإخوة.

the inventor habib@

نعم, الخوارزمية لكلاسيكية للتباديل تنص على الآتي (و هي التي استخدمها الأخ مومو في محاولاته):

في كل مرة يتم تثبيت أحد أحرف الكلمة ثم يتم إظهار جميع الإحتمالات المُرافقة لذلك الحرف.

انظر المثال : الحرف ذو اللون الأزرق يُمثل بداية الإحتمال و الأحرف ذات اللون الأحمر تُمثل الإحتمالات المُرافقة له :

في المرة الأولى قمنا بتثبيت A و إظهار B و C ثم C و B و هي الإحتمالات المُرافقة لــ A ثم كررنا نفس العملية مع B و C.

اقتباس

يعني في المتال السابق لدينا عدد مرات التبادل هو 6 لان 2*3=6

و هنا تكمن إحدى أبرز مشاكل خوارزمية التبديل ..!

لأن الــ complexity factorial يحتاج إلى وقت لا نهائي للتنفيذ عند معالجة بيانات كبيرة (770 سنة من أجل n=20 !!) :

و بالتالي فإن الوقت المُستغرق للخوارزمية سيكون كارثيا بغض النظر عن التحسينات التي قد تطرأ عليها (ما لم يتغير التعقيد الزمني).

أحمد الشنقيطي كتب:

و هنا تكمن إحدى أبرز مشاكل خوارزمية التبديل ..!

لأن الــ complexity factorial يحتاج إلى وقت لا نهائي للتنفيذ عند معالجة بيانات كبيرة (770 سنة من أجل n=20 !!) :

عوضا عن ذلك انتظر الي 2025 الموعد المحدد (بمتوسط التوقعات الاحصائية) بولادة الحواسيب الكمية ( هنا التفاصيل عنها )والتي ستجعل من 770 اقل من 0.000770 ثانية

اقتباس

لأن الــ complexity factorial يحتاج إلى وقت لا نهائي للتنفيذ عند معالجة بيانات كبيرة (770 سنة من أجل n=20 !!) :

يعني أن ليس هناك حل لدلك الا ادا كان الحاسوب سريع جدا جدا

اقتباس

عوضا عن ذلك انتظر الي 2025 الموعد المحدد بولادة الحواسيب الكمية والتي ستجعل من 770 اقل من 0.000770 ثانية

هل لهذا علاقة بالــ Quantum Algorithm, مثل Shor's algorithm, Grover's algorithm and Deutsch–Jozsa algorithm ؟

اقتباس

يعني أن ليس هناك حل لدلك الا ادا كان الحاسوب سريع جدا جدا

الأصل أن العمليات المعقدة (تحتاج إلى سنوات للتنفيذ) يتم إجراءها على حواسيب فائقة السرعة (Supercomputer)

مثل الحاسوب الصيني الضخم Tianhe-1A (بالصينية 天河一号. بالعربية درب التبانة _ مجرتنا _), هذا الحاسب قادر نظرياً على اجراء كوادريليون حساب في الثانية (1 پـِتافلوپ) !!!

و هو من إنتاج مركز الحاسوب الفائق الوطني و تحت رعاية الجامعة الوطنية لتكنولوجيا الدفاع, يعمل على نظام تشغيل ليونكس و تبلغ ذاكرته 98304 GB و تصل سرعته إلى 1.206 پـِتافلوپس و يُستخدم في استكشاف النفط ومحاكاة الطائرات و قد وصلت تكلفته إلى 88.24 مليون دولار (من قال أنه توجد أزمة مالية ؟ :D)

أحمد الشنقيطي كتب:

هل لهذا علاقة بالــ Quantum Algorithm, مثل Shor's algorithm, Grover's algorithm and Deutsch–Jozsa algorithm ؟

نعم يتم تطبيق الخوارزميات الكمومية فى هذا النوع من الحواسيب الكمومية وهي تختلف مطلقا عن Classic Algorithms

للطرق التقليدية التي تم عرضها في الموضوع، يمكن تسريع الحصول على النتائج باستخدام تعليمات أسمبلي بدلاً من أوامر C/C++

ومثلاً كتابة برنامج مركزي يقوم بتوزيع المهام على برامج فرعية قد تكون موزعة على حواسب مختلفة، بالتالي يكون لديك distributed computing.

BOINC أحد الأمثلة على ذلك، وهو مستخدم في حساب checksums في مشروع freerainbowtables.com

إضافة: تنفيذ البرنامج كتطبيق x64 مهم جداً لتخفيض الوقت، فأحجام المسجّلات التي سيتم استخدامها في التعليمات سيتضاعف وبالتالي سيكون هناك قدرة على اختصار عدد التعليمات المطلوب تنفيذها.

اقتباس

يمكن تسريع الحصول على النتائج باستخدام تعليمات أسمبلي بدلاً من أوامر C/C++

هل تعتقد أن إدراج أوامر أسمبلي في كود C/C++ (باستخدام asm مثلا) سيزيد من سرعة البرنامج ؟

مثال ؟

اقتباس

مثلاً كتابة برنامج مركزي يقوم بتوزيع المهام على برامج فرعية قد تكون موزعة على حواسب مختلفة، بالتالي يكون لديك distributed computing.

لو كنا نعمل على حاسب يمتلك عدة معالجات سريعة فأظن أن استخدام أكثر من (Computing Element (CE عن طريق البرمجة المتوازية (parallel programming) سيكون مفيدا أيضا.

أحمد الشنقيطي كتب:

السلام عليكم

باستخدام خوارزمية جديدة و بالاستعانة بالدالة write الموجودة في المكتبة unistd.h يُمكننا عرض جميع الإحتمالات المطلوبة في وقت وجيز شيئا ما (الملف التنفيذي في المرفقات باسم NumberOfPermutation_1) :

#include <stdio.h>
#include <unistd.h>
#define	NB	12
char base[] = "ABCDEF0123456789";

void fonction(char tab[NB + 1], int rank) {
    int i;
    if (rank <= NB) {
        for (i = 0; base != '\0'; i++) {
            tab[rank] = base;
            fonction(tab, rank + 1);
        }
        for (i = 0; i < NB; i++)
            write(1, &tab, 1);
        write(1, "\n", 1);
    }
}

int main() {
    char tab[NB + 1];
    int i;
    for (i = 0; i < NB; i++)
        tab = base[0];
    fonction(tab, 0);
    return (0);
}

لكن بإلغاء التكرار و تطوير الخوارزمية السابقة, سيكون البرنامج أسرع بكثير (الملف التنفيذي في المرفقات باسم NumberOfPermutation_2) :

#include <stdio.h>
#define echanger(a, b)  do {int temp=(a); (a)=(b); (b)=temp;} while (0)

char *suivant(char *p, int n) {
    int i, j = n - 1, k = n - 1;
    while (k > 0 && p[k - 1] > p[k])
        k--;
    if (k != 0) {
        while (p[j] < p[k - 1])
            j--;
        echanger(p[k - 1], p[j]);
        for (i = k, j = n - 1; i < j; i++, j--)
            echanger(p, p[j]);
    }
    return k == 0 ? 0 : p;
}

int main() {
    char mot[] = "ABCDEF";
    size_t nb_lettres = (sizeof mot / sizeof *mot) - 1;
    do
        printf("%s\n", mot); while ((suivant(mot, nb_lettres)) != 0);
    return 0;
}

يُمكننا تطوير الخوارزمية السابقة لتصبح أسرع و أقل تكلفة (راجع Knuth, tome 3), الملف التنفيذي في المرفقات باسم NumberOfPermutation_3 :

#include <stdio.h>
#define echanger(a, b)  do {int temp=(a); (a)=(b); (b)=temp;} while (0)

void perm(char *t, int n, int k) {
    int i;
    if (k == n - 1)
        printf("%s\n", t);
    else
        for (i = k; i < n; i++) {
            echanger(t[k], t);
            perm(t, n, k + 1);
            echanger(t, t[k]);
        }
}

int main() {
    char t[] = "ABCDEF";
    perm(t, sizeof t / sizeof *t - 1, 0);
    return 0;
}

توجد مقالة رائعة جدا للدكتور James McCaffrey بعنوان Série de tests: Permutations de chaînes, يمكنك الإطلاع عليها من خلال الرابط التالي:

Série de tests: Permutations de chaînes

فكرة جيدة, أعتقد أن الكود سيكون أسرع هكذا :

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

void faire_combi(char * str, char * tmp, int len, int ind) {
    int i;
    if (ind >= len) {
        puts(tmp);
        return;
    }
    for (i = 0; i < len; i++) {
        if (str > 0) {
            char pt = str;
            str = -1;
            tmp[ind] = pt;
            faire_combi(str, tmp, len, ind + 1);
            str = pt;
        }
    }
}

void combinaisons(char * str) {
    int len = strlen(str);
    char * tmp = (char*) malloc(len + 1);
    tmp[len] = '\0';
    faire_combi(str, tmp, len, 0);
    free(tmp);
}

int main() {
    char str[] = "ABCDEF";
    combinaisons(str);
    return 0;
}

hassan9599@

خذ إحدى الخوارزميات الثلاثة السابقة, ستكفيك.

أخيرا, ما رأيكم في تحويل الموضوع إلى نقاش فى بعض خوارزميات التبديل المتقدمة مثل خوارزمية Kenneth Rosen أو Addison-Wesley.

NumberOfPermutation_1.rar

NumberOfPermutation_2.rar

NumberOfPermutation_3.rar

تمام اخي احمد ولكن البرامج لا تحفظ العمل ولا يوجد زر للتوقف

أحمد الشنقيطي كتب:

هل تعتقد أن إدراج أوامر أسمبلي في كود C/C++ (باستخدام asm مثلا) سيزيد من سرعة البرنامج ؟

مثال ؟

هذا سطر من أحد برامجك السابقة، وفيه التمثيل بالأسمبلي بالنتيجة

        ;for (i = k; i < n; i++) {
00F913F9  mov         eax,dword ptr [k] 	; 1 clk
00F913FC  mov         dword ptr ,eax 	; 1 clk
00F913FF  jmp         perm+5Ah (0F9140Ah) 	; 1 clk
00F91401  mov         eax,dword ptr  	; 1 clk
00F91404  add         eax,1 			; 1 clk
00F91407  mov         dword ptr ,eax 	; 1 clk
00F9140A  mov         eax,dword ptr  	; 1 clk
00F9140D  cmp         eax,dword ptr [n] 	; 2 clk
00F91410  jge         perm+0D1h (0F91481h)	; 1 clk
	  ; do something
	  jmp         00F913F9			; 1 clk
00F91481  ...
--------------------------------------------------------
						; 11 clk

بينما في الأسمبلي فأنت تتعامل على مستوى مجرد أكثر

مثلاً أنا وجدت أني لا أحتاج للاحتفاظ بقيمة المتغير i

فلماذا أحجز له dword في الذاكرة وفي كل مرة أقرأ وأكتب القيمة فيها؟ ببساطة أستخدم المسجل eax بدلاً عن حجز مكان في الذاكرة وعندما أنتهي منه فلا تهمني القيمة فيه.

أيضاً n و k لا أحتاج لتمريرها كقيم في الذاكرة وإنما أمرر القيم في المسجلات، وأوفر أيضاً 1 clock.

        ;for (i = k; i < n; i++) {
	mov	eax, dword ptr [k]		; 1 clk
	jmp	@F				; 1 clk
_loop:	inc	eax				; 1 clk
@@:	cmp	eax, dword ptr [n]		; 2 clk
	jge	_end				; 1 clk
	; do something
	jmp	_loop				; 1 clk
_end
--------------------------------------------------------
						; 7 clk

	; ESI = n, passed to func
	; EDI = k, passed to func
        ;for (i = k; i < n; i++) {
	mov	eax, edi
	jmp 	@F
_loop:	inc	eax
@@:	cmp	eax, esi			; 1 clk
	jge	_end
	; do something
	jmp	_loop
_end
--------------------------------------------------------
						; 6 clk

            echanger(t[k], t);
01021412 8B 45 08         mov         eax,dword ptr [t] 
01021415 03 45 10         add         eax,dword ptr [k] 
01021418 0F BE 08         movsx       ecx,byte ptr [eax] 
0102141B 89 4D EC         mov         dword ptr [temp],ecx 
0102141E 8B 45 08         mov         eax,dword ptr [t] 
01021421 03 45 10         add         eax,dword ptr [k] 
01021424 8B 4D 08         mov         ecx,dword ptr [t] 
01021427 03 4D F8         add         ecx,dword ptr  
0102142A 8A 11            mov         dl,byte ptr [ecx] 
0102142C 88 10            mov         byte ptr [eax],dl 
0102142E 8B 45 08         mov         eax,dword ptr [t] 
01021431 03 45 F8         add         eax,dword ptr  
01021434 8A 4D EC         mov         cl,byte ptr [temp] 
01021437 88 08            mov         byte ptr [eax],cl 
01021439 33 C0            xor         eax,eax 
0102143B 75 D5            jne         perm+62h (1021412h)

				; edi = k
mov	esi, eax		; esi = i
mov	ebx, dword ptr [t]	; ebx = t
mov	al, byte ptr [ebx+edi]
mov	ah, byte ptr [ebx+esi]
mov	byte ptr [ebx+esi], al
mov	byte ptr [ebx+edi], ah

قس على ذلك على باقي أجزاء البرنامج، وبما أن البرنامج سيقوم بتنفيذ عملية طويلة جداً فالفرق الزمني المختصر سيكون كبير أيضاً.

اقتباس

تمام اخي احمد ولكن البرامج لا تحفظ العمل ولا يوجد زر للتوقف

البرنامج يعرض الإحتمالات الممكنة على الشاشة فقط, يُمكنك استبدال printf بــ fprintf لحفظ المعلومات في ملف نصي كما فعلتُ سابقا.

بالنسبة لزر التوقف, فالكود مكتوب في بيئة الــ Console لذا لن تجد أزراراً أو ما شابه, لكن يُمكنك كتابة الكود في بيئة الــ GUI إن أردت, فالخوارزميات جاهزة لديك ! :)

اقتباس

بما أن البرنامج سيقوم بتنفيذ عملية طويلة جداً فالفرق الزمني المختصر سيكون كبير أيضاً.

هذا ما كنت أتوقعه, حتى لو أدرجنا بعض أوامر الأسمبلي في كود C/C++ فعقبة السرعة ستظل موجودة ..

لكن أعتقد أن تنفيذ كود الأسمبلي على جهاز يملك عدة معالجات "سريعة" سيُحدث فرقا زمنيا ملحوظا.

أحمد الشنقيطي كتب:

هذا ما كنت أتوقعه, حتى لو أدرجنا بعض أوامر الأسمبلي في كود C/C++ فعقبة السرعة ستظل موجودة ..

طبيعي، ولكن بالنهاية السرعة التي ستحصل عليها من تنفيذ كود C/C++ ستكون أقل بضعفين أو أكثر من السرعة التي ستحصل عليها من التنفيذ بأوامر أسمبلي.

وهذا الفرق ليس بقليل.

أحمد الشنقيطي كتب:

لكن أعتقد أن تنفيذ كود الأسمبلي على جهاز يملك عدة معالجات "سريعة" سيُحدث فرقا زمنيا ملحوظا.

الأسمبلي قادرة على إحداث فرق ملحوظ في السرعة بكافة الظروف :lol: أنت بكلامك هذا لا تعطيها قدرها!

اقتباس

An old joke goes something like this:"There are three reasons for using assembly language: speed, speed, and more speed."

لنحسب عدد الاحتمالات ببساطة:

|solution space| = 16^12 = 281474976710656
for each solution, we have 12 digits.
Lets assume that each digit is represented with one byte only for simplicity.
solution space size = 281474976710656 * 12 Bytes
                    = 3377699720527872 Bytes
                    = 3298534883328 KiB
                    = 3221225472 MiB
                    = 3145728 GiB

أود أن أرى من لديه ثلاثة ملايين GiB لتخزين كل الاحتمالات :sad:

إن كان المطلوب هو إنتاج عينات عشوائية من هذا المجال, فالموضوع يتم ببساطة عن طريق uniform distributed random number في الحالة البسيطة إن كانت جميع الاحتمالات متساوية في الأهمية. أما محاولة إنتاجها و تخزين كل الاحتمالات, فهو أمر غير ممكن على الأقل بالتكنلوجيا المتوفرة.

إذا, لا يمكن رؤية جميع الإحتمالات إلا في الحواسيب الفائقة (Supercomputer) ؟

أو أن يكون لديك ~3000 مستخدم كل واحد يستخدم 1 تيرا بايت على الأقل لتخزين جزء من النتائج.

إذا, أنصح الأخ hassan9599 بالتخلي عن الفكرة إلى حين شراء حاسوب فائق .. أو امتلاك أكثر من 3000 مستخدم كل واحد يستخدم 1 تيرا بايت !! :wacko:

انا احتاج هذة الاحتمالات لكسر شفرات القنوات والشفرات تعتمد علي خوارزمية

يعني الشفرة مستحيل تبقي زي كدة 000000000000 او 000000000100

ممكن تبقي زي كدة 6DE5729A3850

فأنا احتاج برنامج يصنع الاحتمالات الخوارزمية بهذة الشكل 6DE5729A3850

وليس بهذا الشكل 000000000000 او 000000000100

اقتباس

اين البرنامج يا اخوان

هذا مثال باستخدام Cpp11, فقط قم بتغيير numbers_count لتنتج العدد الذي تريده من الأعداد العشوائية. استخدمت g++ 7.1 لترجمة البرنامج:

#include <cstdint>
#include <cstddef>
#include <fstream>
#include <iomanip>
#include <random>

int main(){
    // specify the min/max range of the vouchers we want to generate
    const std::uint64_t min = 0x0ul, max = 0xfffffffffffful;
    // specify how many vouchers we want to generate, and the width
    // of the vouchers when represented in text
    const std::size_t numbers_count = 1000000, field_width = 12;
    std::random_device seed;
    std::mt19937_64 engine(seed());
    std::uniform_int_distribution<std::uint64_t> range(min, max);
    auto rnd = [&](){ return range(engine); };
    std::ofstream output("output.txt");
    output << std::hex << std::setfill('0');
    for(std::size_t i = 0; i < numbers_count; ++i)
        output << std::setw(field_width) << rnd() << '\n';       
}

اقتباس

انا احتاج هذة الاحتمالات لكسر شفرات القنوات والشفرات تعتمد علي خوارزمية

يعني الشفرة مستحيل تبقي زي كدة 000000000000 او 000000000100

ممكن تبقي زي كدة 6DE5729A3850

فأنا احتاج برنامج يصنع الاحتمالات الخوارزمية بهذة الشكل 6DE5729A3850

وليس بهذا الشكل 000000000000 او 000000000100

الأفضل أن تُحاول كسر الخوارزمية لتختصر عليك الطريق و إلا فسيلزمك تجربة أكثر من Belliard احتمال ..! و قد يستغرق هذا منك عدة أشهر إن لم تكن سنوات.

بالنسبة للكسر فأعتقد أنه يُخالف قوانين المنتدى.

اقتباس

هذا مثال باستخدام Cpp11, فقط قم بتغيير numbers_count لتنتج العدد الذي تريده من الأعداد العشوائية. استخدمت g++ 7.1 لترجمة البرنامج

جميل جدا أخي خالد, ممكن ترفق لنا الملف التنفيذي لأنني أملك النسخة 3.4 من g++.

طيب هل يمكن احد يصنع لي ملف تكست يحتوي علي عدد كبير من الارقام والحروف معا وليس ارقام فقط او حروف فقط

أخي حسان, لا تجعل السؤال طريقك للتعلم !

الموضوع يحتوي على العديد من الخوارزميات التي يمكنها حل مشكلتك, اختر واحدة منها و أضف إليها بعض التعديلات حتى تُناسب رغباتك.

يُغلق الموضوع.