Как создать специальное двоичное дерево

Question

Я хочу проиндексировать некоторые данные, где ключ является ulong. Этот ulong (64 бита) представляет собой комбинацию продуктов, где каждый бит ulong является продуктом в комбо.

Так что, если мы получим длинный ключ со значением 3. Это действительно 1 + 2. Это означает, что продукты 1 и 2 присутствуют в комбо.

ulong Combo1 = 1 | 2;
ulong Combo2 = 1 | 4 | 8;

Если я хочу узнать, использует ли Combo1 какой-либо продукт для Combo2, я мог бы просто сделать это:

if((Combo1 & Combo2) != 0)
{
  //They share at least 1 product
}

Это очень красиво и быстро, но становится трудно, если у меня есть:

List<ulong> Combos = new List<ulong>();

И в нем более 1 миллиона комбинированных ключей (ключ представляет используемые продукты).

Как я могу проиндексировать этот список ulongs, чтобы я мог зациклить его и сделать следующее:

foreach(ulong combo in Combos)
{
  //Find all the combos in Combos where no product is shaded
  List<ulong> WorksWith = GetFromIndexOrTree(combo);
  foreach(ulong combo2 in WorksWith)
  {
    //Use
  }
}

private List<ulong> GetFromIndexOrTree(ulong combo)
{
  //magic index or tree
}

Большое спасибо за вашу помощь и за комментарии.

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

Answer 1

Пусть

S будет набором продуктов.

C ⊂ P (S) набор комбинаций.

F (p) = { c ∈ C | p ∉ c } набор всех комбинаций c ∈ C, которые не содержат произведение p ∈ S.

Тогда

G (X) = ∩ _{p ∈ X} F (p)

дает набор комбо, где ни один комбо не содержит продукта p в наборе продуктов X ⊂ S .

---

C #

List<ulong> combos = new List<ulong> { 1 | 2, 1 | 4 | 8 };

Dictionary<int, List<ulong>> dict = Enumerable
    .Range(0, 64)
    .ToDictionary(i => i, i => combos
        .Where(combo => ((1UL << i) & combo) == 0)
        .ToList());

ulong input = 1 | 2; // find all combos that don't have product 1 or 2

List<ulong> result = Enumerable
    .Range(0, 64)
    .Where(i => ((1UL << i) & input) != 0)
    .Select(i => dict[i])
    .Aggregate((a, b) => Enumerable
        .Intersect(a, b)
        .ToList());