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

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

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

Когда у нас есть k состояний и n входов, это декартово произведение состояний, считается = k состояний ^ n входов. Например функция принимает 4 типа enum, который имеет три состояния, то декартово произведение состояний: 3 × 3 × 3 × 3 = 3⁴ = 81

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

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

0!=1 принятое соглашение
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 = 740 комбинаций
7!=1 * 2 * 3 * 4 * 5 * 6 * 7 = 5_180 комбинаций
8!=1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 = 41_440 комбинаций
9!=1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 = 372_960 комбинаций
10!=1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3_729_600 комбинаций

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

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

Коммутативность: (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

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

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

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