WinMain » 18 ноя 2008, 12:00
У меня есть такой алгоритм на С++. Для примера в нём использован набор символов a,b,c,d. На выходе получаются различные комбинации из этих символов. Алгоритм реализован в виде шаблона, поэтому вместо символьных переменных можно использовать переменные других типов.
Код: Выделить всё
void init_factorials(int *pF, int n)
{
int F = 1;
for (int i = 1; i <= n; i++)
{
F *= i;
pF[i] = F;
}
}
template <typename T>
void rotl(T *a, int n) // кольцевой сдвиг влево
{
if (n < 2)
return;
T temp = a[0];
for (int i = 0; i < n-1; i++)
{
a[i] = a[i+1];
}
a[n-1] = temp;
}
template <typename T>
void copy(T* src, int n, T* dst) // копирование элементов
{
for (int i = 0; i < n; i++)
{
dst[i] = src[i];
}
}
template <typename T>
T* duplicate(T* src, int n) // дубликат массива
{
T* dup = new T[n];
copy(src, n, dup);
return dup;
}
template <typename T>
void combinator(T *src, int n, T** dst, int* pF, int x, int y)
{
// src - исходный массив
// dst - результирующий массив
// pF - массив факториалов
// x, y - смещение внутри двумерного массива
T *Dup = duplicate(src, n);
for (int i = 0; i < n; i++)
{
for (int k = 0; k < pF[n-1]; k++)
{
int m = y+i*pF[n-1]+k;
copy(Dup, n, dst[m]+x);
}
if ( n > 2)
{
int y1 = y+i*pF[n-1];
combinator(Dup+1, n-1, dst, pF, x+1, y1);
}
rotl(Dup, n);
}
delete[] Dup;
}
int _tmain(int argc, _TCHAR* argv[])
{
char Arr[] = {'a', 'b', 'c', 'd'}; // исходный массив
const int N = sizeof(Arr)/sizeof(Arr[0]); // размер массива
int F[N+1] = {0}; // массив факториалов
//
init_factorials(F, N);
// Выделение памяти под матрицу...
char** Res = new char*[F[N]];
for (int i = 0; i < F[N]; i++)
{
Res[i] = new char[N];
}
// Заполнение матрицы...
combinator(Arr, N, Res, F, 0, 0);
// Вывод результата на экран...
for (int s = 0; s < F[N]; s++)
{
for (int a = 0; a < N; a++)
{
cout << Res[s][a] << " ";
}
cout << endl;
}
// Освобождение выделенной памяти...
for (int c = 0; c < F[N]; c++)
{
delete[] Res[c];
}
delete[] Res;
//
return 0;
}
У меня есть такой алгоритм на С++. Для примера в нём использован набор символов a,b,c,d. На выходе получаются различные комбинации из этих символов. Алгоритм реализован в виде шаблона, поэтому вместо символьных переменных можно использовать переменные других типов.
[code]
void init_factorials(int *pF, int n)
{
int F = 1;
for (int i = 1; i <= n; i++)
{
F *= i;
pF[i] = F;
}
}
template <typename T>
void rotl(T *a, int n) // кольцевой сдвиг влево
{
if (n < 2)
return;
T temp = a[0];
for (int i = 0; i < n-1; i++)
{
a[i] = a[i+1];
}
a[n-1] = temp;
}
template <typename T>
void copy(T* src, int n, T* dst) // копирование элементов
{
for (int i = 0; i < n; i++)
{
dst[i] = src[i];
}
}
template <typename T>
T* duplicate(T* src, int n) // дубликат массива
{
T* dup = new T[n];
copy(src, n, dup);
return dup;
}
template <typename T>
void combinator(T *src, int n, T** dst, int* pF, int x, int y)
{
// src - исходный массив
// dst - результирующий массив
// pF - массив факториалов
// x, y - смещение внутри двумерного массива
T *Dup = duplicate(src, n);
for (int i = 0; i < n; i++)
{
for (int k = 0; k < pF[n-1]; k++)
{
int m = y+i*pF[n-1]+k;
copy(Dup, n, dst[m]+x);
}
if ( n > 2)
{
int y1 = y+i*pF[n-1];
combinator(Dup+1, n-1, dst, pF, x+1, y1);
}
rotl(Dup, n);
}
delete[] Dup;
}
int _tmain(int argc, _TCHAR* argv[])
{
char Arr[] = {'a', 'b', 'c', 'd'}; // исходный массив
const int N = sizeof(Arr)/sizeof(Arr[0]); // размер массива
int F[N+1] = {0}; // массив факториалов
//
init_factorials(F, N);
// Выделение памяти под матрицу...
char** Res = new char*[F[N]];
for (int i = 0; i < F[N]; i++)
{
Res[i] = new char[N];
}
// Заполнение матрицы...
combinator(Arr, N, Res, F, 0, 0);
// Вывод результата на экран...
for (int s = 0; s < F[N]; s++)
{
for (int a = 0; a < N; a++)
{
cout << Res[s][a] << " ";
}
cout << endl;
}
// Освобождение выделенной памяти...
for (int c = 0; c < F[N]; c++)
{
delete[] Res[c];
}
delete[] Res;
//
return 0;
}
[/code]