الگوریتم پیدا کردن زیر دنباله های یک دنباله

[vahid javani]

سلام
دنباله ‎ [1,2,3] ‎ را در نظر بگیرید. این دنباله ‎ 6 زیر دنباله متفاوت دارد: 1 و 2 و 3 و 1,2 و 2,3و 1,2,3
تو مسابقه برنامه نویسی بیان به این سوال بر خوردم!
چیزی در این مورد نتونستم پیدا کنم اگه امکان داره راهنماییم کنید.

اگه معادل انگلیسی این نوع الگوریتم ها رو هم می دونید بیزحمت بگید، دوست دارم بیشتر در موردش تحقیق کنم.

[diapason]

سلام
چیزی که شما دنبالش هستید، همان ترکیب (Combination) و جایگشت (Permutation) در ریاضیات است. البته چون در زیردنباله های شما تکرار وجود ندارد، همان ترکیب.
تعداد روش های انتخاب r شیء از n شیء (جایگشت).
P(n,r)=n!/(n-r)!
مثلن برای تعیین تعداد مجموعه های 2 عضوی از مجموعه بالا خواهد شد
P(3,2)=3!/(3-2)!
=[1,2] 1,3],[2,3],[2,1],[3,1],[2,1]
در صورتی که تکرار مجاز زیر دنباله ها نباشد (بدون جایگشت):
C(n,r)=n!/[(r!)*(n-r)!]
C(n,r)=3!/(3-2)!
=[1,2] 1,3],[2,3]
حالا در سوال شما مجموع ترکیب های ممکن از 1 تا n عضوی از مجموعۀ n عضوی مطرح شده است که نیاز به یک سیگما هم پیدا میکنید تا تعداد ترکیب های به دست آمده برای 1 از 3، 2 از 3 و 3 از 3 را با هم جمع کند.

[vahid javani]

سلام
چیزی که شما دنبالش هستید، همان ترکیب (Combination) و جایگشت (Permutation) در ریاضیات است. البته چون در زیردنباله های شما تکرار وجود ندارد، همان ترکیب.
تعداد روش های انتخاب r شیء از n شیء (جایگشت).
P(n,r)=n!/(n-r)!
مثلن برای تعیین تعداد مجموعه های 2 عضوی از مجموعه بالا خواهد شد
P(3,2)=3!/(3-2)!
=[1,2] 1,3],[2,3],[2,1],[3,1],[2,1]
در صورتی که تکرار مجاز زیر دنباله ها نباشد (بدون جایگشت):
C(n,r)=n!/[(r!)*(n-r)!]
C(n,r)=3!/(3-2)!
=[1,2] 1,3],[2,3]
حالا در سوال شما مجموع ترکیب های ممکن از 1 تا n عضوی از مجموعۀ n عضوی مطرح شده است که نیاز به یک سیگما هم پیدا میکنید تا تعداد ترکیب های به دست آمده برای 1 از 3، 2 از 3 و 3 از 3 را با هم جمع کند.

ممنون از پاسختون
من الگوریتم های ترکیب و جایگشت رو چک کردم ولی چیز درست و حسابی پیدا نکردم!

[diapason]

ممنون از پاسختون
من الگوریتم های ترکیب و جایگشت رو چک کردم ولی چیز درست و حسابی پیدا نکردم!

وای!!!!! عذر خواهی میکنم. من روی تعدادش فکر می کردم. الان متوجه شدم منظور شما تعدادش نبوده و خود زیردنباله ها بودن :ناراحت:. ولی خوب حداقل فعلا تعداد زیردنباله ها را دارید
اما در هر صورت مربوط به الگوریتم پیدا کردن تمام ترکیب ها خواهد شد.
نمونه بحث:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117/Combinations-in-C.htm