Комбинаторика

Правило умножения
Комбинации
Правило суммирования
Перестановки
Размещение
Сочетание
Свойства Коммутативность и Ассоциативность, Дистрибутивность
Сочетания и распределение вариантов
Подмножества через битовые маски (bit masks)

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

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

Комбинаторика вместе с другими дисциплинами из дискретной математики используется для построения алгоритмов. Например, алгоритмов поиска оптимального маршрута или оптимизации цепей поставок.

Комбинаторику применяют для оценки времени работы алгоритмов и для их ускорения. Это помогает делать эффективнее работу поисковых систем, голосовых помощников, навигаторов и других сервисов.

Декартово произведение

Когда у нас есть k состояний и n входов, это декартово произведение состояний, считается = k состояний ^ n входов.

Например, функция принимает 4 типа enum, который имеет три состояния, то декартово произведение состояний: 3 × 3 × 3 × 3 = 3⁴ = 81

Правило умножения (произведения)

(«И» → умножение)

Если некоторое событие происходит n разными способами, а другое событие — m разными способами, то число разных способов, которыми могут произойти оба события, равно n × m.

Или так, если объект A можно выбрать n способами и после каждого такого выбора объект B можно выбрать m способами, то для пары «A и B» есть n × m вариантов выбора.

Пример: "Взлом кода". Предположим, что PIN-код состоит из двух цифр и латинской буквы. На то, чтобы ввести код один раз, уходит в среднем одна секунда. Какое максимальное время потребуется, чтобы подобрать правильный PIN-код?

Две цифры можно набрать 100 способами (00–99) и букву — 26 способами (A–Z). Следовательно, всего существует 100 × 26 = 2600 PIN-кодов. В худшем случае, чтобы подобрать правильный, нам придется перепробовать их все. Через 2600 секунд (то есть через 43 минуты) мы его точно взломаем.

Комбинации

Биномиальный коэффициент - это количество способов, которыми можно извлечь m элементов из ряда, состоящего из n элементов, независимо от порядка их следования:

$C (m n) = \frac{n !}{m ! ( n - m )!}$

Пример: Сколько способов выбрать 2 элемента из 5

$C (2 5) = \frac{5 !}{2 ! , 3 !} = \frac{120}{2 \cdot 6} = 10$

Правило суммирования

(«ИЛИ» → суммирование)

Если есть несколько несовместимых способов получить результат, то:

общее число способов = сумма способов каждого варианта

Например: В коробке 5 синих шаров и 3 красных шаров. Сколько способов выбрать один шар?

Есть два несовместимых случая, одновременно оба выбрать нельзя, значит это альтернативы:

Выбрать синий шар → 5 способов

Выбрать красный шар → 3 способа

Складываем: 5+3=8 способов выбрать один шар

Если бы задача была («И» → умножаем): выбрать один синий и один красный. Тогда это умножение 5×3=15

Запись через Σ

Можно ввести индекс по «типу шара»:

(i = 1) → синие
(i = 2) → красные

Тогда:

$\sum_{i = 1}^{2} a_{i}$

где:

(a_1 = 5) (синие)
(a_2 = 3) (красные)

Подстановка

$\sum_{i = 1}^{2} a_{i} = a_{1} + a_{2} = 5 + 3 = 8$

Перестановки

Перестановка n объектов/элементов — это способ их последовательного расположения с учётом порядка. Например, abc, bca и cab — это разные перестановки трёх букв.

Когда у нас N вариантов, то возможных комбинаций последовательностей перестановки: N!

Перестановку n объектов ещё называют перестановкой длины n. Количество всех таких перестановок обозначается как $P_{n} = n!$

Факториал натурального числа n — это произведение всех натуральных чисел от до n. Порядок множителей значения не имеет. Такое произведение обозначается через n!.

$n! = n \times (n -1) \times (n -2) ... \times 3 \times 2 \times 1$

Сколькими способами можно выбрать первый элемент из n? После того как он будет выбран, сколькими способами можно выбрать второй? Сколько вариантов останется для третьего?

Факториал числа:

0!=1 принятое соглашение
1!=1 комбинация
2!=1 * 2 = 2 комбинации
3!=1 * 2 * 3 = 6 комбинаций
4!=1 * 2 * 3 * 4 = 24 комбинации
5!=1 * 2 * 3 * 4 * 5 = 120 комбинаций
6!=1 * 2 * 3 * 4 * 5 * 6 = 720 комбинаций
7!=1 * 2 * 3 * 4 * 5 * 6 * 7 = 5_040 комбинаций
8!=1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 40_320 комбинаций
9!=1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 = 362_880 комбинаций
10!=1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3_628_800 комбинаций

Например в распределенной системе где мы не можем контролировать порядок прихода событий. Возникают события в разных последовательностях но мы должны их обрабатывать как единое сообщение, если у нас 5 возвожных событий то они дают 120 комбинаций хотя это на самом деле один вариант сообщения.

Если в последовательности из n элементов r идентичны, существуют r! способов переупорядочить их. То есть n! включает r! таких комбинаций. Чтобы получить число уникальных комбинаций, нужно разделить n! на этот излишек.

Например, число различных сочетаний букв E в "CODE ENERGY" равняется $\frac{10}{3 !}$ .

Свойства структур данных, такие как Коммутативность и Ассоциативность убирают взрыв комбинаций. Это достигается правильной реализацией операции merge.

Пример перестановок (permutations): программа, которая генерирует все возможные перестановки заданного набора символов. (Сгенерировать все перестановки множества из n различных элементов)

Есть набор символов, например {A, B, C}, нужно использовать все элементы, каждый ровно один раз (т.е. AAA нельзя), порядок важен:

fn permute(chars: &mut Vec<char>, start: usize) {
    if start == chars.len() {
        let s: String = chars.iter().collect();
        println!("{}", s);
        return;
    }
    for i in start..chars.len() {
        chars.swap(start, i);
        permute(chars, start + 1);
        chars.swap(start, i); // откат (backtracking)
    }
}
fn main() {
    let mut chars = vec!['A', 'B', 'C'];
    permute(&mut chars, 0);
}

Размещение

Размещение из n по k — это упорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть некая перестановка k выбранных элементов из n.

Размещения делятся на два основных типа в зависимости от того, могут ли элементы повторяться в выборке:

Размещения без повторений

Используются, когда каждый выбранный элемент уникален. Количество способов выбрать и расположить $k$ элементов из $n$ вычисляется по формуле:

$A_{n}^{k} = \frac{n !}{( n - k )!}$

Пример: перед Вами мешок, в котором лежат 10 билетов, пронумерованных от 1 до 10. Вы по очереди достаете три билета.

Первый вытянутый билет приносит владельцу Автомобиль.

Второй вытянутый билет приносит Смартфон.

Третий вытянутый билет приносит Кружку.

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

Шаг 1: Для «Автомобиля» у Вас есть 10 вариантов (любой из 10 билетов в мешке).

Шаг 2: Для «Смартфона» остается уже 9 вариантов (один билет уже снаружи, он выиграл авто).

Шаг 3: Для «Кружки» остается 8 вариантов.

Вы перемножаете эти возможности. Как это выглядит через формулу: $A_{10}^{3} = \frac{10 !}{( 10 - 3 )!} = \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = 10 \times 9 \times 8 = 720 комбинаций .$

Пример: программа для генерации всех возможных последовательностей фиксированной длины без повторения символов.

Повторения запрещены:

AA нельзя
BB нельзя
CC нельзя

fn generate_without_repetition(chars: &[char], length: usize, current: String) {
    if current.len() == length {
        println!("{}", current);
        return;
    }
    for &ch in chars {
        // пропускаем символ, если он уже есть в строке
        if current.contains(ch) {
            continue;
        }
        let mut next = current.clone();
        next.push(ch);
        generate_without_repetition(chars, length, next);
    }
}
fn main() {
    let chars = ['A', 'B', 'C'];
    generate_without_repetition(&chars, 2, String::new());
}

Размещения с повторениями

Используются, когда один и тот же элемент может быть выбран несколько раз. Количество таких способов определяется формулой:

$\overset{ˉ}{A}_{n}^{k} = n^{k}$

Пример: Сколько трехзначных кодов можно составить из цифр 1, 2, 3, 4 и 5, если цифры могут повторяться?

$\overset{ˉ}{A}_{5}^{3} = 5^{3} = 125$

$n = 5$ — это количество цифр, которые нам доступны

$k = 3$ — это длина кода

Пример: генерация всех двоичных строк длины n:

Для каждой позиции: есть 2 варианта (0 или 1), позиции независимы. Почему с повторениями? Потому что один и тот же символ можно использовать несколько раз в одной последовательности, 00 и 11 возможны именно из-за повторений.

fn generate_binary_sequences(n: usize) {
    let total = 1 << n; // 2^n комбинаций

    for i in 0..total {
        // выводим число как бинарную строку с ведущими нулями
        println!("{:0width$b}", i, width = n);
    }
}
fn main() {
    generate_binary_sequences(2);// 2 bit
    println!("---");
    generate_binary_sequences(3);// 3 bit
}

Размещения с повторениями, можно брать любой элемент сколько угодно раз

fn generate_with_repetition(chars: &[char], length: usize, current: String) {
    if current.len() == length {
        println!("{}", current);
        return;
    }

    for &ch in chars {
        let mut next = current.clone();
        next.push(ch);

        generate_with_repetition(chars, length, next);
    }
}

fn main() {
    let chars = ['A', 'B', 'C'];// из n = 3 символов получаем: n^k=3^3=27 вариантов

    generate_with_repetition(&chars, chars.len(), String::new());
}

Сочетание

Когда порядок выбора или расположения не важен, говорят о сочетании.

Сочетание из n по k — это неупорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть набор, для которого порядок выбора не имеет значения.

Формула обозначается буквой $C$ (от латинского Combinatio):

$C_{n}^{k} = \frac{n !}{k ! ( n - k )!}$

Пример: перед Вами мешок, в котором лежат 10 билетов, пронумерованных от 1 до 10. Вы по очереди достаете три билета. Каждый из них дает одинаковый приз, например, 100 золотых монет.

Вам всё равно, вытянули Ваш билет первым или третьим — Вы всё равно получите свои 100 монет. Поэтому комбинации ${1, 2, 3}$ , ${3, 2, 1}$ и ${2, 1, 3}$ для нас теперь — это один и тот же результат.

Сколькими способами можно выбрать 3 человека из 10 просто для участия в телепередаче (без распределения ролей)?

$C_{10}^{3} = \frac{10 !}{3 ! \cdot ( 10 - 3 )!} = \frac{10 !}{3 ! \cdot 7 !} = 120$

Вывод: Способов выбрать «просто группу» ( $120$ ) всегда меньше, чем способов выбрать «группу с распределением мест» ( $720$ ), потому что мы не считаем перестановки внутри самой группы за новые варианты.

Пример: генерация комбинаций вариантов без повторений и без учёта порядка, AB=BA:

fn combinations(chars: &[char], k: usize, start: usize, current: &mut Vec<char>) {
    if current.len() == k {
        println!("{:?}", current);
        return;
    }

    for i in start..chars.len() {
        current.push(chars[i]);
        combinations(chars, k, i + 1, current);
        current.pop();
    }
}

fn main() {
    let chars = ['A', 'B', 'C'];

    let mut k = 3;
    println!("k=3");
    combinations(&chars, k, 0, &mut Vec::new());

    println!("\nk=2");
    k = 2;
    combinations(&chars, k, 0, &mut Vec::new());
}

Свойства Коммутативность и Ассоциативность, Дистрибутивность

Коммутативность: (90% комбинаторного взрыва устраняется одним свойством, порядок событий больше не влияет на результат)

A + B = B + A

A = {2, 4}
B = {1, 3}
{2,4} ∪ {1,3} = {1,2,3,4}

a.merge(&b)={1,2,3,4}
b.merge(&a)={1,2,3,4}
a.merge(&b) == b.merge(&a) => {1,2,3,4}


let r1 = a.merge(&b);
let r2 = b.merge(&a);
assert_eq!(r1, r2);   // проверка коммутативности

В коде это означает что структура (BTreeSet) данных должна быть всегда в отсортированном состоянии и сортировка должна быть фиксированной и одинаковой

Ассоциативность: (9% комбинаторного взрыва, защищает от разных "группировок" событий)

Ассоциативность - это свойство группировки операций:


(A & B) & C = A & (B & C)

(A | B) | C = A | (B | C)

(A + B) + C = A + (B + C)

Пример:
A = {2, 4}
B = {1, 3}
C = {5, 6}

Вариант №1: (A || B) || C
A || B = {1,2,3,4}
(A || B) || C: {1,2,3,4} ∪ {5,6} = {1,2,3,4,5,6}

Вариант №2: A || (B || C)
B || C = {1,3} ∪ {5,6} = {1,3,5,6}
A || (B || C):{2,4} ∪ {1,3,5,6} = {1,2,3,4,5,6}

Сравниваем:
(A || B) || C  = {1,2,3,4,5,6}
A || (B || C)  = {1,2,3,4,5,6}

(a.merge(b)).merge(c) == a.merge(b.merge(c))

В коде это означает, итог объединения должен зависеть только от содержимого, а не от последовательности вызовов merge

BTreeSet ассоциативна, потому что:

insert() в BTreeSet всегда кладёт туда, где должен быть элемент
порядок вставки НЕ влияет
дубликаты игнорируются
структура сама сортирует элементы

use std::collections::BTreeSet;

fn merge(a: &BTreeSet<i32>, b: &BTreeSet<i32>) -> BTreeSet<i32> {
    let mut out = a.clone();
    out.extend(b.iter().cloned());
    out
}

fn main() {
    // ----------------------
    // Исходные данные
    // ----------------------
    let mut A = BTreeSet::new();
    A.insert(7);
    A.insert(1);
    A.insert(4);

    let mut B = BTreeSet::new();
    B.insert(2);
    B.insert(7);

    let mut C = BTreeSet::new();
    C.insert(4);
    C.insert(9);

    println!("A = {:?}", A);
    println!("B = {:?}", B);
    println!("C = {:?}", C);

    // ----------------------
    // merge в разном порядке
    // ----------------------

    let ab = merge(&A, &B);
    let abc1 = merge(&ab, &C);

    let bc = merge(&B, &C);
    let abc2 = merge(&A, &bc);

    println!("\n(A ∪ B) ∪ C = {:?}", abc1);
    println!("A ∪ (B ∪ C) = {:?}", abc2);

    // Проверка ассоциативности
    assert_eq!(abc1, abc2);

    println!("\nИтог одинаковый в любом порядке!");
}

Знак ∪ — это объединение множеств.

A = {1, 4, 7}
B = {2, 7}
C = {4, 9}

(A ∪ B) ∪ C = {1, 2, 4, 7, 9}
A ∪ (B ∪ C) = {1, 2, 4, 7, 9}

Итог одинаковый в любом порядке!

Дистрибутивность (распределительное свойство) - это свойство, когда одна операция "распределяется" над другой:

& дистрибутивна над | (как умножение над сложением в арифметике):
```
a & (b | c) = (a & b) | (a & c)
```
| дистрибутивна над & (это особенность булевой алгебры!):
```
a | (b & c) = (a | b) & (a | c)
```

Пример:

fn main(){
    //Булева алгебра (работает в обе стороны):-----------------------------------
    let a = true;
    let b = false;
    let c = true;

    // 1. & распределяется над |
    let left1 = a & (b | c);        // true & (false | true) = true & true = true
    let right1 = (a & b) | (a & c); // (true & false) | (true & true) = false | true = true
    assert_eq!(left1, right1); 

    // 2. | распределяется над &
    let left2 = a | (b & c);        // true | (false & true) = true | false = true
    let right2 = (a | b) & (a | c); // (true | false) & (true | true) = true & true = true
    assert_eq!(left2, right2); 

    // С битовыми операциями:----------------------------------------------------
    let a = 0b101; // 5
    let b = 0b011; // 3
    let c = 0b110; // 6

    // 1. & распределяется над |
    let left1 = a & (b | c);        // 101 & (011 | 110) = 101 & 111 = 101
    let right1 = (a & b) | (a & c); // (101 & 011) | (101 & 110) = 001 | 100 = 101
    assert_eq!(left1, right1); 

    // 2. | распределяется над &
    let left2 = a | (b & c);        // 101 | (011 & 110) = 101 | 010 = 111
    let right2 = (a | b) & (a | c); // (101 | 011) & (101 | 110) = 111 & 111 = 111
    assert_eq!(left2, right2); 
}

Пример inplace swap

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

fn main() {
    // В качестве примера применимости свойства `a ^ a = 0` 
    // к любому битовому вектору a рассмотрим следующую программу:
 
    let mut a = 5;
    let mut b = 88;
    println!("a={:08b} b={:08b}",a,b);// a=00000101 b=01011000
    /* 
    Шаг 1 смесь (a ⊕ b) 
    по сути это создание маски из которой можно последовательно 
    доставать либо первую либо вторую составляющую часть
    */   
    b = a ^ b;
    println!("a={:08b} b={:08b}",a,b);// a=00000101 b=01011101
    /* 
    Шаг 2 итоговое значение для a
    подстановка из Шага 1:
      a = a ^ b = a ^ (a ^ b) =>
    далее свойство ассоциативности:
      => (a ^ a) ^ b =>
    далее свойство самообратимости: a ^ a = 0:
      => 0 ^ b =>
    далее свойство нейтральный элемент: 0 ^ b = b:
      => a = b
    */   
    a = a ^ b;
    println!("a={:08b} b={:08b}",a,b);// a=01011000 b=01011101
    /* 
    Шаг 3 итоговое значение для b
    подстановка b из Шага 1 и a из Шага 2:
      b = a ^ b = a ^ (a ^ b) =>
      
    коммутативность во второй скобке:
      => b ^ (b ^ a)
    
    ассоциативность:
      => (b ^ b) ^ a
    
    самообратимость (b ^ b = 0):
      => 0 ^ a
    
    нейтральный элемент (0 ^ a = a):
      => a
    итог: b получает значение a
    */  
    b = a ^ b;
    println!("a={:08b} b={:08b}",a,b);// a=01011000 b=00000101
    println!("a={a} b={b}");// a=88 b=5
    // p.s. такой способ не дает выигрыша в производительности; 
    // выигрыш имеет место лишь в форме интеллектуального развлечения.
}

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

C(n, k) (сочетания) — это сколько способов выбрать k элементов из n, без учета порядка.

Порядок не важен → [A,B,C] = [C,A,B]
Важно только, какие элементы выбраны

Применение, есть 5 реплик базы данных replicas = [R1, R2, R3, R4, R5]. Нам нужно принять решение о подтверждении записи при достаточном большинстве в репликах (кворум). Нужно собрать кворум 3 из 5. Сколько разных комбинаций реплик могут образовать кворум?

// Считаем C(5,3) = 5! / (3! * (5-3)!) = 10

fn comb(n: usize, k: usize) -> usize {
    (0..k).fold(1, |acc, i| acc * (n-i) / (i+1))
}

fn main() {
    println!("C(5,3) = {}", comb(5,3)); // 10
    println!("C(5,2) = {}", comb(5,2)); // 10
}

То есть всего 10 возможных наборов реплик, которые могут подтвердить запись:

Генерация сочетаний (combinations)

Реплики: [R1, R2, R3, R4, R5]
Нужно выбрать 3:

Берём R1, тогда оставшиеся 2 элемента нужно выбрать из [R2,R3,R4,R5] 
    => [R1,R2,R3], [R1,R2,R4], [R1,R2,R5], [R1,R3,R4], [R1,R3,R5], [R1,R4,R5]
Берём R2 (и пропускаем уже использованное [R1]), нужно выбрать 2 из [R3,R4,R5] 
    => [R2,R3,R4], [R2,R3,R5], [R2,R4,R5]
Берём R3, нужно выбрать 2 из [R4,R5] => только [R3,R4,R5]
R4 и R5 → уже нельзя выбрать 3, поэтому дальше нет комбинаций

fn combinations<T: Clone>(arr: &[T], k: usize) -> Vec<Vec<T>> {
    if k == 0 {
        return vec![vec![]];
    }
    if arr.len() < k {
        return vec![];
    }

    let mut result = Vec::new();

    // берем первый элемент
    let first = &arr[0];
    for mut combo in combinations(&arr[1..], k-1) {
        combo.insert(0, first.clone());
        result.push(combo);
    }

    // не берем первый элемент
    result.extend(combinations(&arr[1..], k));

    result
}

fn main() {
    
    let replicas = vec!["R1","R2","R3","R4","R5"];
    let combs = combinations(&replicas, 3);
    for c in combs {
        println!("{:?}", c);
    }
}

[R1,R2,R3]
[R1,R2,R4]
[R1,R2,R5]
[R1,R3,R4]
[R1,R3,R5]
[R1,R4,R5]
[R2,R3,R4]
[R2,R3,R5]
[R2,R4,R5]
[R3,R4,R5]

Практический вывод: мы знаем все варианты, кто может образовать кворум

Применение. Так же используется при распределении задач.

Допустим:

5 воркеров [W1,W2,W3,W4,W5]
Каждая задача должна быть обработана 3 воркерами

Считаем C(5,3) = 10 → 10 возможных комбинаций воркеров для задачи: [W1,W2,W3], [W1,W2,W4], [W1,W2,W5], ...

Теперь алгоритм планировщика может:

Выбрать случайную комбинацию для каждой задачи
Проверить, чтобы один воркер не получил слишком много задач (балансировка)
Контролировать вероятность конфликтов между задачами

Подмножества через битовые маски (bit masks)

Кодирование подмножества в число, в представлении на двоичном уровне каждый бит соответствует одному подмножеству.

В итоге получаем последовательность бит {010}, {110}, ... как множество и теперь мы можем выполнять над ним различные операции: принадлежность, пересечение, объединение, разность, симметрическая разность.

Если у нас есть множество из n элементов:

S = [a, b, c]

А мы знаем, что количество подмножеств будет 2ⁿ (n = количество элементов) т.е. для множества из n=3 подмножеств 2³=8

Вот все 8 вариантов подмножеств и мы можем каждое подмножество закодировать как число от 0 до 2ⁿ-1 в двоичной форме:

Маска	Биты	Подмножество
0	000	{}
1	001	{c}
2	010	{b}
3	011	{b,c}
4	100	{a}
5	101	{a,c}
6	110	{a,b}
7	111	{a,b,c}

Т.е. каждый бит отвечает за включение элемента в подмножество.

...
001 -> ["A"]
010 -> ["B"]
011 -> ["A", "B"]
100 -> ["C"]
101 -> ["A", "C"]
110 -> ["B", "C"]
111 -> ["A", "B", "C"]
...

Маска сама кодирует, какие элементы выбраны:

mask = 5 = 101 → биты 1 и 3 включены → подмножество [A, C]

mask = 3 = 011 → биты 1 и 2 включены → [A, B]

1. Установка бит
Например текущее состояние системы отображено такой маской 1=001={c}. 
Мы хотим изменить состояние и добавить функционал 4=100={a} и 2=010={b} что бы получилось 7=111={a,b,c}.
Для установки (включения) бита в определенной позиции применяется операция OR (|):

1 | 4 | 2 = 7=111={a,b,c}

2. Снятие бит
Если же мы хотим снять бит с позиции т.е. забрать возможность, выключить функционал ... 
применяем операцию AND (&) с инвертированием (~) вычитаемого. 
Заберем 2=010={b} с текущего состояния 7=111={a,b,c} 

7 & (~2) = 5=101={a,c}

3. Переключение битов
Переключение битов операцией (^), установит если был снят и снимит если был установлен. 
Применим к текущему состоянию снова функционал 2=010={b}

5^2=7=111={a,b,c} // т.е. установили b так как он был снят

4. Проверка значения бита
Применям операцию AND (&). Проверим установлены ли все биты в текущем состоянии для функционала 3=011={b,c} 

7 & 3 != 0

т.е. для того чтобы выражение (7 & 3) было истинным, необходимо, 
чтобы все установленные биты второго операнда (3) совпали с установленными битами первого операнда (7).

fn main() {
    // 1. Установка битов (объединение union)
    let mut state = 1;
    println!("state={} биты={:03b}", state, state);// state=1 биты=001
    state |=4;
    state |=2;
    println!("state={} биты={:03b}", state, state);// state=7 биты=111
    // 1 | 4 | 2 = 7=111={a,b,c}

    // 2. Снятие битов (разность множеств)
    state &=!2;
    println!("state={} биты={:03b}", state, state);// state=5 биты=101
    // 7 & (~2) = 5=101={a,c}

    // 3. Переключение битов (toggle если был 1 станет 0, иначе если был 0 станет 1) (симметрическая разность xor)
    state ^= 2;
    println!("state={} биты={:03b}", state, state);// state=7 биты=111

    // 4. Проверка значения бита (пересечение intersection)
    if ((state & 3) != 0){
        println!("бит установлен"); // бит установлен
    }else{
        println!("бит снят"); 
    }

}

fn main() {
    let elements = ["a", "b", "c"];
    let n = elements.len();
    
    for mask in 0..(1 << n) {
        let subset: Vec<_> = (0..n)
            .filter(|i| (mask & (1 << i)) != 0)
            .map(|i| elements[i])
            .collect();
        println!("mask={} биты={:03b} -> {:?}", mask, mask, subset);
    }
    println!("\n\n");
    
    let mask_x = 5; // = {a, c} = 101₂
    let mask_y = 6; // = {b, c} = 110₂
    
    // Пересечение (intersection)
    let mut mask = mask_x & mask_y; // 4 = 100₂ = {c}
    println!("mask={} биты={:03b}", mask, mask);
    
    // Объединение (union)
    mask = mask_x | mask_y; // 7 = 111₂ = {a, b, c}
    println!("mask={} биты={:03b}", mask, mask);
    
    // Разность множеств
    mask = mask_x & (!mask_y);// 1 = 001₂ = {a}
    println!("mask={} биты={:03b}", mask, mask);
    
    // Симметрическая разность (xor)
    mask = mask_x ^ mask_y;// 3 = 011₂ = {a, b}
    println!("mask={} биты={:03b}", mask, mask);
    
    // Легко проверять наличие элемента. Проверка принадлежности одного элемента
    // Пусть mask = 5 = 101₂ = {a, c}
    mask = 5;
    // 1. Проверим, входит ли: a (установленный бит на позиции 0 в 001₂):
    let mut position = 0;
    let is_a = mask & (1 << position) != 0; // true
    println!("Для множества mask={} биты={:03b} является ли множество a=001 его подмножеством? Ответ: {}", 
    mask,mask, is_a);
    
    // 2. Проверим, входит ли: b (установленный бит на позиции 1 в 010₂):
    position = 1;
    let is_a = mask & (1 << position) != 0; // false
    println!("Для множества mask={} биты={:03b} является ли множество b=010 его подмножеством? Ответ: {}", 
    mask,mask, is_a);
    
    // 3. Проверим, входит ли: c (установленный бит на позиции 2 в 100₂):
    position = 2;
    let is_a = mask & (1 << position) != 0; // true
    println!("Для множества mask={} биты={:03b} является ли множество с=100 его подмножеством? Ответ: {}", 
    mask,mask, is_a);

    // Проверка принадлежности подмножества
    let mut subset = 6;// 110 {b, c}
    println!("Для множества mask={} биты={:03b} является ли множество subset={} 
    биты={:03b} его подмножеством? Ответ: {}",
     mask,mask, subset, subset, contains_subset(mask, subset));// flase
    
}

fn contains_subset(set: u32, subset: u32) -> bool {
    (set & subset) == subset
}

Почему так удобно

Нет необходимости хранить массивы массивов (вместо Vec<Vec<T>> используем usize)
Легко проверять наличие элемента через побитовые операции (&)
Можно быстро объединять (|), пересекать (&) и вычитать (^) подмножества

Keyboard shortcuts

Computer Science Bookshelf