2

異なるカテゴリに 2 つのアイテムのリストがあります。A と B としましょう。A は m 個、B は n 個あります。2 つのリストを 1 つのリストに混ぜて、結果が A の順序と B の順序を維持するようにしますが、人工的に見えない方法でそれらを結合します。

m と n が似ている場合、愚かなバージョンは ABAB を交互にすることになりますが、それは不自然に見えます。AABABABBAA などのようなものは偽物に見えません。ほとんどの場合、B よりも A の方が多くなりますが、保証されていません。通常、125 A と 50 B があり、それ以上になることはありませんが、1 までフィルタリングできます。

m/n の比率に基づいたものを作成しましたが、もちろん非常に規則的です。少しランダムな要素を追加しようとしましたが、まだうまくいきません。

正しい見方は明らかに主観的なものです。確かな統計的基盤があれば、明らかにコードを書きやすくなります。どんなアイデアでも大歓迎です。このようなことを行う数学や統計の分野があれば、Google で正しい検索用語を教えてくれても役に立ちます。

これをObjective-Cで書いていますが、コードは必要ありません。アルゴリズムまたはアイデアだけです。

更新：提案されたさまざまなことを調査しましたが、複雑すぎるもの、特にソボルシーケンスなど）がありました。私が現在行っているのは、ランダムアルゴリズムを使用することです (合計 A と B を一緒に追加し、0 から合計 -1 までのランダムな int を選択し、合計 A が A を選択しない場合) 2 つの B が連続して表示されます (B のカウントは事実上常に As の半分未満であるため)。まだ完全ではありませんが、少しランダムではないように見えます。最後に余分な B が残ってしまいますが、いずれにせよ、これらはビジネス上の観点からはあまり望ましくありません。ソボルら全員がより良い混合を確実にするでしょうが、これにはあまりにも多くの努力が必要です.

4

3 に答える 3

3

m A とn Bが与えられた場合:

while (m + n > 0) {
  float r = a random number in the range 0..1;
  if (r < m / (m + n)) {  // use floating point arithmetic
    choose the next A;
    --m;
  } else {
    choose the next B;
    --n;
  }
}
于 2013-06-06T22:33:26.033 に答える
0

Metropolis-Hastings に基づく別のアプローチを次に示します。

from math import log2
from random import randrange


def simscore(lst, j):
    score = 0
    if j > 0 and lst[j] == lst[j - 1]:
        score += 1
    if j < len(lst) - 1 and lst[j] == lst[j + 1]:
        score += 1
    return score


def mix(lst):
    n = len(lst)
    for i in range(len(lst) * (100 + round(log2(n + 1)))):
        j = randrange(n)
        k = randrange(n)
        oldscore = simscore(lst, j) + simscore(lst, k)
        (lst[j], lst[k]) = (lst[k], lst[j])
        newscore = simscore(lst, j) + simscore(lst, k)
        if not (newscore <= oldscore or randrange(4 ** (newscore - oldscore)) == 0):
            (lst[j], lst[k]) = (lst[k], lst[j])


lst = list(125 * 'a' + 50 * 'b')
for i in range(10):
    mix(lst)
    print(''.join(lst))

以下にいくつかのサンプルを示します。

ababababaaababaabaabbabaabaaaaabaaabaababaaaabababaabaababaaabaaabaaabaabaababaaaababaaabaaaaaaabaaabaaaaaaaaabaabaabaaaababaaaaaababababaaabaabaabaaababaabaabaaabaaaaaaaabaaa
aaaaaaabababaaaaabaaabaaabaabaaaaaababaaaabaaaabaaaaaabaaabababaaabaaaaaaabbaababaabaabababaabababaababaaabaababaaaaabaabaaaaaaaabaabaaaababaabaaaaaababaaabababbababababaabaaa
ababababaabaaabbababaaababbaaaabaabaaaabaabaaaababaabababaaababaaaabaaabaaaaaaabaaaabaaababaaaaaaaababaaaabaaababaaaaabaaaabaaaababaabaababaaabaaaaababaababaaaaabaabaabaabaaaa
aaaaaababababaaaaaabaaaabaabaaabababaaabaaaabaaababaabaaaaaaaababaababaaaaabaaabaababaaaaabaaaabababaaaababaabababababbaaabaaaaabbaaaaaabababbaaabaabaaabaaaaaabbaaaaaabaaababa
ababaababaaababababaabaaaaaaabaababaabaaaaaaaaabaabaabaababaabaababababaabaabababababaaabaabababaaaaaaabaabaaaabababaaaaaaaabaaaaaaaabaaaaaaaababaaaaabbaaababaaabaaaaaaababaab
baababaabaabaaabababaaaabaabaababaaaababaabaaaaaabababaabaaaaaaaababaaaaabababaaaabaabababababababaaaaaababaaaabaaaaaaabaaabaaabaaaabaabaaaaaababaaaaaaababaababaabababaaaaaaab
aabaabaaaabababaabaababaaaaabaaaaabaabaaaaababaaababaaababaaaaababaaabaaabaaaabaabababababaaaabaabbabaabaabaabaababaabaabaaaabaaababaaabaabaaaaaabababaaaaaaaabaaaaaaabaaabaaab
babaaaaaababbaaaabababaaaaabaaabababbaaaabaabaaababaabababaabaaabaababaaababaaabaaabaabaababaaaaaaaaaabaaaaaababaabaaabaabaababaaabababbaaaaaabaaaaaaabaaaaaaaabaaaaababaabaaba
aabaaabaaaaaabaababaabaaaaaaaaaaaabababaaababaababaababaaabaabaaabaabaabaaaaabaabaaaabaaabaabaabaababaabaabaabaaaaaaabaabbabaaaabaabaabaaaaaabaaababaaaabaaabaaabbababaabaababa
baaaabababaaaabaaababaabaaaababaaaaabaaaaaaabaaabababbaabababaaaabaabaaaaaabaaaabababababbaaabaaaaabaaaaaabaabaaabaaaaaaaaabaababbaabababaaaabaabaabaababaabababaaaaaaabaaabaaa
于 2013-06-07T16:47:11.543 に答える
0

1 つのアプローチは、指定された決定論的オートマトンによって受け入れられる正しい文字数の単語からランダムに一様にサンプリングすることです。このアルゴリズムは、オートマトンの状態と残りのシンボル数に関する動的プログラムです。20 個の a と 20 個の b を使用したサンプル出力を次に示します。

abbaabbbaabbbabaaabbaaababbaaabbbabbbaaa
bbaaababababbaaabbababababbbabaaababaabb
bbababbbaaabaaabbbabaabaaabbbaababbababa
ababbbabbababbbaabababbaababaabbaaababaa
bbaaababbababbabaabbababaabababaabababba
bbaabbababbbaabbababaaabaababbbaababaaab
babaabaabbababbababbababbaababaaababbaba
aaabababaababbabbababbbaabbababaabbaaabb
babababbabaaababababababaababbbaabbaabba
bbabaabababababbabaababaababbbaabbabaaba

これらを生成した Python は次のとおりです。

from collections import namedtuple
from itertools import product, repeat
from random import random


"""
deterministic finite automata
delta is a dict from state-symbol pairs to states
q0 is the initial state
F is the set of accepting states
"""
DFA = namedtuple('DFA', ('delta', 'q0', 'F'))


"""accepts strings with no runs of length 4"""
noruns4 = DFA(
    delta={
        ('0', 'a'): '1a',
        ('0', 'b'): '1b',
        ('1a', 'a'): '2a',
        ('1a', 'b'): '1b',
        ('1b', 'a'): '1a',
        ('1b', 'b'): '2b',
        ('2a', 'a'): '3a',
        ('2a', 'b'): '1b',
        ('2b', 'a'): '1a',
        ('2b', 'b'): '3b',
        ('3a', 'a'): '4',
        ('3a', 'b'): '1b',
        ('3b', 'a'): '1a',
        ('3b', 'b'): '4',
        ('4', 'a'): '4',
        ('4', 'b'): '4'},
    q0='0',
    F={'0', '1a', '1b', '2a', '2b', '3a', '3b'})


def accepts(dfa, s):
    """returns whether dfa accepts s"""
    q = dfa.q0
    for c in s:
        q = dfa.delta[(q, c)]
    return q in dfa.F


def testaccepts():
    for n in range(10):
        for cs in product(*repeat('ab', n)):
            s = ''.join(cs)
            if not accepts(noruns4, s) != ('aaaa' in s or 'bbbb' in s):
                print(s)
                assert False


testaccepts()


def acceptedstrcnts(dfa, syms, cnts, memo=None, q=None):
    """
    counts the number of strings accepted by dfa,
    subject to the constraint of having the specified number of symbols
    """
    if memo is None:
        memo = {}
    if q is None:
        q = dfa.q0
    key = (q,) + tuple(cnts)
    if key not in memo:
        if sum(cnts) > 0:
            total = 0
            for (i, cnt) in enumerate(cnts):
                if cnt > 0:
                    newcnts = list(cnts)
                    newcnts[i] -= 1
                    newq = dfa.delta[(q, syms[i])]
                    total += acceptedstrcnts(dfa, syms, newcnts, memo, newq)
        else:
            total = 1.0 if q in dfa.F else 0.0
        memo[key] = total
    return memo[key]


print(acceptedstrcnts(noruns4, 'ab', (125, 50)))
memo = {}
acceptedstrcnts(noruns4, 'ab', (4, 4), memo)
# 62 strings with 4 a's, 4 b's, and no runs
print(memo)


def memoget(memo, q, cnts):
    return memo[(q,) + tuple(cnts)]


def samplestrcnts(dfa, syms, cnts, memo):
    """
    uses the memoization dict to sample the counted words
    modulo roundoff error, the sampling is uniform
    """
    cnts = list(cnts)
    cs = []
    q = dfa.q0
    while sum(cnts) > 0:
        denom = memoget(memo, q, cnts)
        outcome = random()
        j = None
        for (i, cnt) in enumerate(cnts):
            if cnt > 0:
                j = i  # default in case roundoff bites us
                newcnts = list(cnts)
                newcnts[i] -= 1
                newq = dfa.delta[(q, syms[i])]
                numer = memoget(memo, newq, newcnts)
                ratio = numer / denom
                if outcome < ratio:
                    break
                outcome -= ratio
        cnts[j] -= 1
        cs.append(syms[j])
        q = dfa.delta[(q, syms[j])]
    return ''.join(cs)


acceptedstrcnts(noruns4, 'ab', (20, 20), memo)
for k in range(10):
    print(samplestrcnts(noruns4, 'ab', (20, 20), memo))
于 2013-06-07T14:31:48.607 に答える