Количество различных подмножеств множества подмножеств

[mustang]

Поскольку maxal ввёл аппарат бинарных матриц, то приведу описание задачи через бинарные матрицы и операции с ними.

Пусть $C$ - бинарная матрица размера $[n \times m]$, где $m = 2^n-1$, причём матрица $C$ состоит из блоков — матриц $C^k$, где $k \in [1..n]$, а размер блоков $[n \times C^k_n]$, где $C^k_n$ - биноминальный коэффициент.

Пример для n=3:

$C = \begin{vmatrix} 1 & 0 & 0\\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{vmatrix}\begin{vmatrix} 1 & 1 & 0\\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{vmatrix}\begin{vmatrix} 1 \\ 1 \\ 1 \end{vmatrix}$

Столбец такой матрицы - это элемент покрытия множества $U$, $|U|=n$.

Бинарный вектор $v^{Ax}$ - это выбор конкретного покрытия множества $U$.

Тогда мы можем сформулировать требования к вектору $v_{Ax}$:

1. $\forall C_i, C_i$ AND $v^{Ax} \ne 0$ - это требование "быть покрытием", а $C_i$ - $i$-ая строка матрицы $C$

2. $\forall C_i, C_j, j>i, (C_i$ XOR $C_j)$ AND $v^{Ax} \ne 0$ - это требование "быть Т0-покрытием"

3. Для любых двух векторов-аксиом не существует такой перестановки строк матрицы $C$, что для любой строки матрицы $C$ битовое AND до и после перестановки с одним и другим вектором-аксиомой равны друг другу.

Третье условие муторно записывать в математической нотации, пишу "заклинание".

Для того, чтобы уйти от полного перебора в п.3 заметим, что из всего класса эквивалентных аксиом нам нужно выбрать одного представителя по какому-то критерию. С учётом введенных обозначений таким критерием может быть минимальным числом, представленным двоичной записью вектора-аксиомы.

Будем представлять вектор-аксиому как набор n векторов-компонент $v^{Ax}_k$, соответствующих блокам матрицы $C$.

Тогда очевидно, что если [i+1..n] векторов-компонент пусты, а $v^{Ax}_i$-й вектор-компонент содержит $p$ единиц (бит), то вид этого компонента будет $|1…10…0|$ (младший разряд находится слева).

Такой подход к блочному представлению и поиску минимального числа - представления вектора-аксиомы позволяет немного "сэкономить" на переборах. Плюс разбивает задачу на поиск минимальных векторов - представителей класса эквивалентных аксиом - на подзадачи, где каждая подзадача определена кортежем из количества бит в каждом векторе-компоненте.

Если найден некоторый минимальный вектор с нулевыми [i+1..n] компонентами, то добавление i-ой компоненты с m битами также образует минимальный вектор. Но такой способ построения, по крайней мере, в однопроходном варинте, не даёт возможность построить все вектора-аксиомы — представителей классов эквивалентных векторов.

Однако мы можем ограничить число операций по проверке перестановок: мы можем проверять минимальность не всего вектора, а покомпонентно.

Пусть $\mathfrak{B}$ - матрица$[n \times n]$ перестановок строк, а $\mathfrak{P}$ - матрица$[m \times m]$ перестановок столбцов.

Тогда $\mathfrak{B} \times C = C \times \mathfrak{P}$, а $v^{Ax} = (v^{Ax}_{perm})^T \times \mathfrak{P}$

По условию поиска минимального элемента, перестановка $\mathfrak{B}$ должна быть такой, чтобы старший ненулевой компонент вектора-аксиомы сохранял свою структуру: $|1…10…0|$.

Это означает, что $\mathfrak{P}$ имеет блочный вид: $\begin{pmatrix} \mathfrak{P}^' & O\\ O & E \end{pmatrix}$, где $\mathfrak{P}^'$ - матрица $[p \times p]$ - матрица перестановки первых $p$ столбцов для которых старший ненулевой вектор-компонент имеет 1.

Тогда $\mathfrak{B} = C \times \mathfrak{P} \times C^{+}$, где $C^{+}$ - псевдообратная матрица к $C$

Что можно сказать о структуре матрицы перестановки строк $\mathfrak{B}$ ?

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