[Project Euler]التقليب المعجمي

و عليكم السلام و رحمة الله و بركاتهبصراحة هذا الموضوع " المجموعات الجزئية " كنت أفكر فيه من فترة , لكنني لم أتفرغ كليا ً لدراسته . هذه محاولاتي بلغة السي ++ و لكننها غير صحيحة .

#include "stdafx.h"
#include<iostream>
#include<vector>
using namespace std;
long f(int x)
{
long p=1;
for(int i=2;i<=x;i++)
{
  p*=i;
}
return p;
}
void main()
{
int r;
const int n=4;
int a[n]={1,2,3,4};

cin>>r;

long size=f(n)/(f(r)*(f(n-r)));

for(int i=0;i<size;i++)
{

  int c=i;
  int s=0;
  while(c>=n)
  {
   c-=n;
   s++; 
  }
  cout<<"[ "<<a[c];

  for(int j=1;j<r;j++)
  {
   int z=i+j+s;
   while((z)>=n)
   {
	z-=n;
   }
   cout<<","<<a[z];
  }
  cout<<" ]"<<endl;
}
int ii;cin>>ii;
}

لذا أعدت التفكير وقتها إلى طريقة أخرى و هي طريقة التفكير الإنساني

و مثلما قلت لن أعتمد على قانون التوافيق " لكنني سأتسخدمه " و هذه خربشات حلي

اقتباس

في حال n=7

r=3

1 2 3 4 5 6 7

size*r/n

1 2 3 ==5 === size/r

1 2 4

1 2 5

1 2 6

1 2 7

1 3 4 ==4

1 3 5

1 3 6

1 3 7

1 4 5 ==3

1 4 6

1 4 7

1 5 6 ==2

1 5 7

1 6 7 ==1

=====15

12

13

14

15

16

17

=====6

@HGB: سؤالي مختلف, ما احاول عمله هو: استخدام جميع الحروف لكن تبديل اماكنهم فى كل مرة, كما هو فى السؤال 24 فى Project Euler.

هناك 6 احتمالات ل"012" و هي:

012
021
102
120
201
210

عدد الإحتمالات الممكنة هو مضروب n

n! factorial of n

YaSeenTA كتب:

عدد الإحتمالات الممكنة هو مضروب n

n! factorial of n

هذا ما اعنيه ! لكن كيف يتم توليد هذه الاحتملات ؟

- اعتدت علي طريقة لتوليد هذه الاحتملات:

a = '012'
for i in range(0,len(a)):
 for j in range(0,len(a)):
  for k in range(0,len(a)):
   print a + a[j] + a[k]

لكن هذه الطريقة تولد احتملات بها حروف مكررة مثل:

011
020
022
100
110
111
112
121
122
200
202
211
212
220
221
222

كود جافا:

int i = 0;
for (int i0 = 0; i0 < 10; i0++) {
    for (int i1 = 0; i1 < 10; i1++) {
        if (i0 == i1) continue;
        for (int i2 = 0; i2 < 10; i2++) {
            if (i0 == i2 || i1 == i2) continue;
            for (int i3 = 0; i3 < 10; i3++) {
                if (i0 == i3 || i1 == i3 || i2 == i3) continue;
                for (int i4 = 0; i4 < 10; i4++) {
                    if (i0 == i4 || i1 == i4 || i2 == i4 || i3 == i4) continue;
                    for (int i5 = 0; i5 < 10; i5++) {
                        if (i0 == i5 || i1 == i5 || i2 == i5 || i3 == i5 || i4 == i5) continue;
                        for (int i6 = 0; i6 < 10; i6++) {
                            if (i0 == i6 || i1 == i6 || i2 == i6 || i3 == i6 || i4 == i6 || i5 == i6) continue;
                            for (int i7 = 0; i7 < 10; i7++) {
                                if (i0 == i7 || i1 == i7 || i2 == i7 || i3 == i7 || i4 == i7 || i5 == i7 || i5 == i7 || i6 == i7) continue;
                                for (int i8 = 0; i8 < 10; i8++) {
                                    if (i0 == i8 || i1 == i8 || i2 == i8 || i3 == i8 || i4 == i8 || i5 == i8 || i5 == i8 || i6 == i8 || i7 == i8) continue;
                                    for (int i9 = 0; i9 < 10; i9++) {
                                        if (i0 == i9 || i1 == i9 || i2 == i9 || i3 == i9 || i4 == i9 || i5 == i9 || i5 == i9 || i6 == i9 || i7 == i9 || i8 == i9) continue;
                                        i++;
                                        if (i == 1000000) {
                                            System.out.println(i0 + "" + i1 + "" + i2 + "" + i3 + "" + i4 + "" + i5 + "" + i6 + "" + i7 + "" + i8 + "" + i9);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

عدد الاحتمالات هو مضروب n لان ما تحسبه هو nPn

التوليد بسيط جدا

ابسط وابطء طريقه ممكنه , هى طريقه ملىء الساعه

بمعنى كل واحد منهم له ترتيب فى مصفوفه ,, كل دوره انت تبدء من اخر خانه على اليمين تزيدها واحد واذا كانت وصلت للبدايه ,, تريد الخانه التى تليها واحد وهكذا

فى كل مره لابد ان تتحقق من التكرار وان وجد ,, زد واحد مره اخرى

الطريقه الاسرع هى ان تستنتج التتابع الذى يتم ملىء الخانات به ,, هذا سيجعلك تستطلع ملىء كل خانه بالاعتماد على ما قبها ,, استنتاجها ليس صعب فقط اكتب اكتر من واحده امامك

ما هو ابسيط ان تولدهم بتكرارهم (بمعنى مثلا فى ال 012 تبدا من 000 ) ,, هنا طريقه التتابع سهله جدا جدا ,, بعد ذلك تشبط ما يحتوى على تكرارات وتطبع ما لا يحتوى .. بطيئه فعلا وسهله فعلا

                                        if (i == 1000000) {
                                            System.out.println(i0 + "" + i1 + "" + i2 + "" + i3 + "" + i4 + "" + i5 + "" + i6 + "" + i7 + "" + i8 + "" + i9);
                                        }

بارك الله فيك أخى الفاضل ، ولكن من أين جاءت هذه الــ 1000000؟ وما فائدتها؟ ولماذا تضع جملة الطباعة داخل الجملة الشرطيه؟

اعتقد كده لن يطبع الا أخر قيمة للمتغيرات التى استخدمتها حضرتك !!!

المطلوب في المسألة الأصلية في مشروع أولر

اقتباس

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

بالطبع يمكن إضافة break بعد الطباعة ... لكنها لن تستغرق سوى بضع أجزاء من الثانية بكل حال

Speed_Of_Light كتب:

المطلوب في المسألة الأصلية في مشروع أولر

بالطبع يمكن إضافة break بعد الطباعة ... لكنها لن تستغرق سوى بضع أجزاء من الثانية بكل حال

بارك الله فيك وبارك لك. كنت أظنك تريد القيام بتوليد كل الاحتمالات الممكنة ،،،

بهذه الطرق لو كنا نحتاج أن نبدل في 20 خانة كل الإحتمالات سنحتاج ل 20 حلقة تكرار ؟

كيف يمكن أن ننجز 20 خانة ونبدل فيها الإحتمالات بحلقة تكرار واحدة فقط .. وبدون جمل if ؟

حسناً تلك الطريقة السريعة القذرة (quick and dirty) للقيام بالأمر :D

بالطبع يمكن القيام بالموضوع بطريقة "أنظف" وأكثر عمومية

لاحظ أننا استخدمنا أصلاً كل الأرقام العشرية المتاحة ... لكن لنقرض أن المسألة كانت لترتيب رموز وليس أرقام ... يمكن استخدام الحل العام التالي:

// A generic solution for problem #24
public class p024 {

	// Original Problem
    static char[] DIGITS = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

	// Extended Problem
//    static char[] DIGITS = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

    static boolean[] picked = new boolean[DIGITS.length];
    static int[] values = new int[DIGITS.length];
    static int depth = -1;
    static int o = 0;

    public static void main(String[] args) {
        pick();
    }

    static void pick() {
        depth++;
        for (int i = 0; i < picked.length; i++) {
            if (!picked) {
                picked = true;
                values[depth] = i;
                pick();
                if (depth == picked.length - 1) {
                    o++;
                    if (o == 1000000) {
                        print();
                    }
                }
                picked = false;
            }
        }
        depth--;
    }

    static void print(){
        for(int val : values){
            System.out.print(DIGITS[val]);
        }
    }
}

Speed_Of_Light كتب:

حسناً تلك الطريقة السريعة القذرة (quick and dirty) للقيام بالأمر :D

بالطبع يمكن القيام بالموضوع بطريقة "أنظف" وأكثر عمومية

لاحظ أننا استخدمنا أصلاً كل الأرقام العشرية المتاحة ... لكن لنقرض أن المسألة كانت لترتيب رموز وليس أرقام ... يمكن استخدام الحل العام التالي:

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

عذراً على عدم التوضيح ...

لقد استخدمت جافا :D

الفكرة تقوم على تعليم/mark القيم التي تم اختيارها لضمان عدم تكرار احتيارها

استخدامت 3 مصفوفات:

الأولى DIGITS مصفوفة من الأحرف تعبر عن مجموعة الرموز المستخدمة في التقليب المعجمي

الثانية picked مصفوفة من القيم المنطقية لتعليم/تمييز/mark القيم التي تم اختيارها

الثالثة values مصفوفة قيم رقمية تعبر عن رقم الرمز الذي تم اختياره

نقوم الدالة pick باختيار قيمة ما لم يتم اختيارها مسبقاً ووضعها في المصفوفة values وتستخدم المتحول الرقمي depth لتحديد مكان تخزين الرقم في المصفوفة values

كما تقوم باستدعاء الدالة print لطباعة التقليب المعجمي الذي تبحث عنه (هنا 1000000)، وذلك عند اختيار مجموعة كاملة من التقليبات المعجمية (أي عند امتلاء المصفوفة values)

بسيطة أليس كذلك :D

لتجربة المسألة على رموز أكثر من المسألة الأصلية (من 0 إلى 9) يمكنك استخدام المصفوفة DIGITS المكتوبة كتعليق (مسبوقة بـ //)

أو قم بكتابة مجموعة الرموز التي تريدها فيها

السلام عليكم :

طريقة حلى لهذه المساله كالتالى

عدد الاحتمالات المتاحه لعشرة ارقام هى مضروب 10

نحدد index كل خانه من الرقم المطلوب ابتداء من اقصى اليسار من خلال الطريقه التاليه

اولا :الرقم المراد ايجاده هو التبديل رقم 1000000 =number

عند وضع الخانه العاشره باول رقم وهو 0 فان عدد التباديل التى سيتم عملها مع 0 هو عدد تباديل الخانات التسع المتبقيه اى 1*مضروب 9

وعند وضع الخانه العاشره بثانى رقم وهو 1 فان عدد التباديل التى قد تم عملها هو عدد التباديل مع 0 وعدد التباديل مع 1 اى 2*مضروب 9

وهكذ فى كل مره يكون عدد التباديل التى تم عملها هو index *fact of remaining digits

فى كل مره نزود ال index حتى يكون

index *fact of remaining digits >= number

بعد تحديد ال index يكون عدد التباديل التى تم عملها هو index -1 *fact of remaining digits

نطرح قيمة التباديل التى تم عملها من number ثم ننتقل للخانه التاليه بنفس الطريقه حتى اخر خانه

بعد الانتهاء من تحديد index كل خانه نجد قيمتها من المصفوفه الممتلئه بالارقام من 0 الى 9 وكل خانه يتم اخذ قيمتها نحذفها

وده كود كتبته بالسى شارب والرقم الناتج جربته على project Euler وكان الرقم الناتج هو الحل الصحيح والرقم هو 2783915460

   public int fact(int num)
        {
            int result = 1;
            for (int i = num; i > 1; i--)
            {
                result *= i;
            }
            return result;
        }

        private void button1_Click(object sender, EventArgs e)
        {
            List<int> lindex = new List<int>();
            List<int> values = new List<int>();
            int number = 1000000;
            int num, factorial = 0;
            string value = string.Empty;
            for (int i = 9; i >= 0; i--)
            {
                factorial = fact(i);
                for (int j = 1; j <= i + 1; j++)
                {
                    num = factorial* j;
                    if (num >= number)
                    {
                        num -= fact(i);
                        number -= num;
                        lindex.Add(j);
                        break;
                    }
                }
                values.Add(9 - i); 
            }
            for (int i = 0; i < 10; i++)
            {
                value += values[lindex - 1].ToString();
                values.RemoveAt(lindex - 1);

            }
            MessageBox.Show("millionth lexicographic permutation is\t"+value);
        }