組み合わせで表現可能な数

Python 30分プログラム

30分プログラム、その292。Problem23の「2つの過剰数の和で表現可能な正の整数」を計算しようとしてみた。
もしこれができると、

2つの過剰数の和で書き表せない正の整数の総和 = sum(1,28123) - 2つの過剰数の和で表現可能な正の整数

という計算ができるようになるはず。

でも、遅くて使いものにならなかった。方針としては間違っていないはずだから、明日はもっと効率に気をつかって書いてみよう。

使い方

>>> combination([1,2,3])
[2, 3, 4, 4, 5, 6]

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# problem23.py -
#
# Copyright(C) 2008 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2008/04/19 09:26:46
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#
## 組み合せで表現可能かの計算
def combination(xs):
    ys = []
    for i in xrange(0,len(xs)):
        x    = xs[i]
        rest = xs[i:]
        ys.extend(map(lambda y:x+y,rest))
    return set(ys)

参考