Алгоритм комбинаторики

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Аватара пользователя
Decoder
Сообщения: 301
Зарегистрирован: 19 фев 2008, 23:11
Откуда: Moscow

17 ноя 2008, 17:10

Всем привет!
У кого-нибудь есть готовая реализация алгоритма комбинаторики на С++.
Суть алгоритма:
Дан некий набор величин (к примеру: 1, 2, 3).
Нужно получить все возможные варианты перестановок этих величин (соответственно: 123, 132, 213, 231, 321, 312).
Albor
Сообщения: 482
Зарегистрирован: 06 сен 2004, 13:34
Откуда: Днепропетровск

18 ноя 2008, 07:38

Есть в STL. Алгоритмы next_permutation и prev_permutation
Аватара пользователя
WinMain
Сообщения: 912
Зарегистрирован: 14 янв 2005, 10:30
Откуда: Москва
Контактная информация:

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;
}
Приглашаю на свой сайт http://winmain.org
Аватара пользователя
Decoder
Сообщения: 301
Зарегистрирован: 19 фев 2008, 23:11
Откуда: Moscow

18 ноя 2008, 14:16

Спасибо, WinMain! Попробовал твой алгоритм с целочисленными переменными вместо символьных, всё замечательно работает.
Аватара пользователя
Decoder
Сообщения: 301
Зарегистрирован: 19 фев 2008, 23:11
Откуда: Moscow

03 дек 2009, 23:42

Всем привет!
Хотелось бы так же увидеть комбинаторный алгоритм размещения. Т.е. имеется к примеру 4 ячейки, в которые нужно положить 2 шара.
Нужно перечислить все варианты расположения шаров в ячейках.
Что-то вроде такого:
ООХХ
ОХОХ
ОХХО
ХООХ
ХОХО
ХХОО
Поумнеть несложно, куда труднее от дури избавиться.
Аватара пользователя
WinMain
Сообщения: 912
Зарегистрирован: 14 янв 2005, 10:30
Откуда: Москва
Контактная информация:

04 дек 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();
        }
    }
}


Только для обозначения пустой ячейки я здесь использовал символ точки, а не "Х".
Приглашаю на свой сайт http://winmain.org
Ответить