Условие
Получить все размещения из [latex]9[/latex] элементов [latex]\left\{1,2, \ldots, 9\right\}[/latex] по [latex]5[/latex] элементов в каждом.
Код на С++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <algorithm> #include <math.h> using namespace std; int a1[6]; int a2[6]; int cnt=0; //генерация перестановок void permut (int m){ for (int j=1; j<=m; j++) a2[j]=a1[j]; int i = 1; int j; while (i != 0){ for (int i=1; i<=m; i++) cout << a2[i]; cout << endl; i=m-1; while (a2[i]>a2[i+1]) i--; j=m; while (a2[j]<a2[i]) j--; swap (a2[j],a2[i]); int k=i+1; int kk=i+floor((m-i)/2); while (k<=kk){ swap(a2[k],a2[m-k+i+1]); k++; } cnt++; } } int main() { int n=9, k=5; int p=k; //генерация размещений for (int i=1; i<=k; i++) a1[i]=i; while(p>=1){ permut(k); if (a1[k]==n) p-=1; else p=k; if (p>=1) for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1; } //проверка количества размещений cout << cnt << endl; return 0; } |
Код на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
import java.util.*; import java.lang.*; import java.io.*; class A { public static int cnt = 0; public static void Permutation (int m, int[] a1, int[] a2){ for (int j=1; j<=m; j++) a2[j] = a1[j]; int j; int i = 1; while (i != 0){ //for (i=1; i<=m; i++) System.out.print(a2[i]); //System.out.print("\n"); i=m-1; while (a2[i]>a2[i+1]) i--; j=m; while (a2[j]<a2[i]) j--; int tmp = a2[j]; a2[j] = a2[i]; a2[i] = tmp; int k=i+1; int kk=i + (m-i)/2; while (k<=kk){ tmp = a2[k]; a2[k] = a2[m-k+1+i]; a2[m-k+1+i] = tmp; k++; } cnt++; } } public static void main (String[] args) { int[] a1; int[] a2; a1 = new int [6]; a2 = new int [6]; int n=9, k=5; int p=k; for (int i=1; i<=k; i++) a1[i]=i; while(p>=1){ Permutation(k, a1, a2); if (a1[k]==n) p-=1; else p=k; if (p>=1) for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1; } System.out.println(cnt); } } |
Решение
При решении этой задачи мне понадобились 2 источника информации:
Там были приведены алгоритмы генерирования перестановок («Комбинаторные алгоритмы», стр. 27-29) и генерирования сочетаний («Комбинаторика для программистов», стр. 39-41).
Размещения я получал следующим образом:
- Посчитал кол-во всевозможных размещений по формуле [latex]A^{k}_{n}=\frac{n!}{(n-k)!}=\frac{9!}{4!}=15120[/latex];
- Заметил, что размещения — это перестановки всех уникальных комбинаций из 5 чисел (т.е сочетаний);
- Поскольку кол-во перестановок [latex]P_{k}=k![/latex], а кол-во сочетаний — [latex]C_{n}^{k}=\frac{n!}{k!(n-k)!}[/latex], то кол-во размещений [latex]A_{n}^{k}=P_{k}\times{C_{n}^{k}}=\frac{n!k!}{k!(n-k)!}=\frac{n!}{(n-k)!}=15120[/latex];
Таким образом, генерируя вначале сочетание, я генерировал перестановки этого сочетания. В результате вышло 15120 размещений.
Липский хорошо объясняет. Наверное нужно его на сайте разместить рядом с Корменом. вторую не видел раньше. Сейчас посмотрю. Интересно.