按值将文件分成相等的部分

Question

使用bash或python（2.4.x）

我有一个文件-大约100行，文件的结构是这样的。在

aaaaa,  100
aaaab,  75
aaaac,  150
aaaad,  135
aaaae,  144
aaaaf,  12
aaaag,  5
aaaah,  34
aaaai,  11
aaaaj,  43
aaaak,  88
aaaal,  3
baaaa,  25
baaab,  33
baaac,  87
baaad,  111
baaae,  45
baaaf,  99
baaag,  71
baaah,  68
baaai,  168
baaaj,  21
baaak,  11
baaal,  47
caaaa,  59
caaab,  85
caaac,  77
caaad,  33
caaae,  44
caaaf,  16
caaag,  111
caaah,  141
caaai,  87
caaaj,  59
caaak,  89
caaal,  3

我要做的是把它分成12列，每列有大致相同数量的传感器，每列的总和接近相同。在

换句话说，如果我把上面的清单像这样分开。在

^{pr2}$

它有12列相等的项目，非常接近偶数值。在

我可以手动操作，但我们最终需要做几次。我甚至不知道从哪里开始，除了把它变成一个数组，计算数组中的项目并随机拆分。但仍停留在价值平衡上。在

有什么建议吗？在

Answer 1

我写了两个非常简单的实现。第一个方法使用deque从右和从左弹出（一旦列表被排序），将低值与高值放在一起。第二个是@Sean McSomething建议的。在

下面是代码（quick'n'dirty--不幸的是，很少有注释）：

import math
import itertools
import collections


def sum_column(data):
    return sum(zip(*data)[1], 0.0)


def split_groups(sensors):
    sensors.sort(key=lambda item: item[1], reverse=True)
    per_group = len(sensors) // 12
    average = sum_column(sensors) / len(sensors)
    data = collections.deque(sensors)
    groups = [[] for i in xrange(12)]
    cycle = itertools.cycle(groups)
    try:
        while True:
            current = cycle.next()
            if len(current) == per_group - 1:
                if sum_column(current) < average:
                    current.append(data.popleft())
                else:
                    current.append(data.pop())
                continue
            current.append(data.popleft())
            current.append(data.pop())
    except IndexError:
        return groups


def split_groups2(sensors):
    sensors.sort(key=lambda item: item[1], reverse=True)
    groups = [[] for i in xrange(12)]
    cycle = itertools.cycle(groups)
    per_group = int(math.ceil(len(sensors) / 3.))
    partitions = [sensors[i:i + per_group] for i in xrange(0, len(sensors)
                                                           per_group)]
    medium, low = map(reversed, partitions[1:])
    for sensor, value in itertools.chain(partitions[0], medium, low):
        cycle.next().append((sensor, value))
    return groups


def format_groups(result):
    ret = []
    for group in result:
        tmp = []
        tmp.append('\n'.join('{0}   {1}'.format(k, v) for k, v in group))
        tmp.append(' ' * 8 + str(int(sum_column(group))))
        ret.append('\n'.join(tmp))
    return '\n\n'.join(ret)


if __name__ == '__main__':
    import sys

    implementation = split_groups
    if '--second' in sys.argv:
        sys.argv.remove('--second')
        implementation = split_groups2

    with open(sys.argv[1]) as fobj:
        sensors = []
        for line in fobj:
            sensor, value = line.strip().split(',  ')
            sensors.append((sensor, int(value)))
        sys.stdout.write(format_groups(split_groups(sensors)))
        sys.stdout.write('\n')

要点也是：
https://gist.github.com/2703965

我把最简单的部分（格式化）留给你了。现在，它只需垂直打印（而不是按您的要求打印）。应该不会太难。在

这是它所能达到的最佳效果（使用这两种实现）：

^{pr2}$

这与示例相去甚远，但这只是一个开始。您可以使用文件名和可选的--second开关从命令行启动它（以使用第二个实现）。我可以使用命令行解析器，但我习惯于argparse，这在python2.4中没有。所以我就去做那个笨拙的黑客。在

示例运行：

$ python2 groupit.py filename.txt
baaai   168
caaal   3
aaaaj   43
        214

aaaac   150
aaaal   3
caaae   44
        197

aaaae   144
aaaag   5
baaae   45
        194

caaah   141
baaak   11
baaal   47
        199

aaaad   135
aaaai   11
caaaj   59
        205

baaad   111
aaaaf   12
caaaa   59
        182

caaag   111
caaaf   16
baaah   68
        195

aaaaa   100
baaaj   21
baaag   71
        192

baaaf   99
baaaa   25
aaaab   75
        199

caaak   89
caaad   33
caaac   77
        199

aaaak   88
baaab   33
caaab   85
        206

baaac   87
aaaah   34
caaai   87
        208
$ python2 groupit.py --second filename.txt
baaai   168
caaal   3
aaaaj   43
        214

aaaac   150
aaaal   3
caaae   44
        197

aaaae   144
aaaag   5
baaae   45
        194

caaah   141
baaak   11
baaal   47
        199

aaaad   135
aaaai   11
caaaj   59
        205

baaad   111
aaaaf   12
caaaa   59
        182

caaag   111
caaaf   16
baaah   68
        195

aaaaa   100
baaaj   21
baaag   71
        192

baaaf   99
baaaa   25
aaaab   75
        199

caaak   89
caaad   33
caaac   77
        199

aaaak   88
baaab   33
caaab   85
        206

baaac   87
aaaah   34
caaai   87
        208

在问题的例子中，两种算法给出了完全相同的答案。如果你能提供更多的测试用例，我会努力改进它们。我在Python2.7上测试了脚本，因为我没有安装2.4。
抱歉回答太长了。在

Answer 2

如果你想要一个最优的解决方案，这对于大量的输入是没有意思的。你看到的是与CS-Knapsack，Bin Packing等中一些非常著名的难题一致的东西。一些更简单、不太完美的解决方案可能就足够接近了。在

这并不精确，但是，考虑到您的示例数据集，我设法从一个非常简单的方法得到214、197、194、199、205、182、195、192、199、199、206、208。它可能对真实数据起作用，也可能不起作用。在

方法是：

1. 按大小排序列表
2. 将列表分成3部分-高、中、低
3. 把高的每个成员放在一组。在
4. 颠倒中低档名单。在
5. 将它们（按相反的顺序）放入现有的集合中

随着您接近最佳分区，解决方案可能会变得更加复杂。在

Answer 3

有意思的问题，我认为你要花很长时间才能找到最好的解决方案。您可以计算每个拆分的项目数以及它们应该具有的平均值。对整数上的项目进行排序，在值仍低于平均值的情况下取最大的数字，然后重复此过程，直到您只需要再添加一个项目，现在选择最小的项目并尽可能接近平均值（高于或低于并不重要）。在

如果在除最近一步之外的任何一步都陷入困境（例如value>；average），请返回并选择下一个最大的。在