5. Основни комбинаторни алгоритми [1.3]

*** Пермутации [1.3.1] - наредени n-торки
А. Без повторения { 1 2 3 }
123  132  213  231  312  321
Общ брой n!
// permute.c - пермутации без повторения
#include <stdio.h>
#define MAXN 100

const unsigned n = 3;
unsigned char used[MAXN];
unsigned mp[MAXN];

void print(void)
{ unsigned j;
  for (j=0; j<n; j++) printf("%u ", mp[j]+1);
  printf("\n");
}
void permute(unsigned i)
{ unsigned j;
  if (i>=n) { print(); return; }
  for (j=0; j<n; j++)
  { if (!used[j])
    { used[j]=1; mp[i]=j;
      permute(i+1);
      used[j]=0;
    }
  }
}
int main()
{ unsigned j;
  for (j=0; j<n; j++) used[j]=0;
  permute(0);  return 0;
}
Б. С повторения { 1 1 2 3 }
1123  1132  1213  1231  1312  1321  2113  2131  2311  3112  3121  3211
Общ брой n!/(s1!s2!...sk!), където si! е броят на i-тия различен елемент, участващ в мултимножеството. В примера 4!/(2!1!1!) = 12.

*** Вариации [1.3.2] - нареден k-елементен списък измежду n елемента (нареден)
А. Без повторения n= 3 { 1 2 3 },  k = 2
12  13  21  23  31  32
Общ брой n!/(n - k)!  В примера 3!/1 = 6.
Б. С повторения n= 3 { 1 2 3 },  k = 2
11  12  13  21  22  23  31  32  33
Общ брой nk. В примера 32 = 9.
// variate.c - вариации с повторения
#include <stdio.h>
#define MAXN 100

const unsigned n = 3;
const unsigned k = 2;
unsigned mp[MAXN];

void print(void)
{ unsigned j;
  for (j=0; j<k; j++) printf("%u ", mp[j]+1);
  printf("\n");
}
void variate(unsigned i)
{ unsigned j;
  if (i>=k) { print(); return; }
  for (j=0; j<n; j++)
  { mp[i]=j;
    variate(i+1);
  }
}
int main()
{ variate(0); return 0; }

*** Комбинации [1.3.3] k-елементно подмножество измежду n елемента (ненаредено)
А. Без повторения  n= 5 { 1 2 3 4 5 },  k = 2
12  13  14  15  23  24  25  34  35  45
Общ брой n!/((n - k)!k!).  В примера 5!/(3!2!) = 10.
// comb.c - комбинации без повторения
#include <stdio.h>
#define MAXN 20

const unsigned n = 5;
const unsigned k = 2;
unsigned mp[MAXN];

void print(void)
{ unsigned j;
  for (j=0; j<k; j++) printf("%u ", mp[j]);
  printf("\n");
}
void comb(unsigned i, unsigned after)
{ unsigned j;
  if (i>k) return;
  for (j=after+1; j<=n; j++)
  { mp[i-1]=j;
    if (i==k) print();
    comb(i+1,j);
  }
}
int main()
{ comb(1,0);  return 0; }

Б. с повторения n= 5 { 1 2 3 4 5 },  k = 2
11  12  13  14  15  22  23  24  25  33  34  35  44  45  55
Общ брой (n + k - 1)! / ((n - 1)! k!).  В примера 6!/(4!2!) = 15.



Задача 5a.  Огърлици
    Дадени са неограничен брой мъниста от K цвята (K<10), от които се правят огърлици с дължина N (N<10). Да се намери броят на всички различни огърлици с дължина N.
    Входен файл - necklace.inp
Всеки ред на файла съдържа две числа K и N. Числото 0 е последно във файла.
    Изходен файл - necklace.out
За всеки ред от входния файл програмата записва на отделен ред броя на различните огърлици.
Пример:
2 3
3 5
0
Решение на примера:
6
135

Задача 5b. Индекс на Шапли-Шубик за политическа сила при да-не система за гласуване
[ Пети междууниверситетски турнир по програмиране, 19 май 2002 г., БСУ ]
    Във всеки съюз или обединение от политически субекти (напр. държави) се налага да се приеме система за вземане на решения. Една такава система е да се гласува с "да'' или "не'', като всяка държава да има определен брой гласове. Решение да се взема когато броят на гласовете "да'' е по-голям или равен на определена граница. Коалиция се нарича група държави, която гласува
с "да'' за дадено предложение. Ако сумата от гласовете на държавите в коалицията е по-голяма или равна на определената граница, то предложението се приема и тази коалиция се нарича печеливша.
    Например през 1958 г. се създава Европейския съюз с точно такава система за вземани на важни решения. Участващите в съюза държави и гласовете им са: Франция, Германия, Италия - по 4 гласа,
Белгия, Холандия - по 2 гласа, Люксембург - 1 глас. Предложение се приема, ако за него са гласували с "да'' 12 от общо 17 гласа. Две печеливши коалиции в съюза са например Франция, Германия и Италия или Франция, Германия, Белгия, Холандия и Люксембург.
    Една от няколкото известни мерки за политическата сила на дадена държава в един съюз е индексът на Шапли-Шубик. Ето как се дефинира този индекс. Нека съюзът се състои от n държави - p1, p2, ..., pn. Разглеждаме всички възможне наредби на n-те държави. Нека индексите
i1, i2,..., in задават една конкретна наредба. Държавата pik се нарича централна за тази наредба, ако коалицията, състояща се от pi1, pi2, ..., pi(k - 1) не е печеливша, а коалицията pi1, pi2, ..., pik е печеливша. Индекс на Шапли-Шубик за държавата  p се нарича отношението на броя на наредбите, в които  p е централна към броя на всички възможни наредби. Да се напише програма за пресмятане на индекса на Шапли-Шубик.
    Входен файл - shsh.in
Съдържа няколко тестови примери. Данните за всеки от примерите са записани на два последователни реда във файла. Първият ред за всеки от примерите съдържа две цели числа, разделени с един интервал - броят N на държавите в съюза (1 < N < 11) и необходимият брой гласове V за вземане на решение. На следващия ред има N цели числа (разделени с по един интервал), които са гласовете на участниците в съюза. Файлът завършва с ред, съдържащ числото 0.
    Изходен файл - shsh.out
За всеки пример трябва да се изведат N цели числа, по едно на ред, всяко равно на индекса на Шапли-Шубик, изразен в проценти за поредния участник в съюза. Числата да са закръглени (по общоприетите правила за закръгляване) с 1 значеща цифра след десетичната точка. Между изходните данни за отделните примери трябва да се оставя по един празен ред.
Пример:
3 51
50 49 1
6 12
4 4 4 2 2 1
0
Решение на примера:
66.6
16.6
16.6

23.3
23.3
23.3
15
15
0

Задача 5c. Политическа сила (Задача 3 )
[ Междууниверситетско състезание по програмиране, 24 март 2002 г., БСУ ]
>    Всички важни решения в Eвропейския съюз се вземат чрез да-не гласуване на дадено предложение, като участващите в съюза държави имат различен брой гласове. Ето разпределението на гласовете по държави: Франция, Германия, Италия и Англия - по 10 гласа, Испания - 8,  Белгия, Холандия, Португалия и Гърция - 5, Австрия и Швеция - 4, Дания, Ирландия и Финландия - 3, Люксембург - 2 гласа. Предложение се приема при събрани 62 от общо 87 гласа.
    Една мярка са политическата сила на една държава в съюза е индексът на Банзаф. Нека p е дадена държава. Обща политическа сила O(p) на p се нарича броя на коалициите C, изпълняващи следните 3 условия:
    1. p е член на коалиция C;
    2. C е печеливша коалиция (събира необходимите брой гласове за приемане на дадено предложение);
    3. Когато p излезе от C, получената коалиция е губеща (не е печеливша).
    Индекс на Банзаф B(p) за държавата p се пресмята по формулата: B(p) = O(p)/s, където s е сумата от общата политическа сила на всички участници в съюза. Да се напише програма за пресмятане на индекса на Банзаф.
    Входен файл - banzaf.inp
Първият ред от един пример съдържа две цели числа - броя на държавите N в съюза (1<N<32) и необходимия брой гласове V за вземане на решение. Следващите N цели числа са гласовете на участниците в съюза. Във файла се съдържат много примери, като последно число във файла е стойност 0 за N.
    Изходен файл - banzaf.out
За всеки пример се извеждат N цели числа - индекса на Банзаф в проценти за участниците в съюза (закръглен до цяло число). Между примерите се оставя празен ред.
Пример:
15 62
10 10 10 10 8 5 5 5 5 4 4 3 3 3 2
2 50
49 51
0
Решение на примера:
11
11
11
11
9
6
6
6
6
5
5
4
4
4
2

0
100