在盒子中生成球

要生成可能重复元素(多集)的k-组合,以下可能有用: A Gray Code for Combinations of a Multiset (1995) .

对于递归解决方案,请尝试以下操作:

计数每个字符出现的次数。假设它们是x1 x2…xm,对应m个不同的字符。

然后你需要找到所有可能的有序对(y1 y2…这样)

0和l=;

和Yi=K。

这里,yi是我出现字符的次数。

其想法是,固定char 1出现的次数(y1)。然后递归地从其余部分生成k-y1的所有组合。

psuedocode:

List Generate (int [] x /* array index starting at 1*/, 
               int k /* size of set */) {

    list = List.Empty;

    if (Sum(x) < k) return list;

    for (int i = 0; i <= x[1], i++) {

        // Remove first element and generate subsets of size k-i.

        remaining = x.Remove(1);

        list_i = Generate(remaining, k-i);

        if (list_i.NotEmpty()) {

            list = list + list_i;    

        } else {

            return list;
        }

    }

    return list;
}

编辑前:

如果我理解正确的话,你需要看看字符串A,看看恰好出现一次的符号。假设有k个这样的符号。然后,您需要生成所有可能的b排列,其中包含k元素,并在相应的位置映射到这些符号。其余的可以忽略/根据需要填写。

我记得在这里张贴了C代码: How to find permutation of k in a given length?

我假设XXYY只给出1个唯一的字符串,并且恰好出现一次的字符串是“区别”点。

以防万一 a=xyy, b=add

区别点是X

所以选择长度为1的“添加”的排列。那些给你 a 和 d .

因此 add 和 dad (or dda) 是你需要的。

为了 a=xyyz b=good

区别点是X和Z

所以你产生长度为2的b排列

go
og
oo
od
do
gd
dg

给你7个独特的排列。

有帮助吗?我的理解正确吗?

好吧,很抱歉,我一直无法清楚地解释这个问题,但这里有一个解决方案。

我们需要两个功能 combinations 和 runvector(v) . combinations(s,k) 生成长度的多集的唯一组合 k . 为了 s='xxyy' 这些将是 ['xx','xy','yy'] . RunVal向量(V) 将表示为排序向量的多集转换为更简单的结构runvector。 runvector('cddeee')=[1,2,3] .

为了解决这个问题,我们将使用递归生成器。我们浏览了所有适合框1的组合和对其余框的追索权,禁止我们已经选择的值。为了完成禁令, 组合 将在多个调用之间维护一个位数组。

在python中,方法如下:

def fillrest(banned,out,rv,b,i):
    if i == len(rv):
        yield None
        return
    for comb in combinations(b,rv[i],banned):
        out[i] = comb
        for rest in fillrest(banned,out,rv,b,i+1):
            yield None

def balls(a,b):
    rv = runvector(a)
    banned = [False for _ in b]
    out = [None for _ in rv]
    for _ in fill(out,rv,0,b,banned):
        yield out[:]

>>> print list(balls('abbccc','xyyzzz'))
[['x', 'yy', 'zzz'],
 ['x', 'yz', 'yzz'],
 ['x', 'zz', 'yyz'],
 ['y', 'xy', 'zzz'],
 ['y', 'xz', 'yzz'],
 ['y', 'yz', 'xzz'],
 ['y', 'zz', 'xyz'],
 ['z', 'xy', 'yzz'],
 ['z', 'xz', 'yyz'],
 ['z', 'yy', 'xzz'],
 ['z', 'yz', 'xyz'],
 ['z', 'zz', 'xyy']]

输出为“box”格式,但可以轻松合并回简单字符串: 'xyyzzzz' , 'xyzyzz' …