一千萬個為什麽

搜索

如何創建一個特殊的二叉樹

我希望索引一些密鑰為ulong的數據。 這個ulong(64位)代表了一系列產品, 其中ulong的每個位都是組合中的Product。

所以如果我們得到一個值為3的ulong鍵,那真的是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 Combos = new List();

其中有超過100萬個Combo Keys(密鑰代表所使用的產品)。

如何索引這個ulongs列表,以便我可以循環它並執行以下操作:

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

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

非常感謝您的幫助和評論。

說我是產品組合(紅色,藍色和白色)。我希望找到所有沒有任何或所有產品(紅色,藍色和白色)的組合。所以我會找到一個組合(黃色),(綠色,黃色),(綠色,黑色)......

Works - Don't works

最佳答案

    S   be the set of products.

    CP(S)   the set of combos.

    F(p) = { cC | pc }   the set of all combos c ∈ C that do not contain the product p ∈ S.

然後

    G(X) = ∩pX F(p)

gives the set of combos where no combo contains any product p in the set of products XS.


C#

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

Dictionary> 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 result = Enumerable
    .Range(0, 64)
    .Where(i => ((1UL << i) & input) != 0)
    .Select(i => dict[i])
    .Aggregate((a, b) => Enumerable
        .Intersect(a, b)
        .ToList());

轉載註明原文: 如何創建一個特殊的二叉樹