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!/(s₁!s₂!...s_k!), където s_i! е броят на 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
Общ брой n^k. В примера 3² = 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.

Задача 5b. Индекс на Шапли-Шубик за политическа сила при да-не система за гласуване
[ Пети междууниверситетски турнир по програмиране, 19 май 2002 г., БСУ ]
    Във всеки съюз или обединение от политически субекти (напр. държави) се налага да се приеме система за вземане на решения. Една такава система е да се гласува с "да'' или "не'', като всяка държава да има определен брой гласове. Решение да се взема когато броят на гласовете "да'' е по-голям или равен на определена граница. Коалиция се нарича група държави, която гласува
с "да'' за дадено предложение. Ако сумата от гласовете на държавите в коалицията е по-голяма или равна на определената граница, то предложението се приема и тази коалиция се нарича печеливша.
    Например през 1958 г. се създава Европейския съюз с точно такава система за вземани на важни решения. Участващите в съюза държави и гласовете им са: Франция, Германия, Италия - по 4 гласа,
Белгия, Холандия - по 2 гласа, Люксембург - 1 глас. Предложение се приема, ако за него са гласували с "да'' 12 от общо 17 гласа. Две печеливши коалиции в съюза са например Франция, Германия и Италия или Франция, Германия, Белгия, Холандия и Люксембург.
    Една от няколкото известни мерки за политическата сила на дадена държава в един съюз е индексът на Шапли-Шубик. Ето как се дефинира този индекс. Нека съюзът се състои от n държави - p₁, p₂, ..., p_n. Разглеждаме всички възможне наредби на n-те държави. Нека индексите
i₁, i₂,..., i_n задават една конкретна наредба. Държавата p_ik се нарича централна за тази наредба, ако коалицията, състояща се от p_i1, p_i2, ..., p_{i(k - 1)} не е печеливша, а коалицията p_i1, p_i2, ..., p_ik е печеливша. Индекс на Шапли-Шубик за държавата  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

0
100