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

Question

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

مثلاً:

ورودی:  123

خروجی: 132

Comments

من نفهمیدم منظورتو یعنی می خواهی تمام جایگشت های عدد رو پیدا کنی ؟‌

---

فرض کن همه ی جایگشت های 1تا n را به ترتیب الفبایی نوشتیم...
تابع ما یکی از این !n می گیره و جایگشت بعدی رو در خروجی میده ...

---

اگر همه به ترتیب نوشته شده باشن و توی پیدا کردن همه حالت ها مشکلی نداشته باشید راحته
  مثلا اگر همه بترتیب داخل یک وکتور ذخیره کرده باشی کافیه  عدد مورد نظر رو داخل این وکتور جست و جو کنی (با binary search ) بعد بیای عنصری که داخل خونه بعد از محل مورد نظر هست رو برگردونی

---

نه اینطوری نمیشه ...
چون باید توی وکتور !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].