Перестановки с повторениями

Перестановки с повторениями допускают повторное использование элементов. Пусть мы имеем множество, состоящее из двух символов A и двух символов B. Тогда все перестановки с повторениями из этих символов будут таковы: AABB, ABBA, BABA, ABAB, BAAB, BBAA. В общем случае, если имеется N1 предметов 1-го вида, N2 предметов 2-го вида и т. д., Nk предметов k-го вида, то общее количество пеpестановок может быть вычислено по формуле: Алгоритм аналогичен генерации перестановок без повторений, за исключением формирования начальной перестановки:   i=0;   Для j от 1 до k           Для m от 1 до N[j] i=i+1; B[i]=j; В программе генерации перестановок с возвращениями (листинг 2.42) количество K различных типов предметов, обозначенных латинскими буквами, вводится с клавиатуры. С клавиатуры также вводятся количества NN[j] предметов каждого типа. Сумма введенных NN[j] определяет общее количество элементов в каждой из генерируемых перестановок. Листинг 2.42. Программа генерации перестановок с возвращениями const   alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';

var   b : array [1..100] of byte;   N,i,j,k,m : byte;   NN : array [1..100] of longint;   Procedure SwapB(i,k:byte);   var x : byte;   begin     x:=B[i]; B[i]:=B[k]; B[k]:=x;   end; Procedure WriteB;   begin     for i:=1 to N do write(alphabet[b[i]]);     writeln;   end; begin   readln(K);   N:=0;   for i:=1 to K do     begin read(NN[i]); N:=N+NN[i]; end;   i:=0;   for j:=1 to k do     for m:=1 to NN[j]       do begin Inc(i); B[i]:=j; end;   WriteB;   while (true) do     begin       i:=N;       while (i>0) and (B[i]>=B[i+1]) do i:=i-1;       if i=0 then exit;       for j:=i+1 to N do if (B[j]>B[i]) then K:=j;       SwapB(i,k);       for j:=i+1 to (i+ ((N+1-i) div 2)) do SwapB(j,N+i+1-j);       WriteB;     end; end.

Сочетания с повторениями

Для множества символов от A до C и размера M = 3 сочетания с повторениями будут следующими: CCC, BCC, BBC, BBB, ACC, ABC, ABB, AAC, AAB, AAA. Общее количество сочетаний:

где N - количество символов, M - количество символов в сочетании. Основная идея генерации таких сочетаний с повторениями заключается в следу-ющем: сочетания записываем в виде (N - 1)-го нуля и M единиц, где единицы заменяют символы, а нули - выступают в pоли pазделителей. Напpимеp: ABB - 1 0 1 1, AAC - 1 1 0 0 1, CCC - 0 0 1 1 1. Поясним эти примеры.

• 1011.

• Первая цифра 1 означает, что в строке символов присутствует символ A.

• Следующая цифра 0 означает, что символы A закончились.

• Следующая цифра 1 означает, что далее идет символ B.

• Следующая цифра 1 означает, что далее идет еще один символ B.

• Цифры закончились.

Итак, строка символов ABB была представлена двоичной строкой 1011.

• 11001.

• Первая цифра 1 означает, что в строке символов присутствует символ A.

• Следующая цифра 1 означает, что далее еще раз идет символ A.

• Следующая цифра 0 означает, что символы A закончились.

• Следующая цифра 0 означает, что символы B закончились (отсутствовали).

• Следующая цифра 1 означает, что далее идет символ С.

• Цифры закончились.

Итак, строка символов AAC была представлена двоичной строкой 11001.

• 00111.

• Первая цифра 0 означает, что в строке символов отсутствует символ A.

• Следующая цифра 0 означает, что в строке символов отсутствует символ B.

• Следующая цифра 1 означает, что далее идет символ С (первый символ).

• Следующая цифра 1 означает, что далее еще раз идет символ С.

• Следующая цифра 1 означает, что далее еще раз идет символ С.

• Цифры закончились.

Итак, строка символов CCC была представлена двоичной строкой 00111. При таком подходе для решения задачи достаточно сгенерировать все перестановки из M единиц и (N - 1)-го нуля. Листинг 2.43. Программа, генерирующая сочетания с повторениями const   alphabet : string[26] = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'; var   b : array [1..100] of byte;   N,i,j,k,M,N1 : byte;   Procedure SwapB(i,k:byte);     var x : byte;     begin       x:=B[i]; B[i]:=B[k]; B[k]:=x;     end; Procedure WriteB;     var i,j : byte;     begin       j:=1;       for i:=1 to N do         if b[i]=0           then Inc(j)           else write(alphabet[j]);       writeln;     end; begin   readln(N1,M); N:=N1-1+M;   for i:=1 to n1-1 do b[i]:=0;   for i:=n1 to n1+m-1 do b[i]:=1;   WriteB;   while (true) do     begin       i:=N;       while (i>0) and (B[i]>=B[i+1]) do i:=i-1;       if i=0 then exit;       for j:=i+1 to N do         if (B[j]>B[i]) then K:=j;       SwapB(i,k);       for j:=i+1 to (i+ ((N+1-i) div 2)) do         SwapB(j,N+i+1-j);       WriteB;     end; end.

Пояснения к программе.

1. Начальная перестановка формируется последовательно из N1-1 нулей и M единиц.

В программе вывода перестановки WriteB осуществлены изменения, соответствующие замыслу (нули - разделители, единицы - символы). Если текущий элемент массива B равен 0, то «становится активным» следующий символ. Если текущий символ массива B равен 1, то текущий активный символ выводится на экран.

Задача 1 Генерация всех подмножеств данного множества

Для генерации всех подмножеств воспользуемся двоичной арифметикой. Пусть наше множество элементов находится в массиве b, а соответствующее двоичное число в массиве а. Если в соответствующем элементе массива а находится единица, то соответствующий элемент массива b берется в подмножество, а если ноль, то не берется. С самого начала в массиве а находятся одни нули, то есть ни один элемент данного множества мы не берем. Далее будем к двоичному числу прибавлять по единице, получая следующие подмножества и так до тех пор пока не получим двоичное число, составленное из единиц.

Program podmnojestva;

const nmax=10;

var a:array[1..nmax] of byte;

m,i,n,j,k:integer;

procedure nextbin; получение следующего двоичного числа

begin

if a[n]=0 then a[n]:=1 если последняя цифра ноль, то заменяем ее на 1

else

begin

i:=n; начиная с конца двоичного числа

while (i>=1)and(a[i]=1) do двигаемся влево, пока цифры числа единицы

begin

a[i]:=0; по пути заменяем единицы нулями

dec(i);

end;

a[i]:=1; первый встреченный ноль заменяем единицей

end;

end;

begin

assign(input,’input.txt’);

reset(input);

assign(output,’output.txt’);

rewrite(output);

read(n); количество элементов в множестве

fillchar(a,sizeof(a),0); заполнение массива нулями

m:=1;

for i:=1 to n do вычисляем количество всех подмножеств

m:=m*2; так как каждый разряд в числе мы можем

заполнить двумя способами, то число всех подмножеств равно 2ⁿ

for k:=1 to m do получение всех подмножеств

begin

nextbin; получаем следующее двоичное число

for j:=1 to n do write(a[j]); вывод подмножества

writeln;

end;

end.

Эта программа генерирует все подмножества из множества натуральных чисел {1,2... n}. Эти числа можно рассматривать как индексы элементов какого-то массива а₁,а₂...a_n. Тогда получив подмножество из индексов, мы тем самым получили подмножество и из элементов множества а. Так как число 2ⁿ быстро увеличивается с ростом n, то сгенерировать все подмножества для данного множества мы сможем для небольших n. Для каких? Это вы можете выяснить самостоятельно.

комбинаториказадачи

Задача 2 Получение всех сочетаний из m по n

Program sochetanij;

const nmax=20;

var c:array[1..nmax] of byte;

i,j,m,n:integer;

procedure nextsoch; получение очередного сочетания

var i,s,num0,num1:integer;

begin

s:=n-1;;

while not ((c[s]=0)and(c[s+1]=1)) do dec(s); ищем, двигаясь справа налево, пару 01

num1:=0;

for i:=s+1 to n do num1:=num1 +c[i]; считаем количество

1 правее найденного 0

c[s]:=1; заменяем 0 на 1

num0:=n-s+1-num1; считаем количество 0

for i:=s+1 to s+num0 do c[i]:=0; делаем последовательность

минимальной, сначала записывая

0 потом 1

for i:=s+num0+1 to n do c[i]:=1;

end;

procedure out; вывод одного сочетания

begin

for i:=1 to n do write(c[i],’ ‘);

writeln;

end;

function last:boolean; логическая функция проверяющая

дошли ли мы до последнего

сочетания 111...000 или нет

если дошли, тогда last=true,иначе false

var i:byte;

begin

for i:=1 to m do проверяем первые m элементов

if c[i]=0 then если среди них есть хотя бы один ноль

begin last:=false;exit end; значит до последнего сочетания не

дошли

last:=true;

end;

procedure init; получение первого сочетания

begin

assign(input,’input.txt’); reset(input);

assign(output,’output.txt’); rewrite(output);

for i:=1 to n-m do c[i]:=0;

for i:=n-m+1 to n do c[i]:=1;

end;

begin

init;

out;

repeat повторяем, пока не достигнем сочетания 111000

nextsoch;

out;

until last;

end.

комбинаториказадачи

Задача 3 Алгоритм генерации перестановок в лексикографическом порядке

Генерировать пререстановки будем опять из индексов элементов массива, то есть чисел 1,2...n.

Алгоритм генерации следующий:

• Просматриваем а₁, ..., а_n с конца до тех пор, пока не попадется a_i<a_i+1. Если таковых нет, то генерация закончена.

• Рассматриваем a_i+1, a_i+2, ..., a_n. Найдем первый с конца a_m больший a_i и поменяем их местами.

• Участок a_i+1, a_i+2, ..., a_n переставим в порядке возрастания (для этого достаточно перевернуть его).

• Выводим найденную перестановку.

• Возвращаемся к началу алгоритма.

Первой при этом первой будет перестановка <1, 2, ...,n>,а последней-<n, ..., 2,1>.

program perestanovka_chisel_1_to_N;

const nmax=30;

var n,j,i:byte;

a:array[1..nmax] of byte;

procedure Init;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

for i:=1 to n do

a[i]:=i;

close(input);

end;

procedure swap(var a,b:byte); процедура, меняющая элементы местами

var c:byte;

begin

c:=a; a:=b; b:=c;

end;

function last:boolean; функция, проверяющая дошли ли

мы до последней перестановки

begin

last:=true;

for i:=1 to n-1 do

if a[i+1]>a[i] then

begin

last:=false; exit;

end;

end;

procedure next; генерация следующей перестановки

begin

i:=n-1; начинаем с предпоследнего элемента

while (i>0) and (a[i]>a[i+1]) do пока не нашли a[i]<a[i+1]

dec(i); двигаемся влево по массиву

j:=n;

while (j>i) and (a[j]<a[i]) do ищем с конца массива первый элемент

dec(j); больший a[i]

swap(a[i],a[j]); меняем их местами

for j:=i+1 to (n+1) div 2 do переворачиваем конец массива

swap(a[j],a[n-j+i+1]);

end;

procedure solve;

begin

for i:=1 to n do write(a[i]); выводим первую перестановку

writeln;

repeat пока не дошли до последней перестановки

next; генерируем следующую перестановку

for i:=1 to n do write(a[i]); выводим ее

writeln;

until last;

end;

begin init; solve; close(output); end.

комбинаториказадачи

Задача 4 Генерация перестановок с использованием множества и рекурсии

Program perestanovka

const nmax=20;

type intset=set of 1..nmax;

var a:array[1..nmax] of integer;

var q,k:integer;

procedure perest(s:intset;k:integer);

var i,j:integer;

begin

for i:=1 to n do перебираем индексы

if i in s then если число в множестве есть

begin

a[k]:=i; записываем его в массив

perest(s-[i],k+1); удаляем из множества и делаем

рекурсивный вызов

s:=s+[i]; добавляем число в множество

if i=n then если получили перестановку

begin

for j:=1 to n do write(a[j],' '); выводим ее

writeln;

inc(q);

end;

end;

end;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

q:=0;

perest([1..n],1);

writeln('q=',q); выводим количество перестановок

end.

Эта программа только выводит перестановки. Для их использования надо применить такой же массив, как и в предыдущей реализации.

комбинаториказадачи

Задача 5 Максимальная сумма

Дана прямоугольная матрица размером n*m, заполненная неотрицательными целыми числами. Надо пройти из верхнего левого угла в правый нижний и по пути набрать как можно большую сумму. Кодируем шаг вниз – 0, вправо – 1. Вывести максимальную сумму и последовательность перемещений, как последовательность 0 и 1.

Так как мы можем сделать только n-1 шагов вниз и m-1 шагов вправо, то задача свелась к генерации сочетаний из n+m-2 элементов по m-1.

Program summa;

const nmax=10;mmax=10;

var c,best:array[1..nmax+mmax-2] of byte;

a:array[1..nmax,1..mmax] of integer;

t,smax,s,i,j,m,n,n1,m1:integer;

procedure nextsoch; получение следующего сочетания

var i,s,num0,num1:integer;

begin

s:=n-1;;

while not ((c[s]=0)and(c[s+1]=1)) do dec(s);

num1:=0;

for i:=s+1 to n do num1:=num1 +c[i];

c[s]:=1;

num0:=n-s+1-num1;

for i:=s+1 to s+num0 do c[i]:=0;

for i:=s+num0+1 to n do c[i]:=1;

end;

procedure out; вывод результата

begin

assign(output,'out.txt');

rewrite(output);

writeln(smax);

for i:=1 to n do write(best[i]);

end;

function last:boolean; проверка-дошли ли до последнего сочетания

var i:byte;

begin

for i:=1 to m do

if c[i]=0 then begin last:=false;exit end;

last:=true;

end;

procedure init; чтение исходных данных

begin

assign(input,'in.txt');

reset(input);

fillchar(c,sizeof(c),0);

read(n1,m1);

for i:=1 to n1 do

for j:=1 to m1 do

read(a[i,j]);

m:=m1-1;n:=n1+m1-2; шагов вниз и вправо на 1 меньше, чем размеры матрицы

for i:=1 to n-m do c[i]:=0; формируем первое сочетание

for i:=n-m+1 to n do c[i]:=1;

end;

begin

init;

smax:=0;

repeat

nextsoch;

s:=a[1,1];i:=1;j:=1;

for t:=1 to n do бежим по полученному сочетанию

if c[t]=0

then begin inc(i);s:=s+a[i,j] end если шаг вниз

else begin inc(j);s:=s+a[i,j] end; если шаг вправо

if s>smax

then

begin

smax:=s; запоминаем лучшую сумму

best:=c; запоминаем лучший путь

end;

until last;

out; выводим результат

end.

комбинаториказадачи

Задача 6 Выбор подмножества

Дан целочисленный массив a[1..N] (1<=N<=20) и число M. Найти подмножество элементов массива a[i1], a[i2], ...a[ik] такое, что i1 < i2 < i3 < ... < ik N и a[i1] + a[i2] + ... + a[ik] = M.

Решение. Сгенерируем все подмножества, которые можно составить из элементов массива и проверим конкретное подмножество на соответствие условию задачи.

function check(j:longint):boolean; генерация подмножества и проверка на условие задачи

var k:integer; s:longint;

begin

s:=0;

for k:=1 to n do

if ((j shr (k-1))and 1)=1 данное условие означает, что в k-й справа позиции числа j, в двоичной системе, стоит 1

then s:=s+a[k];

if s=m then

begin

for k:=1 to n do

if ((j shr (k-1))and 1)=1 then write(a[k]:4);

writeln

end

end;

procedure subsets(n:integer);

var q,j:longint;

begin

q:=1 shl n; таким образом мы помещаем в q число 2^n

for j:=1 to q-1 do цикл по всем подмножествам

if check(j) then exit

end;

Заметим, что если все элементы в массиве положительные, то, изменив порядок рассмотрения подмножеств, решение приведенной выше задачи можно сделать более эффективным. Так, если сумма элементов какого-либо подмножества уже больше, чем M, то рассматривать подмножества, включающие его в себя, уже не имеет смысла. Пересчет же сумм можно оптимизировать, если каждое следующее сгенерированное подмножество будет отличаться от предыдущего не более, чем на один элемент. Приведенная же программа чрезвычайно проста, но обладает одним недостатком: мы не можем ни в каком случае с ее помощью перебирать все подмножества множеств, состоящих из более, чем 30 элементов, что обусловлено максимальным числом битов, отводимых на представление целых чисел в Турбо Паскале (32 бита). Но, как уже было сказано выше, на самом деле, перебор всех подмножеств у множеств большей размерности вряд ли возможен за время, отведенное для решения той или иной задачи.

комбинаториказадачи

Задача 7 Кратчайший путь

Есть N городов (1<=N<=20), обозначенных буквами латинского алфавита.

Известно что человек всегда выходит из города А , и обязательно должен пройти все оставшиеся города и попасть обратно в А. Например, есть пять городов , А , Б , С , Д и Е., Из А -> Б -> C->Д->E->A. То есть за исключением А , порядок посещения оставшихся четырех городов может меняться. То есть существует (5-1)! комбинаций. Найти длину и сам кратчайший путь удовлетворяющий условию задачи (таблица расстояний для примера приводится ниже)...

	A	B	C	D	E
A	0	85	117	163	489
B	85	0	30	50	385
C	117	30	0	27	322
D	163	50	27	0	302
E	489	385	322	302	0

Входные данные

В первой строчке файла input.txt содержится число пунктов N, далее следует матрица расстояний, N строчек по N чисел разделенных пробелами.

Выходные данные

В первой строке файла output.txt длина кратчайшего пути

Во второй один из кратчайших путей

Это задача на нахождение Эйлерова цикла из темы «Графы». Но мы решим ее комбинаторным методом. При данных ограничениях это вполне возможно.

Алгоритм решения рассмотрим на примере.

Для удобства будем нумеровать города по порядку 1 2 3 4 5. Нам нужно получить все цепочки вида 1 N1 N2 N3 N4 1, для каждой такой цепочки надо сосчитать путь по ф-ле S:=A[1,N1]+A[N1,N2]+A[N2,N3]+A[N3,N4]+A[N4,1]. Среди этих путей надо найти путь минимальной длины. Таким образом, задача сводится к генерации всех перестановок в общем случае N-элементного множества (всего таких перестановок N!). Будем генерировать перестановки в алфавитном (лексикографическом порядке) первая перестановка 1 2 3 4, последняя 4 3 2 1.

Порождение всех перестановок будем производить "по индукции". Предположим, что мы умеем порождать все перестановки из N-1 элемента. Тогда сначала сгенерируем все перестановки 2,...,N, приписывая к ним слева единицу. Затем сгенерируем все перестановки чисел 1,3,...,N, приписывая к ним слева двойку и т.д. Последним шагом будет генерация всех перестановок из чисел 1,...,N-1 c приписыванием к ним слева числа N.

Из описанной процедуры вытекает, что каждая следующая перестановка получается из предыдущей таким образом. В "предыдущей" перестановке X[1],...,X[N] справа ищется наибольшая убывающая подпоследовательность X[i]>...>X[N] ( если рассматривать позиции, начиная с i-й, то это последняя перестановка чисел X[i],...,X[N]). Если i=1, то все перестановки были сгенерированы и последовательность сортируется по возрастанию (получаем первую перестановку). Иначе среди чисел X[i],...,X[N] выбирается наименьшее X[j], большее X[i-1], и ставится на позицию i-1, а все оставшиеся числа (и x[i-1] в том числе) сортируются по возрастанию.

комбинаториказадачи

Задача 9 Японская полоса

На клетчатой полоске бумаги высотой в одну клеточку и длиной N клеточек некоторые клетки раскрашены в зеленый и белый цвета. Дальше по этой полоске строится ее код, которым является последовательность чисел — количества подряд идущих зеленых клеток слева направо. Например, для такой полоски

кодом будет последовательность 2 3 2 8 1. При этом количество белых клеток, которыми разделяются группы зеленых клеток нигде не учитывается (главное, что две группы разделяются по крайней мере одной белой клеткой). Поэтому одному и тому же коду могут соответствовать несколько полосок. Например, указанному коду соответствует и такая полоса:

Ваша задача состоит в том, чтобы найти количество полосок длины N, которые соответствуют заданному коду.

Входные данные:

Во входном файле Input.txt вводится сначала число N — длина полоски (1N200). Затем идет число K — количество чисел в коде (0K(N+1)/2). А затем следует K чисел, задающих код.

Выходные данные:

В выходной файл Output.txt вывести количество полосок длины N, соответствующих заданному коду.

Input.txt	Output.txt
4 0	1
5 2 1 2	3
4 2 2 2	0

program Project2;

{$APPTYPE CONSOLE}

{$o-}

uses

SysUtils,math;

type tmass=array[0..150]of integer;

var n,k,i,j,s:integer;

c:array[0..300,0..300] of tmass;

function sum(x,y:tmass):tmass;

var i0:integer;

res:tmass;

begin

fillchar(res,sizeof(res),0);

for i0:=1 to max(x[0],y[0]) do

begin

res[i0]:=res[i0]+x[i0]+y[i0];

res[i0+1]:=res[i0] div 10;

res[i0]:=res[i0] mod 10;

end;

res[0]:=max(x[0],y[0]);

if res[res[0]+1]>0 then

inc(res[0]);

result:=res;

end;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

read(n,k);

s:=0;

for i:=1 to k do

begin

read(j);

s:=s+j;

end;

if n-s<k-1 then

begin

writeln(0);

close(input);

close(output);

halt(0);

end;

n:=n-s+1;

fillchar(c,sizeof(c),0);

c[0,1][1]:=1;

c[0,1][0]:=1;

for i:=1 to n do

for j:=1 to i+1 do

c[i,j]:=sum(c[i-1,j],c[i-1,j-1]);

for i:=c[n,k+1][0] downto 1 do

write(c[n,k+1][i]);

close(input);

close(output);

end.

комбинаториказадачи

К оглавлению