7

クリーンアップされたテキスト:

m=5 の乱数を作成するにはどうすればいいですか? n=100 とします。しかし、最初の乱数は 10 < x1 < 30、2 番目の乱数 nr は 5 < x2 < 20、3 番目の乱数 nr は 10 < x3 < 25 などです。したがって、これら 5 つの乱数の合計は 100 になります。これらの制約された 5 つの数値を作成できますか?

.

[[

関連する問題 A1): 合計が 100 になる 5 つの乱数を作成する標準的な方法は、[0,100] の間の 4 つの数値をサンプリングし、境界 0 と 100 を追加してから、これらの 6 つの数値 [0,x1,x2, x3,x4,100]。私が求める 5 つの乱数はデルタです。あれは、

100 - x[4] = delta 5
x[4]- x[3] = delta 4
x[3]- x[2] = delta 3
x[2]- x[1] = delta 2
x[1] - 0   = delta 1

これらの 5 つのデルタを合計すると 100 になります。たとえば、0、1、2、7、90 などです。この問題を解決するコードを次に示します。

total_sum = 100
n = 5
v = numpy.random.multinomial(total_sum, numpy.ones(n)/n)

]]

.

私の問題では、間隔を広くすることはできません。上記の最大の広がりは 90-7 = 83 で、広すぎます。したがって、[10,30] など、より狭いスプレッドを指定する必要があります。これは、最大の乱数が 30 であることを意味し、83 などの大きなスプレッドは許可されません。

.

[[

関連する問題 A2): 10 < x_i < 30 という同一の境界を持つ 5 つの数値を作成し、合計すると 100 になる部分的な解決策は次のとおりです。したがって、次のように求める 5 つの乱数を取得します。

100 - x[4] = delta 5 + 10
x[4]- x[3] = delta 4 + 10
x[3]- x[2] = delta 3 + 10
x[2]- x[1] = delta 2 + 10
x[1] - 0   = delta 1 + 10

基本的に、私は A1) とまったく同じように行いますが、0 からではなく、10 から開始します。したがって、各数値には下限 10 がありますが、上限はありません。大きすぎたり、大きすぎたりする可能性があります。上限を 30 に制限するにはどうすればよいですか? ここで問題は、上限をどのように制限するかです

]]

.

要約すると、私が解決しようとしている問題の種類は次のようになります。合計 100 になる 5 つの乱数が必要で、各数値の境界を個別に指定する必要があります。最初の乱数は [10,30] とします。次に、2 番目の乱数は [5,10]、3 番目の乱数は [15,35] などです。これらはすべて合計すると 100 になります。

しかし、私が使用している実際のデータには、最大 100 の数値 x_i (m=50) があり、それらすべてを合計すると最大 400,000 になります。また、数値 x_i の範囲は通常 [3000,5000] です。これらの数値は実際には正確ではありません。問題のサイズについて何かを伝えようとしているだけです。目的は MCMC シミュレーションを実行することなので、これらの数値を迅速に生成する必要があります。人々は実際に機能する非常に洗練されたソリューションを提案していますが、時間がかかりすぎるため、使用できません。問題はまだ解決されていません。理想的には、O(m) ソリューションと O(1) メモリ ソリューションが必要です。

この問題は NP 困難であってはなりません。多項式時間解があるはずですよね？

4

5 に答える 5

4

まず、範囲を定義します。

ranges = [range(11,30), range(6,20), range(11,25)]

次に、すべての可能性を列挙します。

def constrainedRandoms(ranges):
    answer = []
    for vector in itertools.product(*ranges):
        if sum(ranges) == 100:
            answer.append(vector)
    return answer

同等のワンライナー:

answer = [v for v in itertools.product(*ranges) if sum(v)==100]

次に、それらからランダムな要素を選択します。

myChoice = random.choice(answer)

編集：

デカルト積（ で計算itertools.product）自体はあまりRAMを消費しません（これは、itertools.productO（1）スペースを使用するジェネレーターを返すためですが、指摘したように多くの時間を費やします）。answerリスト ( )を計算するだけです。悪いニュースは、 を使用するrandom.choiceにはリストが必要だということです。本当にリストを使用したくない場合は、減衰確率関数を考え出す必要があるかもしれません。使用できる非常に単純な確率関数を次に示します。

def constrainedRandoms(ranges):
    choices = (v for v in itertools.product(*ranges) if sum(v)==100) # note the parentheses. This is now a generator as well

    prob = 0.5
    decayFactor = 0.97 # set this parameter yourself, to better suit your needs
    try:
        answer = next(choices)
    except StopIteration:
        answer = None
    for choice in choices:
        answer = choice
        if random.uniform(0,1) >= prob:
            return answer
        prob *= decayFactor
    return answer

減衰確率により、制約に適合する次のベクトルを選択する確率を高めることができます。このように考えてみてください。たくさんの制約があります。これらの制約を満たすベクトルの数が比較的少ない可能性があります。これは、ベクトルを使用しないと決定するたびに、別のそのようなベクトルが存在する確率が減少することを意味します。したがって、時間の経過とともに、現在のベクトルを「ランダムに選択されたベクトル」として返すように、徐々にバイアスをかける必要があります。もちろん、ベクトルを返さずにループ構造全体を処理することも可能です。
この減衰確率のアイデアにより、すべての候補ベクトルを反復処理する必要がなくなることに注意してください。時間が経つにつれて、コードが考慮中の現在のベクトルを返す確率が増加するため、それが継続して他のベクトルを考慮する確率が減少します。したがって、このアイデアは、ランタイムに関する懸念を軽減するのにも役立ちます（ただし、追加するのは恥ずかしいですが、それほどではありません）

于 2013-08-26T16:20:51.873 に答える
2

これを試して：

import random
a = random.randint(10, 30)
b = random.randint(5, 20)
c = random.randint(10, 25)
d = random.randint(5, 15)
e = 100 - (a+b+c+d)

編集：

範囲の制約と目的の合計をn指定して、乱数のリストを生成する方法を次に示します。n

def generate(constraints, limit):
    ans = [random.choice(c) for c in constraints]
    return ans if sum(ans) == limit else generate(constraints, limit)

これはあなたがそれを使用する方法です：

generate([range(10,31),range(5,21),range(10,26),range(5,16),range(10,26)], 100)
=> [25, 20, 25, 12, 18]

ただし、注意してください: 制約が最終的に合計に達することを保証しない場合、無限ループとスタック オーバーフロー エラーが発生します。次に例を示します。

generate([range(1,11), range(10, 21)], 100)
=> RuntimeError: maximum recursion depth exceeded while calling a Python object
于 2013-08-26T16:17:33.360 に答える
0

2 つのスパン、4 つのスパン、8 つのスパンなどを使用して、それぞれの可能な合計を作成する方法の数を数えることができます (ここで、スパンはエンドポイントを含む整数の範囲です)。これらの数値を表にすると、サンプルに向かって逆方向に作業できます。たとえば、それぞれが 1 から 9 までの数字を含む 16 のスパンがあるとしますt = 100。1 から w の範囲で乱数 r を選択します。leftways(t-j)*rightways(j))J>j の合計が r を超え、J>j+1 の合計が r を超えない数 J を検索 (またはルックアップ) しますleftways(i)。rightways(j)最後の 8 スパンを使用して j を作成する方法の数です。最初の 8 スパンで i = tj を使用し、最後の 8 スパンで j を使用して再帰します。基本ケースは、必要な合計を作成する方法が 1 つしかない場合に発生します。

以下のコードは、幅の降順でスパンを並べ替え (つまり、最も広いスパンを最初にリストする)、いくつかのスワップを削除することで、より効率的に実行するように修正できます。スパンが幅の降順でない場合、結果ベクトルはスパンと同じ順序にならないことに注意してください。for j ...また、線形検索を二分検索に置き換えることは可能かもしれませんが、findTargetかなり多くのスペースを使用せずにそうする方法がわかりません。

タプルだけでなくオブジェクトを使用してツリー構造を格納することにより、コードをよりクリーンで明確にすることができます。

使用されるスペースO(s²·(lg m))は、最大合計が s になる m スパンがある場合です。使用される時間はO(s²·(lg m))、製品の合計の最初の集計と、おそらくO(m+(lg m)·(s/m))またはO(m+(lg m)·s)各サンプルです。(スペースと時間の要件を適切に分析していません。) 2 GHz マシンでは、16 の同一のスパン 1...10 がある場合、示されているコードは毎秒約 8000 サンプルを生成します。32 個の同一スパン 1 ～ 3 がある場合、毎秒約 5000 サンプル。32 個の同一スパン 1 ～ 30 がある場合、毎秒約 2000 サンプルです。コードの後に​​、さまざまなターゲットの合計とスパンのセットの出力例をいくつか示します。

from random import randrange
def randx(hi):   # Return a random integer from 1 to hi
    return 1+randrange(hi) if hi>0 else 0

# Compute and return c with each cell k set equal to 
# sum of products a[k-j] * b[j], taken over all relevant j
def sumprods(lt, rt):
    a, b = lt[0], rt[0]
    (la,ma,aa), (lb,mb,bb) = a, b
    if ma-la < mb-lb:           # Swap so |A| >= |B|
        la, ma, aa, lb, mb, bb = lb, mb, bb, la, ma, aa
    lc, mc = la+lb, ma+mb
    counts = [0]*(mc+1)
    for k in range(lc,mc+1):
        for j in range(max(lb,k-ma), min(mb,k-la)+1):
            counts[k] += aa[k-j] * bb[j]
    return (lc, mc, counts)

def maketree(v):
    lv = len(v)
    if lv<2:
        return (v[0], None, None)
    ltree = maketree(v[:lv/2])
    rtree = maketree(v[lv/2:])
    return (sumprods(ltree, rtree), ltree, rtree)


def findTarget(tototal, target, tree):
    global result
    lt, rt = tree[1], tree[2]
    # Put smaller-range tree second
    if lt[0][1]-lt[0][0] < rt[0][1]-rt[0][0]: lt, rt = rt, lt
    (la,ma,aa), (lb,mb,bb) = lt[0], rt[0]
    lc, mc = la+lb, ma+mb
    count = 0
    for j in range(max(lb,tototal-ma), min(mb,tototal-la)+1):
        i = tototal-j
        count += aa[i] * bb[j]
        if count >= target: break
    # Suppose that any way of getting i in left tree is ok
    if lt[1]: findTarget(i, randx(aa[i]), lt)
    else: result += [i]
    # Suppose that any way of getting j in right tree is ok
    if rt[1]: findTarget(j, randx(bb[j]), rt)
    else: result += [j]

spans, ttotal, tries = [(1,6), (5,11), (2,9), (3,7), (4,9), (4,12), (5,8),
                        (3,5), (2,9), (3,11), (3,9), (4,5), (5,9), (6,13),
                        (7,8), (4,11)],  100, 10

spans, ttotal, tries = [(10*i,10*i+9) for i in range(16)], 1300, 10000

spans, ttotal, tries = [(1,3) for i in range(32)],  64, 10000

spans, ttotal, tries = [(1,10) for i in range(16)], 100, 10

print 'spans=', spans
vals = [(p, q, [int(i>=p) for i in range(q+1)]) for (p,q) in spans]
tree = maketree(vals)
nways = tree[0][2][ttotal]
print 'nways({}) = {}'.format(ttotal, nways)
for i in range(1,tries):
    result = []
    findTarget(ttotal, randx(nways), tree)
    print '{:2}: {}  {}'.format(i, sum(result), result)

以下に示す出力サンプルでは、​​コロン付きの行にサンプル番号、サンプル合計、およびサンプル値配列が含まれています。他の行は、スパンのセットと、目的の合計を作成する方法の数を示しています。

spans= [(1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10), (1, 10)]
nways(100) = 202752772954792
 1: 100  [8, 9, 1, 2, 8, 1, 10, 6, 6, 3, 6, 10, 6, 10, 10, 4]
 2: 100  [2, 6, 10, 3, 1, 10, 9, 5, 10, 6, 2, 10, 9, 7, 4, 6]
 3: 100  [1, 6, 5, 1, 9, 10, 10, 7, 10, 2, 8, 9, 10, 9, 2, 1]
 4: 100  [10, 7, 6, 3, 7, 8, 6, 5, 7, 7, 5, 1, 9, 6, 9, 4]
 5: 100  [7, 1, 10, 5, 5, 4, 9, 5, 3, 9, 2, 8, 6, 8, 10, 8]
    spans= [(1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3), (1, 3)]
nways(64) = 159114492071763
 1: 64  [2, 2, 1, 3, 1, 2, 2, 2, 1, 2, 3, 3, 3, 2, 2, 1, 2, 3, 1, 3, 1, 3, 2, 1, 2, 3, 2, 2, 1, 2, 2, 2]
 2: 64  [1, 2, 1, 1, 1, 3, 3, 3, 2, 1, 1, 2, 3, 2, 2, 3, 3, 3, 1, 2, 1, 2, 2, 3, 2, 2, 1, 3, 1, 3, 2, 2]
 3: 64  [2, 1, 3, 2, 3, 3, 1, 3, 1, 3, 2, 2, 1, 2, 1, 3, 1, 3, 1, 2, 2, 2, 2, 1, 1, 3, 2, 2, 3, 2, 3, 1]
 4: 64  [2, 3, 3, 2, 3, 2, 1, 3, 2, 2, 1, 2, 1, 1, 3, 2, 2, 3, 3, 1, 1, 2, 2, 1, 1, 2, 3, 3, 2, 1, 1, 3]
 5: 64  [1, 1, 1, 3, 2, 2, 3, 2, 2, 1, 2, 2, 1, 2, 1, 1, 3, 3, 2, 3, 1, 2, 2, 3, 3, 3, 2, 2, 1, 3, 3, 1]
spans= [(0, 9), (10, 19), (20, 29), (30, 39), (40, 49), (50, 59), (60, 69), (70, 79), (80, 89), (90, 99), (100, 109), (110, 119), (120, 129), (130, 139), (140, 149), (150, 159)]
nways(1323) = 5444285920
 1: 1323  [8, 19, 25, 35, 49, 59, 69, 76, 85, 99, 108, 119, 129, 139, 148, 156]
 2: 1323  [8, 16, 29, 39, 48, 59, 69, 77, 88, 95, 109, 119, 129, 138, 147, 153]
 3: 1323  [9, 16, 28, 39, 49, 58, 69, 79, 87, 96, 106, 115, 128, 138, 149, 157]
 4: 1323  [8, 17, 29, 36, 45, 58, 69, 78, 89, 99, 106, 119, 128, 135, 149, 158]
 5: 1323  [9, 16, 27, 34, 48, 57, 69, 79, 88, 99, 109, 119, 128, 139, 144, 158]
    spans= [(1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (
1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (
1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (1, 30), (
1, 30), (1, 30), (1, 30)]
nways(640) = 19144856039395888221416547336829636235610525
 1: 640  [7, 24, 27, 9, 30, 23, 30, 27, 28, 29, 2, 30, 28, 19, 7, 27, 10, 2, 21, 23, 24, 2
7, 24, 16, 29, 8, 13, 23, 2, 19, 27, 25]
 2: 640  [30, 2, 17, 28, 30, 16, 5, 1, 26, 24, 22, 19, 26, 16, 16, 30, 27, 15, 19, 30, 15,
 30, 22, 5, 30, 9, 13, 25, 19, 15, 30, 28]
 3: 640  [2, 24, 1, 23, 20, 5, 30, 22, 24, 19, 22, 9, 28, 29, 5, 24, 14, 30, 24, 16, 26, 2
1, 26, 20, 20, 19, 24, 29, 24, 8, 23, 29]
 4: 640  [7, 20, 16, 24, 22, 14, 28, 28, 26, 8, 21, 9, 22, 24, 28, 19, 5, 13, 9, 24, 25, 2
2, 29, 18, 20, 21, 17, 26, 30, 9, 26, 30]
于 2013-08-27T21:27:22.490 に答える
0

一般化されたソリューションは次のとおりです。

import random
def constrained_rndms(constraints, total):
    result = []
    for x, y in constraints:
        result.append(random.randint(x,y))
    result.append(total - sum(result))
    return result

s = constrained_rndms([(10,20),(5,20),(10,25),(5,15)],100) # -- [19, 5, 16, 15, 45]
sum(s) # -- 100
于 2013-08-26T16:28:23.973 に答える