Алгоритм для создания набора spanning

Ответ 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]

Ответ 2

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

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

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

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

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

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

Ответ 3

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

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

Ответ 4

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

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)

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

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

    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;
    }

Ответ 5

Результат, созданный вместе с пустым множеством {}, выглядит как результат poweret (или набор мощности), но это не то же самое.

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

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

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