ну сохранять напрямую весь массив, действительно, избыточно
если это делать, нужно записать одно из n^n чисел
всего же различных комбинаций - n!, что намного меньше
таким образом, нужно просто перевести сведения о порядке элементов в одно число
сделать это можно, например, так:
| Код | int encode(CSomeArray array)
{
int n,i;
n=array.Length();
i=array.Find(n-1);
array.Cut(i);
return i+n*function(array);
}; |
класс CSomeArray - придуман для наглядности алгоритма
методы:
Length() - возвращает длину массива
Find(x) - ищет элемент x в массиве и возвращает его индекс
Cut(i) - вырезает элемент с индексом i (длина приэтом уменьшается на 1)
Insert(x,i) - вставляет элемент x в позицию с номером i (все, что после него - сдвигается)
на самом деле здесь реализован просто перевод числа в другую систему счисления
особенностью является переменное основание этой системы:
для младшего разряда оно=1
для старшего - n
число записывается так:
0*1+i1*1*2+i2*1*2*3+i3*1*2*3*4+...
i1 - положение 1 в массиве, который получится после выкидывания всех чисел кроме 0 и 1
i2 - положение 2 в массиве из 0,1,2
...
декодировать можно так:
| Код | CSomeArray decode(int x,int n)
{
CSomeArray result;
int i;
int nn;
for(i=0;i<n;i++)
result.Insert(i,x%(i+1));
return result;
}; |
может, что-нибудь и напутал, но, надеюсь, алгоритм понятен |
