قبل از هر چیزی تعریفی دقیقی از جایگشت ها (permutation ) را باید بدانیم که در زیر ارائه  شده است.

یک جایگشت (خطی) عبارت است ازهرترتیب قرار گرفتن کلکسیونی از اشیا ( بصورت خطی)  بوجود می آید.

در اینجا به کلمه ی ” خطی ” دقت شود زیرا جایگشت دیگری نیز به نام جایگشت دوری داریم که در آن اشیا بصورت دایره ای قرار میگیرند و  کلمه ی ” خطی ” در تقابل با مفهوم جایگشت دوری آمده است. الگوریتم این برنامه  را با مثال توضیح میدهیم.

جایگشتهای مجموعه ی {a,b,c,d,e} برابرند با اجتماع مجموعه های زیر:

a و جایگشتهای مجموعه ی {b,c,d,e}

b و جایگشتهای مجموعه ی{a,c,d,e}

c و جایگشتهای مجموعه ی {a,b,d,e}

d و جایگشتهای مجموعه ی {a,b,c,e}

e و جایگشتهای مجموعه ی {a,b,c,d}

پس در هر مرحله یک عضو از مجموعه (در این جا یک کاراکتر از کل رشته ) را انتخاب میکنیم و با جایگشت بقیه ی اعضا در نظر میگیریم اما از آنجایی که برای تمام اعضای مجموعه این کار باید انجام شود این کار با یک حلقه ی for و تعویض هر عضو مجموعه با اولین عضو انجام میدهیم.

تابع بازگشتی برای انجام این الگوریتم بصوریت بازگشتی بوده و ۳ آرگومان دارد اولی خود رشته (مجموعه) است , دومی کاراکتری (عضوی از مجموعه) است که در هر مرحله

جایش را با کارکتر های (اعضای) بعد از خود عوض میکند و هنگام فراخونی اولیه تابع در این آرگومان صفر قرار میگیرد و آرگومان سوم  ایندکس آخرین کاراکتر (عضو) است چون لازم است که در چه مرحله ای به کاراکتر (عضو) آخر برای فراخوانی دوباره میرسیم.

و این هم کد برنامه جایگشت ها ی (permutation ) یک مجموعه با زبان برنامه نویسی سی پلاس پلاس ( ++C )  ::

#include <iostream>
#include <string>
using namespace std;
void per(string s,int k,int n)
{
    if(k==n)
    {
        cout<<s<<endl;
    }
    else
    {
        for(int i=k;i<=n;i++)
        {
            char c=s[i];
            s[i]=s[k];
            s[k]=c;
            per(s,k+1,n);
        }
    }
}
int main(void)
{
    string s;
    cout<<"\t\t\t\tPermutation"<<endl<<endl;
    cout<<"Enter the string: ";
    cin>>s;
    per(s,0,s.size()-1);
    cin.get();
    return 0;
}