Как найти следующую лексикографическую перестановку - Исправление недочетов и поиск решений вместе с Examum.ru

Алгоритм: Как найти следующую лексикографическую перестановку

Время на прочтение
3 мин

Количество просмотров 33K

Если кратко описать, что такое лексикографический порядок — это сортировка в алфавитном порядке. Т.е. последовательность символов — AAA → AAB → AAC → AAD → ……… → WWW — является отсортированной в алфавитном (или в нашем случае лексикографическом) порядке.

Представьте, что у Вас есть конечная последовательность символов, например 0, 1, 2, 5, 3, 3, 0 и Вам необходимо найти все возможные перестановки этих символов. Наиболее интуитивным, но и наибольшим по сложности, является рекурсивный алгоритм, когда мы выбираем первый символ из последовательности, далее рекурсивно выбираем второй, третий итд, до тех пор, пока все символы из последовательности не будет выбраны. Понятно, что сложность такого алгоритма — O(n!).

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

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

В качестве примера возьмем вышеприведенную последовательность — (0, 1, 2, 5, 3, 3, 0). Чтобы получить последовательность выше оригинальной, достаточно переставить первый и второй элементе местами, но в этом нет необходимости, так как можно переставить второй и и третий и получив более близкую по возрастанию последовательность. что приведет нас к следующей более близкой перестановки итд.

Наиболее оптимальным алгоритмом в этом случае будет следующий:

Прежде всего Вы должны найти наибольший не-увеличивающийся суффикс. В вышеприведенном примере это будет — (5, 3, 3, 0). Если Вы попробуете сделать любую перестановку в данной последовательности, то она не будет выше оригинальной.
Стоит сказать, что найти данную последовательность вы можете за O(n) времени, просматривая последовательность слева направо.
Следующий элемент от суффикса является точкой поворота. В нашем случае — это 2. Точка поворота будет всегда меньше первого элемента суффикса. Это значит, что в суффиксе обязательно будет элемент превышающий точку поворота и если мы поменяет точку поворота на наименьший элемента из суффикса, превышающий опорный элемент точки поворота — мы получим последовательность превышающую оригинальную — в нашем случает это будет — (0, 1, 3, 5, 3, 2, 0).
Т.е. результатом этой операции будет минимально возможный по возрастанию префикс.
И на последнем шаге мы должны отсортировать суффикс в порядке возрастания. Т.е. мы получим минимально возможный суффикс. В нашем примере это будет (0, 2, 3, 5) и вся последовательность будет выглядеть как (0, 1, 3, 0, 2, 3, 5).

Это значение и будет следующей лексикографической перестановкой.

Что касается практического применения алгоритма, то за все время моей работы он мне ни разу не понадобился, но на интервью в Uber посчитали иначе :))

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

Большое спасибо PYXRU и 646f67, что ткнули меня носом в возможную оптимизацию алгоритма — произвести расчет перестановки за линейную сложность просто сделав reverse суффикса.

func NextPermutationAlgorithm(w string) string {

 l := len(w)
	b := []byte(w)
	r := "no answer"

	for i:=l-1; i>0 ; i--{
		if b[i-1] < b[i] {
			pivot := i
			for j := pivot; j < l; j++ {
				if b[j] <= b[pivot] && b[i-1] < b[j] {
					pivot = j
				}
			}

			b[i-1], b[pivot] = b[pivot], b[i-1]

			for j := l-1; i < j; i, j = i+1, j-1 {
				b[i], b[j] = b[j], b[i]
			}

			r = string(b)
			break
		}
	}

	return r
}

Источник

Этот онлайн калькулятор иллюстрирует работу нерекурсивного алгоритма Нарайаны для генерации перестановок в лексикографическом порядке. Вы вводите элементы начальной перестановки, разделенные запятыми, и количество итераций алгоритма (перестановка, полученная на предыдущей итерации, является начальной перестановкой следующей итерации). Данные по умолчанию — перестановка 1,2,3 и количество итераций 6 генерируют все возможные перестановки из трех элементов (три факториал) и возвращают к начальной перестановке.

Это иллюстрирует тот факт, что если алгоритм Нарайаны применить в цикле к исходной последовательности из элементов $a_{1},a_{2},...,a_{n}$ , упорядоченных так, что $a_{1}leqslant a_{2}leqslant ...leqslant a_{n}$ , то он сгенерирует все перестановки элементов множества ${a_{1},a_{2},...,a_{n}}$ в лексикографическом порядке¹.

Описание алгоритма можно прочитать под калькулятором.

Алгоритм Нарайаны

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

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Алгоритм Нарайаны

Найти такой наибольший , для которого $a_{j}<a_{j+1}$ .
Увеличить $a_{j}$ . Для этого надо найти наибольшее , для которого $a_{l}>a_{j}$ . Затем поменять местами $a_{j}$ и $a_{l}$ .
Записать последовательность $a_{j+1},...,a_{n}$ в обратном порядке.

Алгоритм придуман индийским математиком Пандитом Нарайаной в XIV веке.

Источник

Для заданной строки найти все ее лексикографически следующие перестановки.

Слова расположены в том же порядке в лексикографическом порядке, в каком они предположительно появляются в словаре. Например, лексикографически следующая перестановка строки ABCD является ABDC, для строки ABDC является ACBD, а для строки ACBD является ACDB.

Потренируйтесь в этой проблеме

Простым решением было бы использовать std::next_permutation который генерирует следующую большую лексикографическую перестановку строки. Если функция может определить следующую более высокую перестановку, она переставляет элементы и возвращает значение true. Если это невозможно (поскольку это уже максимально возможная перестановка), он переставляет элементы в соответствии с первой перестановкой и возвращает false.

Реализацию можно увидеть ниже на C++:

C++

#include <iostream>

#include <algorithm>

using namespace std;

// Функция для поиска всех лексикографически следующих перестановок

// строка с использованием `std::next_permutation`

void permutations(string str)

{

// базовый вариант

if (str.length() == 0) {

return;

}

while (1)

{

// печатаем текущую перестановку

cout << str << » «;

// найти следующую лексикографически упорядоченную перестановку

if (!next_permutation(str.begin(), str.end())) {

break;

}

int main()

{

string str = «BADC»;

permutations(str);

return 0;

}

Скачать Выполнить код

результат:

BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

Мы также можем реализовать собственные next_permutation() функция. Следующий алгоритм генерирует следующую перестановку лексикографически после данной перестановки. Это изменяет перестановку на месте.

Найдите самый большой индекс i такой, что str[i-1] меньше чем str[i].
Вернуть ложь, если i является первым индексом строки, что означает, что мы уже находимся в максимально возможной перестановке, т. е. строка отсортирована в порядке убывания. Если i не является первым индексом строки, тогда подстрока str[i…n) сортируется по убыванию, т. str[i-1] < str[i] >= str[i+1] >= str[i+2] >= … >= str[n-1].
Найдите самый высокий индекс j справа от указателя i такой, что str[j] больше, чем str[i-1] и поменять местами символ по индексу i-1 с индексом j.
Обратная подстрока str[i…n) и вернуть истину.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

#include <iostream>

#include <algorithm>

using namespace std;

// Функция для поиска следующих лексикографически перестановок строки.

// Возвращает true, если строка может быть переупорядочена как лексикографически

// большая перестановка; в противном случае возвращается ложь.

bool next_permutation(string &str, int n)

{

// найти наибольший индекс `i`, такой, что `str[i-1]` меньше, чем `str[i]`

int i = n — 1;

while (str[i — 1] >= str[i])

{

// если `i` это первый индекс строки, это значит, что мы уже

// при максимально возможной перестановке, т.е. строка отсортирована в

// в порядке убывания

if (—i == 0) {

return false;

}

/* Если мы доходим до этого места, подстрока `str[i…n)` сортируется в порядке убывания

т. е. str[i-1] < str[i] >= str[i+1] >= str[i+2] >= … >= str[n-1] */

// найти наибольший индекс `j` справа от индекса `i` такой, что

// str[j] > str[i-1]

int j = n — 1;

while (j > i && str[j] <= str[i — 1]) {

j—;

}

// поменять местами символ с индексом `i-1` на индекс `j`

swap(str[i — 1], str[j]);

// перевернуть подстроку `str[i…n)` и вернуть true

reverse (str.begin() + i, str.end());

return true;

}

// Функция для поиска всех лексикографически следующих перестановок строки

void permutations(string str)

{

int n = str.length();

// базовый вариант

if (n == 0) {

return;

}

// базовый вариант

if (n == 1) {

cout << str;

return;

}

while (1)

{

// печатаем текущую перестановку

cout << str << » «;

// найти следующую лексикографически упорядоченную перестановку

if (!next_permutation(str, str.length())) {

break;

}

int main()

{

string str = «BADC»;

permutations(str);

return 0;

}

Скачать Выполнить код

Java

import java.util.Arrays;

class Main

{

private static void swap(char[] chars, int i, int j)

{

char ch = chars[i];

chars[i] = chars[j];

chars[j] = ch;

}

private static void reverse(char[] chars, int start)

{

for (int i = start, j = chars.length — 1; i < j; i++, j—) {

swap(chars, i, j);

}

// Функция для поиска следующих лексикографически перестановок строки.

// Возвращает true, если строка может быть переупорядочена как лексикографически

// большая перестановка; в противном случае возвращается ложь.

public static boolean next_permutation(char[] chars)

{

// найти наибольший индекс `i`, такой, что `chars[i-1]` меньше, чем `chars[i]`

int i = chars.length — 1;

while (chars[i — 1] >= chars[i])

{

// если `i` это первый индекс строки, это значит, что мы уже

// при максимально возможной перестановке, т.е. строка отсортирована в

// в порядке убывания

if (—i == 0) {

return false;

}

если мы достигнем этого места, подстрока `chars[i…n)` будет отсортирована в порядке убывания

т.е. chars[i-1] < chars[i] >= chars[i+1] >= chars[i+2] >= … >= chars[n-1]

// найти наибольший индекс `j` справа от индекса `i` такой, что

// chars[j] > chars[i-1]

int j = chars.length — 1;

while (j > i && chars[j] <= chars[i — 1]) {

j—;

}

// поменять местами символ с индексом `i-1` на индекс `j`

swap(chars, i — 1, j);

// перевернуть подстроку `chars[i…n)` и вернуть true

reverse(chars, i);

return true;

}

// Функция для поиска всех лексикографически следующих перестановок строки

public static void permutations(String str)

{

// базовый вариант

if (str == null || str.length() == 0) {

return;

}

// базовый вариант

if (str.length() == 1) {

System.out.print(str);

return;

}

// преобразовать строку в массив символов

char[] chars = str.toCharArray();

while (true)

{

// печатаем текущую перестановку

System.out.print(new String(chars) + » «);

// найти следующую лексикографически упорядоченную перестановку

if (!next_permutation(chars)) {

break;

}

public static void main(String[] args)

{

String str = «BADC»;

permutations(str);

}

Скачать Выполнить код

Python

def swap(chars, i, j):

ch = chars[i]

chars[i] = chars[j]

chars[j] = ch

def reverse(chars, start):

(i, j) = (start, len(chars) — 1)

while i < j:

swap(chars, i, j)

i = i + 1

j = j — 1

# Функция поиска лексикографически следующих перестановок строки.

# Возвращает истину, если строка может быть переупорядочена как лексикографически

# большая перестановка; в противном случае возвращается ложь.

def next_permutation(chars):

# найти наибольший индекс `i`, такой, что `chars[i-1]` меньше, чем `chars[i]`

i = len(chars) — 1

while chars[i — 1] >= chars[i]:

#, если `i` является первым индексом строки, это означает, что мы уже

# при максимально возможной перестановке, т. е. строка отсортирована в

# в порядке убывания

i = i — 1

if i == 0:

return False

»’ if we reach here, the substring `chars[i…n)` is sorted in descending order;

i.e., chars[i-1] < chars[i] >= chars[i+1] >= chars[i+2] >= … >= chars[n-1] »’

# найти наибольший индекс `j` справа от индекса `i` такой, что

# `chars[j] > chars[i-1]`

j = len(chars) — 1

while j > i and chars[j] <= chars[i — 1]:

j = j — 1

# поменять местами символ с индексом `i-1` на индекс `j`

swap(chars, i — 1, j)

# перевернуть подстроку `chars[i…n)` и вернуть true

reverse(chars, i)

return True

# Функция для поиска всех лексикографически следующих перестановок строки

def permutations(s):

# Базовый вариант

if not s:

return

# Базовый вариант

if len(s) == 1:

print(s)

return

# преобразовать строку в список

chars = list(s)

while True:

# распечатать текущую перестановку

print(».join(chars), end=‘ ‘)

# найти следующую лексикографически упорядоченную перестановку

if not next_permutation(chars):

break

if __name__ == ‘__main__’:

s = ‘BADC’

permutations(s)

Скачать Выполнить код

Output:

BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

Временная сложность приведенных выше решений в наихудшем случае равна O(n.n!) как есть n! перестановки для строки длины n, и каждая перестановка занимает O(n) время. Худший случай возникает, когда строка содержит все отдельные элементы.

Обратите внимание, что приведенное выше решение может обрабатывать строки, содержащие повторяющиеся символы, и не будет печатать повторяющиеся перестановки.

Также см:

Найти все лексикографически предыдущие перестановки строки

Спасибо за чтение.

Пожалуйста, используйте наш онлайн-компилятор размещать код в комментариях, используя C, C++, Java, Python, JavaScript, C#, PHP и многие другие популярные языки программирования.

Как мы? Порекомендуйте нас своим друзьям и помогите нам расти. Удачного кодирования

Источник

All the permutations of a word when arranged in a dictionary, the order of words so obtained is called lexicographical order. in Simple words, it is the one that has all its elements sorted in ascending order, and the largest has all its elements sorted in descending order.

lexicographically is nothing but the greater permutation of it.

For reference: a b c d e f g h i j k l m n o p q r s t u v w x y z

For example, lexicographically next permutation of “gfg” is “ggf” and the next permutation of “acb” is “bac”.
Note: In some cases, the next lexicographically greater word might not exist, e.g, “aaa” and “edcba”.

In C++, there is a specific function that saves us from a lot of code. It’s in the file #include <algorithm>. The function is next_permutation(a.begin(), a.end()).
It returns ‘true’ if the function could rearrange the object as a lexicographically greater permutation. Otherwise, the function returns ‘false’.

Example:

CPP

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

string s = { "gfg" };

bool val

= next_permutation(s.begin(),

s.end());

if (val == false)

cout << "No Word Possible"

<< endl;

else

cout << s << endl;

return 0;

}

Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(1), as constant extra space is used.

The same program can also be implemented without using STL. Below is the code snippet for the same.

The Idea is Based on the Following Facts:

A sequence sorted in descending order does not have the next permutation. For example “edcba” does not have the next permutation.
For a sequence that is not sorted in descending order for example “abedc”, we can follow these steps.
- a) Traverse from the right and find the first item that is not following the ascending order. For example in “abedc”, the character ‘b’ does not follow the ascending order.
- b) Swap the found character with the closest greater (or smallest greater) element on the right side of it. In the case of “abedc”, we have ‘c’ as the closest greater element. After swapping ‘b’ and ‘c’, the string becomes “acedb”.
- c) After swapping, reverse the string after the position of the character found in step a. After reversing the substring “edb” of “acedb”, we get “acbde” which is the required next permutation.

Optimizations in steps b) and c)
a) Since the sequence is sorted in decreasing order, we can use binary search to find the closest greater element.

c) Since the sequence is already sorted in decreasing order (even after swapping as we swapped with the closest greater), we can get the sequence sorted (in increasing order) after reversing it.

CPP

#include <iostream>

using namespace std;

void swap(char* a, char* b)

{

if (*a == *b)

return;

*a ^= *b;

*b ^= *a;

*a ^= *b;

}

void rev(string& s, int l, int r)

{

while (l < r)

swap(&s[l++], &s[r--]);

}

int bsearch(string& s, int l, int r, int key)

{

int index = -1;

while (l <= r) {

int mid = l + (r - l) / 2;

if (s[mid] <= key)

r = mid - 1;

else {

l = mid + 1;

if (index == -1 || s[index] >= s[mid])

index = mid;

}

return index;

}

bool nextpermutation(string& s)

{

int len = s.length(), i = len - 2;

while (i >= 0 && s[i] >= s[i + 1])

--i;

if (i < 0)

return false;

else {

int index = bsearch(s, i + 1, len - 1, s[i]);

swap(&s[i], &s[index]);

rev(s, i + 1, len - 1);

return true;

}

int main()

{

string s = { "gfg" };

bool val = nextpermutation(s);

if (val == false)

cout << "No Word Possible" << endl;

else

cout << s << endl;

return 0;

}

Java

import java.io.*;

public class Main {

public static char[] nextPermutation(String s) {

char[] arr = s.toCharArray();

int n = arr.length;

int i = n - 2;

while (i >= 0 && arr[i] >= arr[i+1]) {

i--;

}

if (i < 0) {

String st = "No next Permutation possible";

char[] ar = st.toCharArray();

return ar;

}

int j = n - 1;

while (j >= 0 && arr[j] <= arr[i]) {

j--;

}

swap(arr, i, j);

rev(arr, i+1, n-1);

return arr;

}

private static void swap(char[] arr, int i, int j) {

char temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

private static void rev(char[] arr, int start, int end) {

while (start < end) {

swap(arr, start, end);

start++;

end--;

}

public static void main(String[] args)

{

String str2 = "gfg";

System.out.println(nextPermutation(str2));

}

Python3

def next_permutation(s: str) -> str:

arr = list(s)

n = len(arr)

i = n - 2

while i >= 0 and arr[i] >= arr[i+1]:

i -= 1

if i < 0:

return "No next Permutation possible"

j = n - 1

while j >= 0 and arr[j] <= arr[i]:

j -= 1

arr[i], arr[j] = arr[j], arr[i]

rev(arr, i+1, n-1)

return ''.join(arr)

def rev(arr: list, start: int, end: int) -> None:

while start < end:

swap(arr, start, end)

start += 1

end -= 1

def swap(arr: list, i: int, j: int) -> None:

temp = arr[i]

arr[i] = arr[j]

arr[j] = temp

if __name__ == '__main__':

s = "gfg"

print(next_permutation(s))

C#

using System;

class GFG {

public static char[] NextPermutation(string s) {

char[] arr = s.ToCharArray();

int n = arr.Length;

int i = n - 2;

while (i >= 0 && arr[i] >= arr[i+1]) {

i--;

}

if (i < 0) {

string st = "No next Permutation possible";

char[] ar = st.ToCharArray();

return ar;

}

int j = n - 1;

while (j >= 0 && arr[j] <= arr[i]) {

j--;

}

Swap(arr, i, j);

Reverse(arr, i+1, n-1);

return arr;

}

private static void Swap(char[] arr, int i, int j) {

char temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

private static void Reverse(char[] arr, int start, int end) {

while (start < end) {

Swap(arr, start, end);

start++;

end--;

}

public static void Main(string[] args) {

string str2 = "gfg";

Console.WriteLine(NextPermutation(str2));

}

Javascript

function next_permutation(s) {

let arr = Array.from(s);

let n = arr.length;

let i = n - 2;

while (i >= 0 && arr[i] >= arr[i+1]) {

i--;

}

if (i < 0) {

return "No next Permutation possible";

}

let j = n - 1;

while (j >= 0 && arr[j] <= arr[i]) {

j--;

}

let temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

rev(arr, i+1, n-1);

return arr.join('');

}

function rev(arr, start, end) {

while (start < end) {

swap(arr, start, end);

start++;

end--;

}

function swap(arr, i, j) {

let temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

let s = "gfg";

console.log(next_permutation(s));

Time Complexity:

In the worst case, the first step of next_permutation takes O(n) time.
The binary search takes O(log n) time.
The reverse takes O(n) time.

Overall time complexity is O(n). Where n is the length of the string.
Auxiliary Space is O(1), because no extra space is used.

This article is contributed by Harshit Gupta. If you like GeeksforGeeks and would like to contribute, you can also write an article on write.geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks. Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Last Updated :
06 Apr, 2023

Like Article

Save Article

Источник

Для
начала введем понятие
лексикографического
порядка.
Лексикографическим
порядок называется
потому, что он лежит в основе упорядочения
слов в словаре. Например, слово able
в
английском
словаре стоит перед словом gray,
так
как в алфавите буква а
стоит
перед буквой g.

ОПРЕДЕЛЕНИЕ
8.46. Для
заданного линейно упорядоченного
множества S
лексикографический
порядок <
на
строках элементов множества S
определяется
следующим образом: а
<
b,
если
а
= а₁,a₂,a₃,…a_m,
b
= b₁,b₂,b₃,…b_n,
и
выполнено
одно из условий: а) а₁
< b₁;
б) а_i
= b_i
для
всех 1 <
i
<
k
и
а_k₊₁
< b_k₊₁;
в) а_i
= b_i
для
всех 1 <
i
<
т. и
т
< n.

Теперь
будем формировать множество всех
перестановок элементов линейно
упорядоченного
множества. Для простоты рассмотрим
только перестановки первых n
целых чисел, отметив, что метод справедлив
и для прочих случаев. Пусть строка
а₁,a₂,а₃
…а_n
обозначает
перестановку

Таким образом,
51342 представляет перестановку

(	1	2	3	4	5	)
5	1	3	4	2

Для
нахождения всех перестановок необходимо
иметь возможность сформировать
перестановку, следующую за данной
согласно лексикографическому порядку.
.Поэтому
для формирования следующей строки
необходимо менять те символы, которые
ближе всего к концу. Предположим, что
a_i
> а_i₊₁
для т <
a_i
< n. Если
бы это условие выполнялось для всех
неотрицательных т,
то мы
имели бы лексикографически
наибольшую строку, что означало бы
завершение процесса. Поэтому
допустим, что существует такое т,
что а_i
> а_i₊₁
для т <
i
< n,
но а_т
< а_m₊₁.
Если переупорядочить все а_i,
где i
> m,
то мы создадим строку, которая будет
лексикографически меньше

Таким образом,
приходим к следующей процедуре:

Процедура
Формирование
перестановки (а₁
,…, a_n)
Найти
т
такое,
что а_i
>
а_i_+

1
для т
< i
< n,
но а_т
<
а_m₊₁;
Выбрать
наименьшую цифру а_i,
такую что i
>
m
и а_т
< а_i;
Поменять
местами a_m
и а_i;
Переупорядочить
все а_i,
стоящие после нового а_т,
в
возрастающем порядке; Конец
процедуры.

Теперь
рассмотрим метод формирования всевозможных
сочетаний из n
элементов
множества S.
Мы
не будем использовать лексикографический
порядок элементов множества S,
а
воспользуемся лексикографическим
порядком на строках
бинарных чисел. Напомним, что любому
сочетанию элементов из n
элементов
соответствует бинарная строка длины
n.
Если
множество S
задано в виде {а₁,
а₂,
а₃,
…
а_n}.
то единица на месте k:-го
бита в бинарной строке показывает, что
а_k
присутствует в выбранном подмножестве,
в то время как 0 в том же месте
бинарной строки показывает, что а_k.–
не включено в выбранное подмножество.
Например,
если множество S
представляет
собой {а₁,
а₂,
а₃,
а₄,
а₅},
то
10110 соответствует выбору подмножества
{а₁,
а₃,
a₄},
а 10001 – выбору подмножества {
а₁,
а₅}.
Таким
образом, для формирования всех сочетаний
из множества n
элементов
достаточно сформировать все бинарные
строки длины n.
С этой целью проще
всего сосчитать от 0 до 2ⁿ
– 1, используя бинарные строки длины n.

Эквивалентный
метод состоит в том, чтобы показать, как
по данной бинарной
строке длины n
построить
следующую бинарную строку такой же
длины. Для этого достаточно найти в
строке первый 0 справа, заменить его на
1, а все элементы справа от новой
единицы заменить на 0. Как говорилось
ранее, формирование сочетаний
не является лексикографическим
упорядочением объектов множества, а
представляет собой лексикографическое
упорядочение бинарных строк.

13.
Приложения комбинаторики к задачам
теории вероятности в случае равновозможности
всех исходов эксперимента.

Наша
концепция вероятности будет зависеть
от того, что мы понимаем под экспериментом.
Оставив термин «эксперимент»
неопределенным, зададимся целью,
чтобы он отвечал следующим условиям:
а) эксперимент
дает более одного исхода;
б)исход
точно не известен;
в) конечное
множество всех исходов может быть
определено до начала эксперимента;
г) эксперимент
можно повторить при тех же условиях.
Примером
эксперимента является подбрасывание
двух монет. В этом случае множество
исходов
S
= {(H,H),
(H,
T),
(T,
H),
(T,
T)},
где
H
обозначает
падение монеты вверх «орлом», а Т
–
падение монеты «решкой» вверх.

ОПРЕДЕЛЕНИЕ
8.48. Выборочное
пространство, или
множество
элементарных событий –
это множество всех исходов эксперимента.
Событие
– подмножество
выборочного пространства.

Таким
образом, множество S
– это
выборочное пространство. На языке теории
множеств выборочное пространство
S
является универсом.

имеем

Интуитивно,
вероятность события – это вероятность
того, что событие наступит. Если
эксперимент повторяется несколько раз,
то вероятность события – это
частота наступления события. В этом и
следующих разделах будем предполагать,
что все исходы эксперимента равновозможны.
Заметим, что это вовсе
не означает,
что все события в мире равновозможны.
Просто такое предположение
дает нам возможность использовать
комбинаторные принципы, поскольку
вероятность
– одно из основных приложений
комбинаторики. С учетом этого предположения
сформулируем определение вероятности.
ОПРЕДЕЛЕНИЕ
8.49. Пусть
S
– множество
всех возможных исходов эксперимента.
Вероятность
Р(А) наступления
события А
определяется
как отношение

P(A)

|A|

|S|

ТЕОРЕМА
8.52. Если
A
и В
– непересекающиеся множества
исходов эксперимента, то Р(A

B)
= P(A)
+ P(B)

ДОКАЗАТЕЛЬСТВО.
Используя
принцип сложения,

ТЕОРЕМА
8.53. Если
S
–
выборочное пространство, А’
—
дополнение множества А
до
множества S
как универса, то а) P(S)
= 1.
б) Р(А’)
= 1 – Р(А).
в) Р()
= 0.
г)Для
каждого события А
имеем
Р(А)
>
0.
д)Если
А

В,
то
Р(А)
<
Р(В).
е)Для
каждого события А
имеем
0 <
Р(А)
<
1.

ДОКАЗАТЕЛЬСТВО,
a)
P(S)
=
|S|/|S|
= 1.
б) Согласно
пункту (а) и предыдущей теореме имеем
1
= P(S)
= Р(А

А’)
=
Р(А)
+ Р(А’).
Поэтому
Р(А’)
=
1 – Р(А).

в)Согласно
пункту (б) имеем Р()
=
1 – Р(‘)
=
1 – P(S)
=
1– 1 = 0.

г)Поскольку
должно существовать не менее одного
исхода, то |S|
> 0.
Кроме того, |А|
>
0,
учитывая, что множество А
содержит
некоторое число элементов. Следовательно,

д) Если
А

В, то В = А+(В – А). Поэтому
Р(B)
=
Р(А
+ (В – А)) =
Р(А)
+ Р(В – А) и
Р(В)
–
Р(А)
=
Р(В
–
А), Однако,
согласно пункту (г),
P(B
– A)
>
0

Поэтому
Р(В)
– Р(А) >
0
и
P(A)

P(B)
е)
Поскольку А

S,
то
Р(А) <
Р(S)
= 1. Объединяя с пунктом (г), получаем
0
<

P(A)
<
1

ТЕОРЕМА
8.56. Если
А
и
В
– множества
исходов эксперимента, то
Р(А

В)
= Р(А) + Р(В) – Р(А 
В).

ДОКАЗАТЕЛЬСТВО.
На
рис. 8.12 показано, что А
= (А – В) 
(А

В),
В
= {В – A)

(А

В),
и
A

В
= (А – В) 
(А

В)

(В
–
А),
где (А
–
В),
(А 
В)
и
(В
– А) – попарно
непересекающиеся множества.

Поэтому,
по теореме 8.6 имеем
Р(А)
= Р((А
– B)

(A

В)) =
Р(А
– В)
+ Р(А

В),
Р(В)
= Р((В
–
A)

(А

В))
=
Р(В
– А)
+ Р(А

В),
и
Р(А
В)
=
Р((А
– В)

(A

В) 
(В – А)) =
Р(А
– В) + Р(А

В) + Р(В
–
А).

Следовательно,
Р(А)
+ Р(В)
= (Р(А
–
В) + Р(А

В)) + (Р(В
–А)
+ Р(А

В))
=
(Р(А
– В)+Р(А

В)
+ (Р(В – А)) + Р(А 
В)
= Р(А 
В)+Р(А

В),
так
что Р(А

B)
= Р(А) + Р(В) – Р(А

В).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник