Обращение целых чисел

Обратная перестановка чисел, и в частности бит-ревёрсная перестановка, является техникой перестановки, используемой в некоторых алгоритмах быстрого преобразования Фурье.

Задать функцию, которая генерирует обратную перестановку степени .

In[1]:=

reversalperm[k_, b_] := IntegerReverse[Range[0, b^k - 1], b, k] + 1;

Сгенерировать бит-ревёрстную перестановку списка длиной .

In[2]:=

Table[reversalperm[k, 2], {k, 0, 5}]

Out[2]=

Сгенерировать базовую перестановку трёх позиций для списка из 9 элементов.

In[3]:=

reversalperm[2, 3]

Out[3]=

Представить эти замены.

In[4]:=

segment[{p1_, p2_}] := {PointSize[Large], Point[{p1, p2}], Line[{p1, p2}], Text[Last[p1], p1 - {1/2, 0}], Text[Last[p2], p2 + {1/2, 0}]};

In[5]:=

With[{k = 2, b = 3}, Graphics[ segment /@ Thread[{Thread[{0, Range[b^k]}], Thread[{b^k, reversalperm[k, b]}]}] ]]

Out[5]=