python：算法 - 從平均值收集項目

不知道這是否是正確的地方，但我有一個與算法有關的問題，我不能想到一個有效的算法。所以想到分享我的問題聲明.. :) 爲了緩解我想解釋的，讓我創建一個假設的例子。python：算法 - 從平均值收集項目

想，我有一個包含whcih包含兩件事情的對象的列表..

lets say product id and price

現在，這是一個很長很長list..sort像清單.. 出這個我有定義了三個價格段。低價，中價和高價然後是k1，k2，k3，其中k1，k2和k3是比率。因此，現在的工作是，我必須從這個龐大的庫存中收集產品，以便有低價位的n1個產品，中檔的n2個產品和高價位的n3個產品......其中n1：n2 ：n3 == k1：k2：k3

現在，我該如何有效實現以下功能。我指定的價格低一點的是100美元，我必須收集20種產品在此範圍內.. 中等價格區間大概是500塊錢等

於是我開始與100美元..再看看對於90至100之間以及100至110之間的項目假設我在間隔1低（90,100）和間隔1高（2,100,110）中找到2個商品然後，我轉到下一個低間隔和下一個高間隔。我一直這樣做，直到我得到這個間隔的產品數量。

我該怎麼做？也有可能的情況下，當一個特定的價格範圍內的產品數量少於我所需要的...（也許中等價格範圍是105美元...）..那麼我應該怎麼做，在這種情況下.. 請原諒我，如果這不是正確的平臺..從問題你可以看出，這更像是一個辯論問題，而不是「我得到這個錯誤」類型的問題。謝謝

來源

2011-11-14 Fraz

如果您對項目N進行排序，然後根據比率將N分成n1：n2：n3，會更容易嗎？ –

@AlvinK。嗯..這可能是一個解決方案，雖然我不能真正使用我計算出的一些統計數據..但絕對是一個非常好的例子，假設一小部分可以導致簡單的編程.. :) – Fraz

您可能正在尋找selection algorithm。
首先找到n1'th的最小元素，讓它是e1，並且下限列表是所有的元素，例如element <= e1。
對其他範圍做同樣的事情。對於下界列表

僞代碼：

getLowerRange(list,n): 
    e <- select(list,n) 
    result <- [] 
    for each element in list: 
    if element <= e: 
     result.append(element) 
    return result

注意，如果有許多「相同」項目此溶液失敗[結果將是一個更大的列表]，但找到的那些項目，並且除去它從結果列表中並不難。

請注意，選擇算法是O(n)，所以此算法將消耗與列表大小相關的線性時間。

來源

2011-11-14 19:36:34 amit

這似乎是你應該嘗試一個數據庫解決方案，而不是使用列表。檢查出sqlite。它默認在Python中

來源

2011-11-14 19:19:12

方法1

如果什麼樣的產品屬於三個價格段永遠不會改變，分配你爲什麼不乾脆建造3所列出，一個產品在各個價格段（假設這些集合不相交）。然後你可以從這些列表中隨機選擇（either with or without replacement - 如你所願）。每個班級的項目數量由比率給出。

方法2

如果產品價格段分配意在預先指定的，例如，通過將相應的價格值的函數調用每個段，你可能需要有排序的產品通過價格並使用二進制搜索來選擇m-nearest-neighbors（例如）。可以根據比率指定參數m。如果您指定最大距離，您可能會拒絕超出期望價格範圍的產品。

方法3

如果產品價格段分配需要進行自主確定，你就能把自己的clustering算法的選擇，例如，k-means，分配你的產品，比方說，k = 3價格段。對於實際的產品選擇，您可以按照上述類似的方式進行。

來源

2011-11-14 20:43:04 moooeeeep

python：算法 - 從平均值收集項目

回答

相關問題