Генерация шаров в коробках

Для создания k-комбинаций возможных повторяющихся элементов (мультимножества) может быть полезно следующее: Код Грея для комбинаций мультимножества (1995).

Для рекурсивного решения попробуйте следующее:

Подсчитайте, сколько раз появляется каждый символ. Скажем, они равны x1 x2 ... xm, что соответствует m различным символам.

Затем нужно найти все возможные упорядоченные пары (y1 y2 ... ym) такие, что

0 <= yi <= xi

и Сумма yi = k.

Здесь yi — количество раз появления символа i.

Идея состоит в том, чтобы исправить количество появлений символа 1 (y1). Затем рекурсивно сгенерируйте все комбинации k-y1 из оставшихся.

псевдокод:

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 элементов, и сопоставить эти символы в соответствующих позициях. Остальное вы можете игнорировать/заполнять по своему усмотрению.

Я помню, как публиковал код С# для этого здесь: >Как найти перестановку k заданной длины?

Я предполагаю, что xxyy даст только 1 уникальную строку, а те, которые появляются ровно один раз, являются «отличительными» точками.

Например, в случае a=xyy, b=add

отличительная черта х

Таким образом, вы выбираете перестановки «добавить» длины 1. Это дает вам a и d.

Таким образом, вам нужны add и dad (or dda).

Для a=xyyz b=good

отличительные точки x и z

Итак, вы генерируете перестановки b длины 2, дающие

go
og
oo
od
do
gd
dg

давая вам 7 уникальных перестановок.

Это помогает? Правильно ли я понимаю?

Хорошо, извините, я никогда не мог четко объяснить проблему, но вот решение.

Нам нужны две функции combinations и runvector(v). combinations(s,k) генерирует уникальные комбинации мультимножества длины k. Для s='xxyy' это будет ['xx','xy','yy']. runvector(v) преобразует мультимножество, представленное в виде отсортированного вектора, в более простую структуру, вектор выполнения. runvector('cddeee')=[1,2,3].

Для решения задачи воспользуемся рекурсивными генераторами. Мы прогоняем все комбинации, которые подходят для поля 1, и обращение к остальным полям, запрещая значения, которые мы уже выбрали. Чтобы выполнить запрет, combinations будет поддерживать битовый массив вызовов.

В питоне подход выглядит так:

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']]

Выходные данные имеют формат «коробки», но могут быть легко объединены обратно в простые строки: 'xyyzzzz', 'xyzyzz'...