Разобрать каждое подмножество k-элементов n-элементного вектора

Вам просто нужен bigint. В Rust есть различные библиотеки bigint, самая быстрая из них — коврик. Однако он связан с GMP, что делает его лицензированным LGPL и не работает на Windows-MSVC.

Вот как с ним может выглядеть ваш код (не проверялось):

use rug::{Assign, Integer};

pub struct Combinations {
    result: Integer,
    temp1: Integer,
    temp2: Integer,
    temp3: Integer,
}

impl Combinations {
    pub fn new(upper_bound_length: usize) -> Self {
        Self {
            result: Integer::with_capacity(upper_bound_length),
            temp1: Integer::with_capacity(upper_bound_length),
            temp2: Integer::with_capacity(upper_bound_length),
            temp3: Integer::with_capacity(upper_bound_length),
        }
    }
}

/// This is an operation `rug` doesn't natively provide. It can be accelerated more if it's a hotspot,
/// via SIMD and such.
fn trailing_zeros(v: &Integer) -> u32 {
    let mut result = 0;
    for &limb in v.as_limbs().iter().rev() {
        let trailing_zeros = limb.trailing_zeros();
        result += trailing_zeros;
        if trailing_zeros < gmp_mpfr_sys::gmp::limb_t::BITS {
            break;
        }
    }
    result
}

pub fn set_next_bit_permutation(v: &mut Combinations) {
    v.temp1.assign(&v.result - 1);
    v.temp1 |= &v.result;
    v.temp2.assign(!&v.temp1);
    v.temp1 += 1;
    v.temp3.assign(-&v.temp2);
    v.temp2 &= &v.temp3;
    v.temp2 -= 1;
    v.temp2 >>= trailing_zeros(&v.result) + 1;
    v.result.assign(&v.temp1 | &v.temp2);
}

Зависимости:

gmp-mpfr-sys = "1.6.4"
rug = { version = "1.25.0", default-features = false, features = ["integer"] }

Помимо оптимизированных алгоритмов и реализации rug, у него есть еще одна потрясающая особенность: возможность присваивать результат вычисления непосредственно другой переменной без выделения (что происходит с незавершенными операциями и assign()). Альтернативой для таких библиотек, как num-bigint, будет сначала назначить левую переменную цели, а затем использовать op=.

Если вы готовы перекомпилировать для каждого размера, вы можете работать еще быстрее, используя целые числа произвольного размера во время компиляции, что позволит компилятору полностью развернуть циклы. Крейт bnum — это пример крейта, который реализует целые числа произвольного размера, хотя я не знаю, будет ли он таким же быстрым, как rug, поскольку его реализация не так оптимизирована, как GMP.

На самом деле это легко и эффективно сделать с помощью отсортированного массива из k индексов.

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

Поэтому мы инициализируем массив наименьшими индексами: A=[0, 1, ... k-1]

Затем, чтобы привести в порядок следующий массив индексов подмножества, просто:

1. Найдите наименьший индекс i такой, что i == k-1 или A[i+i] > A[i]+1.
2. Приращение A[i]
3. Установите для предыдущих элементов значение [0, 1,... i-1]

Когда вы увеличите A[k-1] до n, все готово.