PDA

Просмотр полной версии : Алгоритм комбинаторики



Decoder
17.11.2008, 17:10
Всем привет!
У кого-нибудь есть готовая реализация алгоритма комбинаторики на С++.
Суть алгоритма:
Дан некий набор величин (к примеру: 1, 2, 3).
Нужно получить все возможные варианты перестановок этих величин (соответственно: 123, 132, 213, 231, 321, 312).

Albor
18.11.2008, 07:38
Есть в STL. Алгоритмы next_permutation и prev_permutation

WinMain
18.11.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;
}

Decoder
18.11.2008, 14:16
Спасибо, WinMain! Попробовал твой алгоритм с целочисленными переменными вместо символьных, всё замечательно работает.

Decoder
03.12.2009, 23:42
Всем привет!
Хотелось бы так же увидеть комбинаторный алгоритм размещения. Т.е. имеется к примеру 4 ячейки, в которые нужно положить 2 шара.
Нужно перечислить все варианты расположения шаров в ячейках.
Что-то вроде такого:
ООХХ
ОХОХ
ОХХО
ХООХ
ХОХО
ХХОО

WinMain
04.12.2009, 20:16
Вот как этот алгоритм будет выглядеть на C#


using System;
using System.Collections.Generic;
using System.Text;

namespace Placement
{
class Program
{
static void MakePlacements(int nTotal, int nChecks, char[] cells, int offset, IList<string> strList)
{
char check = 'O';
while (nChecks <= nTotal && nChecks > 0)
{
if (nChecks > 1)
{
char[] newCells = new char[cells.Length];
cells.CopyTo(newCells, 0);
newCells[offset] = check;
MakePlacements(nTotal - 1, nChecks - 1, newCells, offset + 1, strList);
nTotal--;
offset++;
}
else
{
for (int i = 0; i < nTotal; i++)
{
char[] newCells = new char[cells.Length];
cells.CopyTo(newCells, 0);
newCells[offset + i] = check;
strList.Add(new string(newCells));
}
break;
}
}
}
static void MakePlacementList(int nTotal, int nChecks, IList<string> strList)
{
string str = new string('.', nTotal);
MakePlacements(nTotal, nChecks, str.ToCharArray(), 0, strList);
}
static void Main(string[] args)
{
List<string> strList = new List<string>();
MakePlacementList(6, 3, strList);
//
foreach (string s in strList)
{
Console.WriteLine(s);
}
//
Console.ReadLine();
}
}
}


Только для обозначения пустой ячейки я здесь использовал символ точки, а не "Х".