تشخیص جایگشت از روی جایگشت قبلی - هفت خط کد انجمن پرسش و پاسخ برنامه نویسی

وبـــلاگ هــفت خــط کــد


آموزش های برنامه نویسی
۱۶۹ نفر آنلاین
۰ عضو و ۱۶۹ مهمان در سایت حاضرند

تشخیص جایگشت از روی جایگشت قبلی

+2 امتیاز
90 بازدید
چطوری میشه از روی یک جایگشت از اعداد 1تاn جایگشت بعدی رو فهمید.

مثلاً:

ورودی:  123

خروجی: 132
سوال شده شهریور 14, 1393  بوسیله ی Amin (امتیاز 804)   2 8 43
نه اینطوری نمیشه ...
چون باید توی وکتور !n رشته ذخیره بشه برای n های بیش از یکی دو رقم خیلی بزرگ میشه ؟
شنیدم یه تابع تو c++ داره ولی الگوریتمشو نمی دونم ( next permutation)
نحوه پیاده سازیش این جا هست http://en.cppreference.com/w/cpp/algorithm/next_permutation
template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
 
    while (1) {
        BidirIt i1, i2;
 
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}
الگوریتم هم این جا :
http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l greater than k such that a[k] < a[l].
Swap the value of a[k] with that of a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

لطفا وارد شوید یا ثبت نام کنید برای جواب دادن به این سوال.

...