0

背景：私はPython 3で作業していますが、他のプログラミング言語で回答が得られた場合でも、それを使用できます。関数や効率的なアルゴリズムやプログラミングのヒントに関する提案があれば役立ちます。

問題：4つの整数のセットとそれらの平均値に関する問題があります。

与えられた情報：1。セット内の整数の数（4）2.整数の平均

必要な情報：1。与えられた平均をもたらす可能性のある値のリスト

注：セット内の整数の数は少ないので、リストを生成する効率的な方法はそれほど難しいことではありませんが、これまでのところ行き詰まっています。私は数値の合計（平均* 4）から始めていますが、反復する正しい方法をまだ見つけていません。

編集：すべての整数は非負です。私の目的では、それらも8桁以下です。

4

2 に答える 2

1

平均ではなく、合計 N を使用します。

def all_possibilities(N, k=4):
    if k == 1:
        yield (N,)
        return
    for i in xrange(N+1):
        for p in all_possibilities(N-i, k-1):
            yield (i,) + p


print list(all_possibilities(5))

プロデュース:

[(0, 0, 0, 5), (0, 0, 1, 4), (0, 0, 2, 3), (0, 0, 3, 2), (0, 0, 4, 1),
 (0, 0, 5, 0), (0, 1, 0, 4), (0, 1, 1, 3), (0, 1, 2, 2), (0, 1, 3, 1),
 (0, 1, 4, 0), (0, 2, 0, 3), (0, 2, 1, 2), (0, 2, 2, 1), (0, 2, 3, 0),
 (0, 3, 0, 2), (0, 3, 1, 1), (0, 3, 2, 0), (0, 4, 0, 1), (0, 4, 1, 0),
 (0, 5, 0, 0), (1, 0, 0, 4), (1, 0, 1, 3), (1, 0, 2, 2), (1, 0, 3, 1),
 (1, 0, 4, 0), (1, 1, 0, 3), (1, 1, 1, 2), (1, 1, 2, 1), (1, 1, 3, 0),
 (1, 2, 0, 2), (1, 2, 1, 1), (1, 2, 2, 0), (1, 3, 0, 1), (1, 3, 1, 0),
 (1, 4, 0, 0), (2, 0, 0, 3), (2, 0, 1, 2), (2, 0, 2, 1), (2, 0, 3, 0),
 (2, 1, 0, 2), (2, 1, 1, 1), (2, 1, 2, 0), (2, 2, 0, 1), (2, 2, 1, 0),
 (2, 3, 0, 0), (3, 0, 0, 2), (3, 0, 1, 1), (3, 0, 2, 0), (3, 1, 0, 1),
 (3, 1, 1, 0), (3, 2, 0, 0), (4, 0, 0, 1), (4, 0, 1, 0), (4, 1, 0, 0),
 (5, 0, 0, 0)]

一般に、choose(N+k-1, k-1) の解があります。

活用する短いソリューションitertools.combinationsは次のとおりです。

import itertools

def all_possibilities(N, k=4):
    for c in itertools.combinations(range(N + k - 1), k - 1):
        yield tuple(x - y - 1 for x, y in zip(c + (N + k - 1,), (-1,) + c))
于 2013-02-03T20:01:25.917 に答える
0

(一意の) 負でない整数のセットを実際に探していると仮定すると、整数に次のa, b, c, dように名前を付けることができa > b > c > d、合計すると になることに注意してくださいaverage * 4。次に、次のようなジェネレーター関数との組み合わせを見つけることができます。

def get_4set_with_average(average):
    target_float = average * 4.0
    target = int(target_float)
    if target_float != target or target < 6:
        raise ValueError('No combinations possible')
    for a in xrange(target):
        for b in xrange(a):
            for c in xrange(b):
                for d in xrange(c):
                    if a + b + c + d == target:
                        yield([a, b, c, d])

print list(get_4set_with_average(4))

これは、4 つの整数間の関係を考慮に入れることで、さまざまな方法でより効率的にすることができます...

given that...
    a > b > c > d >= 0 and a + b + c + d = target 
it must be that...
    3 <= a <= target - 3,
    2 <= b <= target - a - 1,
    (target - a - b) / 2 < c <= target - a - b

これにより、次のことがわかります。

def get_4set_with_average(average):
    target_float = average * 4.0
    target = int(target_float)
    if target_float != target or target < 6:
        raise ValueError('No combinations possible')
    for a in xrange(3, target - 2):
        for b in xrange(1, min(a, target - a)):
            for c in xrange(int((target - a - b) / 2) + 1, 
                            min(b, target - a - b + 1)): 
                yield([a, b, c, target - a - b - c])

(私はこれを少しテストしましたが、完全ではありません。確認する必要があります。)

より効率的なアルゴリズムがあることは間違いありませんが、可能な組み合わせの数が非常に多いため、これを大きな値に対して実行することは困難です。(私のマシンでは平均 = 20 でも長い時間がかかります。)

于 2013-02-03T21:10:04.020 に答える