Комбинаторика

9.2.1 Нахождение числа сочетаний из n по m

Функция находит число сочетаний из n элементов по m:

Вычисления проводятся по рекуррентной формуле:

//*****************************************************************

//Функция находит число сочетаний C из n по m.

//*****************************************************************

int combinationsnm (int n, int m)

{

int result;

int i;

if(n<m)

{

result = 0;

}

else

{

if(m>double(n)/double(2))

{

m = n-m;

}

if(m==0)

{

result = 1;

}

else

{

n = n+1;

result = 1;

i = 1;

do

{

result = result*(n-i)/i;

i = i+1;

}

while(i<=m);

}

}

return result;

}

9.2.2 Генерация перестановки, следующей за данной

Процедура находит перестановку следующую за данной в лексикографическом порядке. Начальная перестановка задается в массиве X, туда же после работы процедуры помещается найденная перестановка. Результат равен истине, если на вход подана перестановка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все перестановки n чисел надо инициализировать массив X значениями 1, 2,..., n и последовательно вызывать процедуру до тех пор пока результат не окажется равным истине.

Количество перестановок из n чисел будет равно факториалу числа n.

// ******************************************************************

char NextPermutation(int n; int& x[]);

Процедура находит перестановку следующую за данной в

лексикографическом порядке. Начальная перестановка

задается в массиве X, туда же после работы процедуры

помещается найденная перестановка.

Скажем, для N равного 3 существуют шесть

перестановок:

№1: 1 2 3

№2: 1 3 2

№3: 2 1 3

№4: 2 3 1

№5: 3 1 2

№6: 3 2 1

Результат равен истине, если на вход подана перестановка, являющаяся последней при лексикографическом упорядочивании.

Таким образом чтобы получить все перестановки n - чисел надо инициализировать массив X значениями 1,2,..., n и последовательно вызывать процедуру до тех пор пока результат не окажется равным истине.

Количество перестановок из n чисел будет равно факториалу числа n.

*************************************************************************/

bool nextpermutation(int n, int& x[])

{

bool result;

int k;

int t;

int y;

k = n-1;

while(k>0)

{

if(x[k]<=x[k+1])

{

break;

}

k = k-1;

}

if(k!=0)

{

t = k+1;

while(t<n)

{

if(x[t+1]<=x[k])

{

break;

}

t = t+1;

}

y = x[k];

x[k] = x[t];

x[t] = y;

t = 0;

while(t<(n-k)/2)

{

y = x[n-t];

x[n-t] = x[k+1+t];

x[k+1+t] = y;

t = t+1;

}

result = false;

}

else

{

result = true;

}

return result;

}

9.2.3 Генерация перестановки по номеру

Этот алгоритм предназначен для получения перестановки по её номеру (перестановки упорядочены в лексикографическом порядке). В оющем случае, чтобы получить перестановку с номером K, можно вызвать K раз алгоритм получения следующей перестановки. Если требуется последовательно получать перестановки с номерами от 1 до K, то можно поступить и так, но в случае, когда требуется получить лишь K-ую перестановку, но такой способ крайне неэффективен. Для этого можно использовать специальный алгоритм, который позволяет непосредственно получить искомую перестановку без всяких промежуточных шагов.

//******************************************************************

KthPermutation(int n; int k; int &a[]);

процедура находит K-ую из перестановок чисел от 1 до N, упорядоченных в лексикографическом порядке. Перестановки нумеруются от 1 до N!.

Скажем, для N равного 3 существуют шесть

перестановок:

№1: 1 2 3

№2: 1 3 2

№3: 2 1 3

№4: 2 3 1

№5: 3 1 2

№6: 3 2 1

Число N должно быть достаточно мало, чтобы

N! уместилось в разрядную сетку компьютера.

*************************************************************************/

void kthpermutation(int n, int k, int &a[])

{

int temp;

int selnum;

int i;

int j;

int f;

k = k-1;

f = 1;

a.setbounds(1, n);

for(i = 1; i <= n; i++)

{

a[i] = i;

f = f*i;

}

for(i = 1; i <= n-1; i++)

{

f = f/(n+1-i);

selnum = i+k/f;

temp = a[selnum];

for(j = selnum; j >= i+1; j--)

{

a[j] = a[j-1];

}

a[i] = temp;

k = k%f;

}

}

9.2.4 Получение номера перестановки

Этот алгоритм позволяет по перестановке чисел от 1 до N получить её номер в списке перестановок, упорядоченных в лексикографическом порядке.

// ******************************************************************

// int permutationnum(int n, int& a[]);

// процедура находит порядковый номер перестановок чисел

// от 1 до N, упорядоченных в лексикографическом порядке.

// Перестановки нумеруются от 1 до N!.

// Скажем, для N равного 3 существуют шесть перестановок:

// №1: 1 2 3

// №2: 1 3 2

// №3: 2 1 3

// №4: 2 3 1

// №5: 3 1 2

// №6: 3 2 1

// Число N должно быть достаточно мало, чтобы N!

// уместилось в разрядную сетку компьютера.

//******************************************************************

int permutationnum(int n, int& a[])

{

int result;

int t;

int i;

int j;

int f;

result = 0;

f = 1;

for(i = 1; i <= n; i++)

{

f = f*i;

}

for(i = 1; i <= n-1; i++)

{

f = f/(n+1-i);

t = a[i]-1;

for(j = 1; j <= i-1; j++)

{

if(a[j]<a[i])

{

t = t-1;

}

}

result = result+f*t;

}

result = result+1;

return result;

}

9.2.5 Генерация выборки из n по m, следующей за данной

Функция находит выборку, следующую за данной в лексикографическом порядке. Начальная выборка задается в массиве X, туда же после работы функции помещается найденная выборка. Результат функции равен истине, если на вход подана выборка являющаяся последней при лексикографическом упорядочивании. Таким образом чтобы получить все выборки - надо инициализировать массив X значениями 1, 2,..., m и последовательно вызывать функцию до тех пор пока результат не окажется равным истине. Числа внутри выборки, поданной на вход функции, должны быть упорядочены по возрастанию.

/*************************************************************************

Выборки из n элементов по m.

char nextretrieval(int n, int m, int &x[]);

процедура находит выборку следующую в лексикографическом порядке за выборкой заданной в массиве X. Если выборка в массиве последняя, то переменной Result присваивается значение True, иначе False.

Числа в сочетании упорядочены по возрастанию.

Скажем, для N=3, M=2 существуют три комбинации:

№1: 1 2

№2: 1 3

№3: 2 3

Таким образом чтобы получить все выборки из n по m, надо

инициализировать массив X значениями 1,2,..., m и последовательно

вызывать процедуру до тех пор пока результат не окажется равным истине.

Количество выборок будет равно числу сочетаний из n по m.

*************************************************************************/

char nextretrieval(int n, int m, int &x[])

{

bool result;

int i;

result = false;

i = m;

while(i>0)

{

if(x(i)<n-(m-i))

{

break;

}

i = i-1;

}

if(i>0)

{

x(i) = x(i)+1;

i = i+1;

while(i<=m)

{

x(i) = x(i-1)+1;

i = i+1;

}

}

else

{

result = true;

}

return result;

}

9.2.5 Генерация выборки по номеру

Этот алгоритм предназначен для получения выборки (комбинации, сочетания) из N по M по её номеру (выборки упорядочены в лексикографическом порядке). В принципе, чтобы получить выборку с номером K, можно вызвать K раз алгоритм получения следующей выборки. Если требуется последовательно получать выборки с номерами от 1 до K, то можно поступить и так, но в случае, когда требуется получить лишь K-ую выборку, но такой способ крайне неэффективен. Для этого можно использовать специальный алгоритм, который позволяет непосредственно получить искомую выборку без всяких промежуточных шагов. Под выборкой в данном случае понимается упорядоченный массив из M неповторяющихся чисел в диапазоне от 1 до N включительно.

/*************************************************************************

void kthretrieval(int n, int m, int k, int &a[])

Эта процедура по номеру комбинации из N по M строит саму комбинацию, имеющую номер K. Комбинации упорядочены в лексикографическом порядке и имеют номера от 1 до C(n,m)

Числа в сочетании упорядочены по возрастанию.

Скажем, для N=3, M=2 существуют три комбинации:

№1: 1 2

№2: 1 3

№3: 2 3

Числа N и M должны быть достаточно малы, чтобы C(n,m)

уместилось в разрядной сетке компьютера.

*************************************************************************/

void kthretrieval(int n, int m, int k, int &a[])

{

int i;

int j;

int lbound;

int c;

int t;

a.setbounds(1, m);

if(n==1||n==m)

{

for(i = 1; i <= m; i++)

{

a[i] = i;

}

return;

}

if(m==1)

{

a[1] = k;

return;

}

t = 1;

lbound = 1;

c = 1;

for(i = 1; i <= m-1; i++)

{

c = c*(n-i)/i;

}

for(i = 1; i <= m-1; i++)

{

for(j = lbound+1; j <= n; j++)

{

if(t+c>k)

{

a[i] = j-1;

break;

}

t = t+c;

c = c*(n-j+1-m+i)/(n-j+1);

}

c = c*(m-i)/(n-a(i));

lbound = a[i]+1;

}

a[m] = lbound+k-t;

}

9.2.6 Получение номера выборки

Ещё один алгоритм для работы с выборками. Этот алгоритм позволяет по выборке из N по M получить её номер в списке выборок, упорядоченных в лексикографическом порядке. Под выборкой в данном случае понимается упорядоченный массив из M неповторяющихся чисел в диапазоне от 1 до N включительно

/*************************************************************************

int retrievalnum(int n, int m, int &a[]);

процедура находит порядковый номер сочетания чисел из N по M, упорядоченных в лексикографическом порядке.

Числа от 1 до N. Нумерация идет от 1 до C(N,M).

Числа в сочетании должны быть упорядочены по возрастанию.

Скажем, для N=3, M=2 существуют три сочетания:

№1: 1 2

№2: 1 3

№3: 2 3

Числа N и M должны быть достаточно малы, чтобы C(n,m)

уместилось в разрядной сетке компьютера.

*************************************************************************/

int retrievalnum(int n, int m, int &a[]);

{

int result;

int i;

int j;

int lbound;

int c;

if(n==1||n==m)

{

result = 1;

return result;

}

if(m==1)

{

result = a[1];

return result;

}

result = 1;

lbound = 1;

c = 1;

for(i = 1; i <= m-1; i++)

{

c = c*(n-i)/i;

}

for(i = 1; i <= m-1; i++)

{

for(j = lbound+1; j <= a[i]; j++)

{

result = result+c;

c = c*(n-j+1-m+i)/(n-j+1);

}

c = c*(m-i)/(n-a[i]);

lbound = a[i]+1;

}

result = result+a(m)-lbound;

return result;

}

Дата добавления: 2014-10-17