2

我有许多订单，每个订单都包含购买的Item物品。

1 : {Item1, Item2, Item3, Item4, Item5}  
2 : {Item2, Item8, Item4, Item3, Item11, Item5} 
3 : { ... }

我的目标是确定这些物品中的每一个被一起购买的频率以及能够在 O(1) 中获得结果的频率。

我的想法是基于子集项目迭代订单 - 增加特定数组的元素。这将使我有可能在 O(1) 中提取所需的值。

例如。Item3 和 Item4 被买了 2 次。

int frequency = myArray[getHash(Item3+Item4)]

print frequency;

Output : 2

问题：

开发一个int getHash(...)函数，它将能够散列项目的子集。

注意：{Item1, Item2} = {Item2, Item1}

非常感谢！欢迎任何更好的想法的帮助！

4

2 回答 2

4

因为{A,B} = {B,A}在继续之前，您首先需要对列表进行排序。您按什么排序并不重要，但您确实需要确保没有任何值被认为是相等的，除非它们的排序可以互换。

接下来，任何简单的散列算法都应该起作用。一种常见的技术是使用两个素数，我将它们称为c和p。

int hash = c;
foreach(Item i in items) hash = hash * p + i.GetHashCode()
return hash;

p有时选择为 31，因为它不仅是素数，而且编译器将其解析为位移和减法，这比乘法快得多。x * 31与(x << 5) - 1（假设我使用了正确的班次......我不时搞砸了，哈哈。）

于 2012-10-19T15:34:31.287 回答
0

对不起，我没有使用哈希，但我试图以我愿意的方式尝试一下。就像尝试解决那种挑战一样。

Dictionary<Item, Dictionary<Item, Count>> combine = new Dictionary<Item, Dictionary<Item, Count>>();

foreach (Item item in Sell)
{
    Dictionary<Item, int> key;
    if (!combine.TryGetValue(item, out key))
    {
        key = new Dictionary<Item, Count>();
        combine.Add(item, key);
    }

    foreach (Item otherItem in Sell)
    {
        if (item == otherItem)
            continue;

        Count count;
        if (key.TryGetValue(otherItem, out count))
            count++;
        else
            key.Add(otherItem, new Count());
    }
}

这可能非常愚蠢，因为对于每件商品，您最终都会得到一本同时在柜台购买的所有其他商品的字典。如果您想知道 Item1 是否与 Item2 AND Item3 vs Item2 OR Item3 同时购买... Bleh。别管我。

于 2012-10-19T15:47:16.077 回答