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

در ریاضیات کاربردی، جایگشت بیت-واژگون‌گر جایگشتی است که از اعضای یک دنباله $n$عضوی به دست می‌آید که در آن $n=2^{k}$است. این جایگشت یه این شکل به دست می‌آید که ابتدا اعضای دنباله اصلی را با اعداد $0$تا $n-1$اندیس‌دهی می‌کنیم و سپس اندیس هر عضو را از نظر دودویی واژگون می‌کنیم. (با این فرض که همه اعداد دقیقاً دارای $k$بیت هستند) در نهایت هم هر عضو را با توجه به اندیسی که گرفته در جایگشت جواب قرار می‌دهیم. یکی از ویژگی‌های مهمی هم که این عملیات دارد این است که پیج است. یعنی اگر دو بار این عملیات را روی حایگشت اعمال کنیم در نهایت به جایگشت اولیه می‌رسیم.

مثال

جایگشت ۸ عضوی $<0,1,2,3,4,5,6,7>$را در نظر بگیرید، در این مثال $n=8$و $k=3$است و زمانی که الگوریتم را روی آن اجرا کنیم نتیجه جایگشت $<0,4,2,6,1,5,3,7>$است. برای دیدن بهتر این دنباله هم در مثال‌های بیشتر می‌توانید به این‌جا مراجعه کنید.

تعمیم‌دادن

عملیات قبلی که روی جایگشت اعمال می‌شد فقط برای جایگشت‌هایی بود که اندازه آن‌ها $2^{k}$است، اما با این تعمیم می‌توان آن را برای جایگشت‌هایی که طول آن‌ها $b^{k}$است انجام داد. (باید شرط $b>1$را داشته‌باشیم) نحوه انجام عملیات برای این جایگشت‌ها به این گونه است که اندیس‌ها را در مبنای $b$می‌نویسیم و سپس هر اندیس را وارونه می‌کنیم. (طول همه اندیس‌ها $k$در نظر گرفته می‌شود و اگر این گونه نبودند به ابتدای آن‌ها صفر اضافه می‌شود) حال هر عضو را با توجه به اندیس جدیدی که گرفته‌است در دنباله جدید قرار می‌دهیم. هم‌چنین این عملیات مانند حالت قبلی پیج است و اگر دو بار آن را روی یک جایگشت اعمال کنیم دوباره به جایگشت اولیه می‌رسیم.

کاربردها

این الگوریتم در حالتی که $b=2$باشد در الگوریتم FFT کاربرد دارد و اگر این کار را به صورت درجا دهیم باعث می‌شود این الگوریتم حافظه کم‌تری مصرف کند و زمان اجرا آن هم کم‌تر بشود. برای اجرای این الگوریتم به صورت درجا هم می‌توان به ازای اعدادی که وارون آن‌ها از خودشان کم‌تر است، با وارون‌شنان جابه‌جا کنیم و در انتها دنباله‌ای را که به دست می‌آید را به عنوان خروجی الگوریتم داد. زمان اجرای این الگوریتم هم $O(n)$ است و حافظه اضافی هم ندارد.

پیاده‌سازی

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

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 عدد داده‌شده را برعکس می‌کنیم و سپس در تابع اصلی خروجی الگوریتم را محاسبه و برمی‌گردانیم.[۱]

جستارهای وابسته

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