Алгоритм генерации связующего множества

Question

Учитывая этот вход: [1,2,3,4]

Я хотел бы создать набор связующих наборов:

[1] [2] [3] [4]
[1] [2] [3,4]
[1] [2,3] [4]
[1] [3] [2,4]
[1,2] [3] [4]
[1,3] [2] [4]
[1,4] [2] [3]
[1,2] [3,4]
[1,3] [2,4]
[1,4] [2,3]
[1,2,3] [4]
[1,2,4] [3]
[1,3,4] [2]
[2,3,4] [1]
[1,2,3,4]

У каждого набора есть все элементы исходного набора, переставленные, чтобы появиться в уникальных подмножествах. Каков алгоритм, который производит эти наборы? Я пробовал функции генератора Python, используя выбор, перестановку, комбинацию, набор мощности и т. Д., Но не могу получить правильную комбинацию.

20 января 2009

Это не домашнее задание. Это улучшенный ответ, над которым я работал для проблемы www.projecteuler.net # 118. У меня уже было медленное решение, но я нашел лучший способ - за исключением того, что я не мог понять, как сделать набор связывания.

Я опубликую свой код, когда вернусь с инаугурации.

21 января 2009

Это возможный алгоритм, который я использовал:

def spanningsets(items):
    if len(items) == 1:
        yield [items]
    else:
        left_set, last = items[:-1], [items[-1]]
        for cc in spanningsets(left_set):
            yield cc + [last]
            for i,elem in enumerate(cc):
                yield cc[:i] + [elem + last] + cc[i+1:]

@ Yuval F: Я знаю, как сделать powerset. Вот простая реализация:

def powerset(s) :
    length = len(s)
    for i in xrange(0, 2**length) :
        yield [c for j, c in enumerate(s) if (1 << j) & i]
    return

Answer 1

Это должно сработать, хотя я не достаточно протестировал.

def spanningsets(items):
    if not items: return
    if len(items) == 1:
        yield [[items[-1]]]
    else:
        for cc in spanningsets(items[:-1]):
            yield cc + [[items[-1]]]
            for i in range(len(cc)):
                yield cc[:i] + [cc[i] + [items[-1]]] + cc[i+1:]

for sset in spanningsets([1, 2, 3, 4]):
    print ' '.join(map(str, sset))

Выход:

[1] [2] [3] [4]
[1, 4] [2] [3]
[1] [2, 4] [3]
[1] [2] [3, 4]
[1, 3] [2] [4]
[1, 3, 4] [2]
[1, 3] [2, 4]
[1] [2, 3] [4]
[1, 4] [2, 3]
[1] [2, 3, 4]
[1, 2] [3] [4]
[1, 2, 4] [3]
[1, 2] [3, 4]
[1, 2, 3] [4]
[1, 2, 3, 4]

Answer 2

А как насчет этого? Я еще не проверял, но попробую позже ...

Я думаю, что этот метод называется динамическим программированием:

1. Возьмите первый элемент [1]
   Что вы можете создать с ним? Только [1]

2. Возьми второй [2]
   Теперь у вас есть две возможности: [1,2] и [1] [2]

3. Возьмите третий [3]
   С первым номером 2 [1,2] можно создать [1,2,3] и [1,2] [3]
   Со вторым из числа 2 [1] [2] можно создать [1,3] [2] и [1] [2,3] и [1] [2] [3]

Надеюсь, достаточно ясно, что я пытался показать. (Если нет, оставьте комментарий!)

Answer 3

Я думаю, что следующий метод является лучшим способом генерирования их для задачи Эйлера, поскольку вы можете заменить возвращаемое значение на число простых подмножеств охвата, и умножение будет тривиальным (особенно с запоминанием):

GenerateSubsets(list)
    partitions = { x | x is subset of list and x contains the lowest element of list }
    foreach (parition in partitions)
        if set == list
            yield { partition }
        else
            yield { partition } x GenerateSubsets(list - part)

Ключевая часть - убедиться, что у рекурсивной стороны всегда есть крайний левый элемент, таким образом, вы не получите дубликаты.

У меня есть грязный код C #, который делает это:

    IEnumerable<IEnumerable<List<int>>> GenerateSubsets(List<int> list)
    {
        int p = (1 << (list.Count)) - 2;
        List<int> lhs = new List<int>();
        List<int> rhs = new List<int>();
        while (p >= 0)
        {
            for (int i = 0; i < list.Count; i++)
                if ((p & (1 << i)) == 0)
                    lhs.Add(list[i]);
                else
                    rhs.Add(list[i]);

            if (rhs.Count > 0)
                foreach (var rhsSubset in GenerateSubsets(rhs))
                    yield return Combine(lhs, rhsSubset);
            else
                yield return Combine(lhs, null);

            lhs.Clear();
            rhs.Clear();
            p -= 2;
        }
    }

    IEnumerable<List<int>> Combine(List<int> list, IEnumerable<List<int>> rest)
    {
        yield return list;
        if (rest != null)
            foreach (List<int> x in rest)
                yield return x;
    }

Answer 4

Наборы результатов вместе с пустым набором {} похожи на результаты powerset (или power set), но это не одно и то же.

Я начал публикацию о подобной проблеме, которая имеет несколько реализаций (хотя и в C #) и в некоторых случаях ориентирована больше на скорость, чем на ясность. Первый пример должен быть легко переведен. Может быть, это все равно даст несколько идей.

Они работают по принципу, согласно которому подсчет комбинаций аналогичен подсчету в двоичном (представьте себе, что нужно считать от 0 до 16). Вы не указываете, важен ли порядок, или просто генерируете все комбинации, поэтому после этого можно будет быстро привести порядок в порядок.

Посмотрите здесь (игнорируйте нечетное название, обсуждение пошло в другом направлении)

Answer 5

Вот Страница репозитория алгоритма SUNY . Возможно, вы можете перевести одну из ссылок кода на python.

Редактировать: это была похожая проблема. Здесь - это страница репозитория SUNY о создании разделов, которая, я считаю, является правильной.