代码之家 › 专栏 › 技术社区 › Chankey Pathak

根据值统一拆分词典[duplicate]

set math dictionary python

Chankey Pathak · 技术社区 · 6 年前

大约 )等于 Knapsack problem (我想是的)

因此,例如[1,2,1,4,10,3,8]=>[[8,2],[10],[1,3,1,4]]

长度相等的块是首选的,但这不是限制。

Python是首选语言,但其他语言也很受欢迎

编辑: 块数已定义

0 回复 | 直到 13 年前

Alin P. 13 年前

贪婪的:
1按降序排列可用项目。
2创建N个空组
三。开始一次将一个项目添加到组中总和最小的组中。

我认为在大多数现实生活中这应该足够了。

ts. 13 年前

基于@Alin Purcaru answer和@amit的评论,我编写了代码(python3.1)。就我所测试的,它具有线性性能(包括项目数和块数,所以最后是O(N*M))。我避免每次都对列表进行排序,保持dict中每个块的值的当前总和(对于更多的块可能不太实用)

import time, random

def split_chunks(l, n):
    """ 
       Splits list l into n chunks with approximately equals sum of values
       see  http://stackoverflow.com/questions/6855394/splitting-list-in-chunks-of-balanced-weight
    """
    result = [[] for i in range(n)]
    sums   = {i:0 for i in range(n)}
    c = 0
    for e in l:
        for i in sums:
            if c == sums[i]:
                result[i].append(e)
                break
        sums[i] += e
        c = min(sums.values())    
    return result


if __name__ == '__main__':

    MIN_VALUE = 0
    MAX_VALUE = 20000000
    ITEMS     = 50000
    CHUNKS    = 256

    l =[random.randint(MIN_VALUE, MAX_VALUE ) for i in range(ITEMS)]

    t = time.time()

    r = split_chunks(l, CHUNKS)

    print(ITEMS, CHUNKS, time.time() - t)

function split_chunks($l, $n){

    $result = array_fill(0, $n, array());
    $sums   = array_fill(0, $n, 0);
    $c = 0;
    foreach ($l as $e){
        foreach ($sums as $i=>$sum){
            if ($c == $sum){
                $result[$i][] = $e;
                break;  
            } // if
        } // foreach
        $sums[$i] += $e;        
        $c = min($sums);
    } // foreach
    return $result;
}

define('MIN_VALUE',0);
define('MAX_VALUE',20000000);
define('ITEMS',50000);
define('CHUNKS',128);

$l = array();
for ($i=0; $i<ITEMS; $i++){
    $l[] = rand(MIN_VALUE, MAX_VALUE);  
}

$t = microtime(true);

$r = split_chunks($l, CHUNKS);

$t = microtime(true) - $t;

print(ITEMS. ' ' .  CHUNKS .' ' . $t . ' ');

amit 13 年前

你可能需要使用人工智能工具来解决这个问题。定义你的第一个问题

States={(c1,c2,...,ck) | c1,...,ck are subgroups of your problem , and union(c1,..,ck)=S } 
successors((c1,...,ck)) = {switch one element from one sub list to another } 
utility(c1,...,ck) = max{sum(c1),sum(c2)...} - min{sum(c1),sum(c2),...}

现在,你可以使用 steepest ascent hill climbing 随机重启。

anytime ,这意味着你可以开始搜索,当时间到了-停止它,你将得到目前为止最好的结果。随着运行时间的增加,结果会更好。

foxtrotmikew 7 年前

def split_chunks2(l, n):
    result = [[] for i in range(n)]
    sums   = [0]*n
    i = 0
    for e in l:
        result[i].append(e)
        sums[i] += e
        i = sums.index(min(sums)) 
    return result