散列一組對象C＃

我有一些訂單，每個訂單包含購買Item對象。散列一組對象C＃

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(...)功能，將能夠湊項目的子集。

注：{項目1，項目2} = {項目2，項目1}

非常感謝您！歡迎任何更好的想法的幫助！

來源

2012-10-19 Wild Goat

所以，如果你要問，「物品3 + 4 + 8購物的頻率是多少？」從你上面的例子中，答案是'1'（因爲即使3和4出現在兩者中，只有第二個列表_also_包含8）？ –

這似乎與文本搜索相似。假設您有文檔'Item1，Item2，Item3，Item4，Item5'和'Item2，Item8，Item4，Item3，Item11，Item5'，並且想要搜索包含單詞'Item3'和'Item4'的文檔。你可以使用[Lucene.Net]（http://lucenenet.apache.org/），這非常快。 –

因爲{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-19 15:34:31 corsiKa

請注意，您並不嚴格*需要*先排序項目，因爲有解決問題的其他方法，但這是一種方法，而且是一個好方法。 – Servy

點好，Servy。還有其他確定唯一性的方法。但是，如果它將被散列，它們必須以相同的順序添加到散列。如果以不同的順序向散列中添加內容是合理可行的，那麼它將不會提供很多可用的散列。 – corsiKa

你的哈希算法可能是每個項目的排他或散列。不管他們的順序如何，這將導致相同的一組項目相同的散列。 – Servy

，但我想給它我會這樣做。就像試圖解決這種挑戰一樣。

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和Item3同時購買Item2或Item3 ... Bleh。別管我。

來源

2012-10-19 15:47:16 LightStriker

散列一組對象C＃

回答

相關問題