جایگشت بیت-واژگون‌گر

در ریاضیات کاربردی، جایگشت بیت-واژگون‌گر جایگشتی است که از اعضای یک دنباله عضوی به دست می‌آید که در آن است. این جایگشت یه این شکل به دست می‌آید که ابتدا اعضای دنباله اصلی را با اعداد تا اندیس‌دهی می‌کنیم و سپس اندیس هر عضو را از نظر دودویی واژگون می‌کنیم. (با این فرض که همه اعداد دقیقاً دارای بیت هستند) در نهایت هم هر عضو را با توجه به اندیسی که گرفته در جایگشت جواب قرار می‌دهیم. یکی از ویژگی‌های مهمی هم که این عملیات دارد این است که پیج است. یعنی اگر دو بار این عملیات را روی حایگشت اعمال کنیم در نهایت به جایگشت اولیه می‌رسیم.Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions, Hachette UK, 2014 ISBN 1-4721-1622-4.

 مثال 
جایگشت ۸ عضوی را در نظر بگیرید، در این مثال و است و زمانی که الگوریتم را روی آن اجرا کنیم نتیجه جایگشت است. برای دیدن بهتر این دنباله هم در مثال‌های بیشتر می‌توانید به این‌جا مراجعه کنید.Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), "In-place permuting and perfect shuffling using involutions", Information Processing Letters, 113 (10–11): 386–391

 تعمیم‌دادن 
عملیات قبلی که روی جایگشت اعمال می‌شد فقط برای جایگشت‌هایی بود که اندازه آن‌ها است، اما با این تعمیم می‌توان آن را برای جایگشت‌هایی که طول آن‌ها است انجام داد. (باید شرط را داشته‌باشیم) نحوه انجام عملیات برای این جایگشت‌ها به این گونه است که اندیس‌ها را در مبنای می‌نویسیم و سپس هر اندیس را وارونه می‌کنیم. (طول همه اندیس‌ها در نظر گرفته می‌شود و اگر این گونه نبودند به ابتدای آن‌ها صفر اضافه می‌شود) حال هر عضو را با توجه به اندیس جدیدی که گرفته‌است در دنباله جدید قرار می‌دهیم. هم‌چنین این عملیات مانند حالت قبلی پیج است و اگر دو بار آن را روی یک جایگشت اعمال کنیم دوباره به جایگشت اولیه می‌رسیم.doi:10.1007/s11075-017-0356-3 Gordon, Dan (ژوئن ۲۰۱۷). "A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates". Numerical Algorithms. 77 (4): 1141–1157

 کاربردها 
این الگوریتم در حالتی که باشد در الگوریتم FFT کاربرد دارد و اگر این کار را به صورت درجا دهیم باعث می‌شود این الگوریتم حافظه کم‌تری مصرف کند و زمان اجرا آن هم کم‌تر بشود. برای اجرای این الگوریتم به صورت درجا هم می‌توان به ازای اعدادی که وارون آن‌ها از خودشان کم‌تر است، با وارون‌شنان جابه‌جا کنیم و در انتها دنباله‌ای را که به دست می‌آید را به عنوان خروجی الگوریتم داد. زمان اجرای این الگوریتم هم  است و حافظه اضافی هم ندارد.Jeong, Jechang; Williams, W.J. (1990), "A fast recursive bit-reversal algorithm", International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90), 3, pp. 1511–1514, doi:10.1109/ICASSP.1990.115695

 پیاده‌سازی 
در این بخش می‌توانید پیاده‌سازی این الگوریتم را با استفاده از زبان پایتون مشاهده کنید که در زمان خطی اجرا می‌شود و طبق الگوریتم گفته شده در قسمت قبل است.import math

def reverse(x, base, len):
    num = []
    for i in range(len):
        num.append(x % base)
        x //= base
    ans = 0
    for value in num:
        ans = ans * base + value
    return ans

def get_bit_reversal(input_array, base):
    for i in range(len(input_array)):
        reversed = reverse(i, base, math.log(len(input_array), base))
        if reversed <i:
            tmp = input_array[i]
            input_array[i] = input_array[reversed]
            input_array[reversed] = tmp
    return input_arrayدر این کد ابتدا با استفاده از تابع reverse عدد داده‌شده را برعکس می‌کنیم و سپس در تابع اصلی خروجی الگوریتم را محاسبه و برمی‌گردانیم.

 جستارهای وابسته 
 الگوریتم درجا
 جایگشت
 دنباله

 منابع 

رده:الگوریتم‌های تبدیل سریع فوریه
رده:الگوریتم‌های ترکیبیاتی
رده:جایگشت‌ها