2

我有两个不同类别的项目列表，比如说 A 和 B，有 m A 和 n B。我想将这两个列表混合成一个列表，以便结果保持 A 的顺序和 B 的顺序，但以一种看起来不人为的方式组合它们。

如果 m 和 n 相似，一个愚蠢的版本将是替代 ABAB，但这看起来不自然。像 AABABABBAA 之类的东西看起来不那么假。在大多数情况下，A 比 B 多，但不能保证。通常有 125 A 和 50 B，而且不会更多，但可以过滤到低至 1。

我已经建立了一个基于 m/n 比率的模型，但当然它是高度规则的。我尝试在其中添加一些随机元素，但看起来仍然不太正确。

正确的外观显然是主观的，显然如果有坚实的统计基础，代码会更容易编写。欢迎任何想法。如果有一个数学或统计分支可以做这样的事情，即使告诉我谷歌中正确的搜索词也会有所帮助。

用 Objective-C 写这个，但我不需要代码，只需要算法或想法。

更新：我调查了各种建议，但有些过于复杂，尤其是像 Sobol 序列这样的东西）。我目前正在做的是使用随机算法（将总 A 和 B 加在一起，从 0 到 total-1 选择随机整数，如果小于总 A 选择 A）但我添加了一个检查以确保不超过2 个 B 连续出现（因为 B 计数几乎总是少于 As 的一半）。还不完美，但它看起来确实不那么随机。你确实会在最后得到过多的 B，但无论如何从商业角度来看，这些都不太理想。Sobol et all 将确保更好的混合，但为此付出了太多努力。

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

一种方法是从指定确定性自动机接受的具有正确字母计数的单词中随机均匀采样。该算法是自动机状态和剩余符号数量的动态程序。以下是一些带有 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 回答