Как найти все разделы набора

Ответ 1

Я нашел прямое рекурсивное решение.

Во-первых, разрешите более простую задачу: как найти все разделы, состоящие из ровно двух частей. Для n-элементного множества мы можем считать int от 0 до (2 ^ n) -1. Это создает каждый n-битовый шаблон, каждый бит которого соответствует одному входному элементу. Если бит равен 0, мы помещаем элемент в первую часть; если он равен 1, элемент помещается во вторую часть. Это оставляет одну проблему: для каждого раздела мы получим дублирующий результат, когда две части будут заменены. Чтобы исправить это, мы всегда ставим первый элемент в первую часть. Затем мы распределяем оставшиеся n-1 элементы, считая от 0 до (2 ^ (n-1)) -1.

Теперь, когда мы можем разбить множество на две части, мы можем написать рекурсивную функцию, которая решает остальную часть проблемы. Функция начинается с исходного набора и находит все разделы с двумя частями. Для каждого из этих разделов он рекурсивно находит все способы разбиения второй части на две части, что дает все трехчастные разделы. Затем он делит последнюю часть каждого из этих разделов на создание всех четырехчастных разделов и т.д.

Ниже приведена реализация в С#. Вызов

Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 })

дает

{ {1, 2, 3, 4} },
{ {1, 3, 4}, {2} },
{ {1, 2, 4}, {3} },
{ {1, 4}, {2, 3} },
{ {1, 4}, {2}, {3} },
{ {1, 2, 3}, {4} },
{ {1, 3}, {2, 4} },
{ {1, 3}, {2}, {4} },
{ {1, 2}, {3, 4} },
{ {1, 2}, {3}, {4} },
{ {1}, {2, 3, 4} },
{ {1}, {2, 4}, {3} },
{ {1}, {2, 3}, {4} },
{ {1}, {2}, {3, 4} },
{ {1}, {2}, {3}, {4} }.

using System;
using System.Collections.Generic;
using System.Linq;

namespace PartitionTest {
    public static class Partitioning {
        public static IEnumerable<T[][]> GetAllPartitions<T>(T[] elements) {
            return GetAllPartitions(new T[][]{}, elements);
        }

        private static IEnumerable<T[][]> GetAllPartitions<T>(
            T[][] fixedParts, T[] suffixElements)
        {
            // A trivial partition consists of the fixed parts
            // followed by all suffix elements as one block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Get all two-group-partitions of the suffix elements
            // and sub-divide them recursively
            var suffixPartitions = GetTuplePartitions(suffixElements);
            foreach (Tuple<T[], T[]> suffixPartition in suffixPartitions) {
                var subPartitions = GetAllPartitions(
                    fixedParts.Concat(new[] { suffixPartition.Item1 }).ToArray(),
                    suffixPartition.Item2);
                foreach (var subPartition in subPartitions) {
                    yield return subPartition;
                }
            }
        }

        private static IEnumerable<Tuple<T[], T[]>> GetTuplePartitions<T>(
            T[] elements)
        {
            // No result if less than 2 elements
            if (elements.Length < 2) yield break;

            // Generate all 2-part partitions
            for (int pattern = 1; pattern < 1 << (elements.Length - 1); pattern++) {
                // Create the two result sets and
                // assign the first element to the first set
                List<T>[] resultSets = {
                    new List<T> { elements[0] }, new List<T>() };
                // Distribute the remaining elements
                for (int index = 1; index < elements.Length; index++) {
                    resultSets[(pattern >> (index - 1)) & 1].Add(elements[index]);
                }

                yield return Tuple.Create(
                    resultSets[0].ToArray(), resultSets[1].ToArray());
            }
        }
    }
}

Ответ 2

Вот нерекурсивное решение

class Program
{
    static void Main(string[] args)
    {
        var items = new List<Char>() { 'A', 'B', 'C', 'D', 'E' };
        int i = 0;
        foreach (var partition in items.Partitions())
        {
            Console.WriteLine(++i);
            foreach (var group in partition)
            {
                Console.WriteLine(string.Join(",", group));
            }
            Console.WriteLine();
        }
        Console.ReadLine();
    }
}  

public static class Partition
{
    public static IEnumerable<IList<IList<T>>> Partitions<T>(this IList<T> items)
    {
        if (items.Count() == 0)
            yield break;
        var currentPartition = new int[items.Count()];
        do
        {
            var groups = new List<T>[currentPartition.Max() + 1];
            for (int i = 0; i < currentPartition.Length; ++i)
            {
                int groupIndex = currentPartition[i];
                if (groups[groupIndex] == null)
                    groups[groupIndex] = new List<T>();
                groups[groupIndex].Add(items[i]);
            }
            yield return groups;
        } while (NextPartition(currentPartition));
    }

    private static bool NextPartition(int[] currentPartition)
    {
        int index = currentPartition.Length - 1;
        while (index >= 0)
        {
            ++currentPartition[index];
            if (Valid(currentPartition))
                return true;
            currentPartition[index--] = 0;
        }
        return false;
    }

    private static bool Valid(int[] currentPartition)
    {
        var uniqueSymbolsSeen = new HashSet<int>();
        foreach (var item in currentPartition)
        {
            uniqueSymbolsSeen.Add(item);
            if (uniqueSymbolsSeen.Count <= item)
                return false;
        }
        return true;
    }
}

Ответ 3

Вот решение в Ruby, что около 20 строк:

def copy_2d_array(array)
  array.inject([]) {|array_copy, item| array_copy.push(item)}
end

#
# each_partition(n) { |partition| block}
#
# Call the given block for each partition of {1 ... n}
# Each partition is represented as an array of arrays.
# partition[i] is an array indicating the membership of that partition.
#
def each_partition(n)
  if n == 1
    # base case:  There is only one partition of {1}
    yield [[1]]
  else
    # recursively generate the partitions of {1 ... n-1}.
    each_partition(n-1) do |partition|
      # adding {n} to a subset of partition generates
      # a new partition of {1 ... n}
      partition.each_index do |i|
        partition_copy = copy_2d_array(partition)
        partition_copy[i].push(n)
        yield (partition_copy)    
      end # each_index

      # Also adding the set {n} to a partition of {1 ... n}
      # generates a new partition of {1 ... n}
      partition_copy = copy_2d_array(partition)
      partition_copy.push [n]
      yield(partition_copy)
    end # block for recursive call to each_partition
  end # else
end # each_partition

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

Ответ 4

Трюк, который я использовал для набора из N элементов. 1. Вычислить 2 ^ N 2. Напишите каждое число между 1 и N в двоичном формате. 3. Вы получите двоичные числа 2 ^ N каждой длины N, и каждое число сообщит вам, как разбить набор на подмножества A и B. Если k-я цифра равна 0, тогда поместите k-й элемент в множество A в противном случае это в наборе B.

Ответ 5

Пожалуйста, обратитесь к номеру колокола, вот краткая мысль об этой проблеме:
рассмотрим f (n, m) как разбиение множества n элементов на m непустых множеств.

Например, разбиение набора из трех элементов может быть следующим:
1) установить размер 1: {{1,2,3},} < - f (3,1)
2) установить размер 2: {{1,2}, {3}}, {{1,3}, {2}}, {{2,3}, {1}} < - f (3,2 )
3) установить размер 3: {{1}, {2}, {3}} < - f (3,3)

Теперь давайте вычислим f (4,2):
существует два способа сделать f (4,2):

а. добавьте набор в f (3,1), который преобразует из {{1,2,3},} в {{1,2,3}, {4}}
B. добавьте 4 к любому из множества f (3,2), который преобразуется из
{{1,2}, {3}}, {{1,3}, {2}}, {{2,3}, {1}}
для изображения {{1,2,4}, {3}}, {{1,2}, {3,4}}
{{1,3,4}, {2}}, {{1,3}, {2,4}}
{{2,3,4}, {1}}, {{2,3}, {1,4}}

So f(4,2) = f(3,1) + f(3,2)*2
которые приводят к f(n,m) = f(n-1,m-1) + f(n-1,m)*m

Вот код Java для получения всех разделов набора:

import java.util.ArrayList;
import java.util.List;

public class SetPartition {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<=3; i++) {
            list.add(i);
        }

        int cnt = 0;
        for(int i=1; i<=list.size(); i++) {
            List<List<List<Integer>>> ret = helper(list, i);
            cnt += ret.size();
            System.out.println(ret);
        }
        System.out.println("Number of partitions: " + cnt);
    }

    // partition f(n, m)
    private static List<List<List<Integer>>> helper(List<Integer> ori, int m) {
        List<List<List<Integer>>> ret = new ArrayList<>();
        if(ori.size() < m || m < 1) return ret;

        if(m == 1) {
            List<List<Integer>> partition = new ArrayList<>();
            partition.add(new ArrayList<>(ori));
            ret.add(partition);
            return ret;
        }

        // f(n-1, m)
        List<List<List<Integer>>> prev1 = helper(ori.subList(0, ori.size() - 1), m);
        for(int i=0; i<prev1.size(); i++) {
            for(int j=0; j<prev1.get(i).size(); j++) {
                // Deep copy from prev1.get(i) to l
                List<List<Integer>> l = new ArrayList<>();
                for(List<Integer> inner : prev1.get(i)) {
                    l.add(new ArrayList<>(inner));
                }

                l.get(j).add(ori.get(ori.size()-1));
                ret.add(l);
            }
        }

        List<Integer> set = new ArrayList<>();
        set.add(ori.get(ori.size() - 1));
        // f(n-1, m-1)
        List<List<List<Integer>>> prev2 = helper(ori.subList(0, ori.size() - 1), m - 1);
        for(int i=0; i<prev2.size(); i++) {
            List<List<Integer>> l = new ArrayList<>(prev2.get(i));
            l.add(set);
            ret.add(l);
        }

        return ret;
    }

}

И результат:
[[[1, 2, 3]]] [[[1, 3], [2]], [[1], [2, 3]], [[1, 2], [3]]] [[[1], [2], [3]]] Number of partitions: 5

Ответ 6

Просто для удовольствия, здесь короче чисто итеративная версия:

public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements) {
    var lists = new List<List<T>>();
    var indexes = new int[elements.Length];
    lists.Add(new List<T>());
    lists[0].AddRange(elements);
    for (;;) {
        yield return lists;
        int i,index;
        for (i=indexes.Length-1;; --i) {
            if (i<=0)
                yield break;
            index = indexes[i];
            lists[index].RemoveAt(lists[index].Count-1);
            if (lists[index].Count>0)
                break;
            lists.RemoveAt(index);
        }
        ++index;
        if (index >= lists.Count)
            lists.Add(new List<T>());
        for (;i<indexes.Length;++i) {
            indexes[i]=index;
            lists[index].Add(elements[i]);
            index=0;
        }
    }

Тест здесь: https://ideone.com/EccB5n

И более простая рекурсивная версия:

public static IEnumerable<List<List<T>>> GetAllPartitions<T>(T[] elements, int maxlen) {
    if (maxlen<=0) {
        yield return new List<List<T>>();
    }
    else {
        T elem = elements[maxlen-1];
        var shorter=GetAllPartitions(elements,maxlen-1);
        foreach (var part in shorter) {
            foreach (var list in part.ToArray()) {
                list.Add(elem);
                yield return part;
                list.RemoveAt(list.Count-1);
            }
            var newlist=new List<T>();
            newlist.Add(elem);
            part.Add(newlist);
            yield return part;
            part.RemoveAt(part.Count-1);
        }
    }

https://ideone.com/Kdir4e

Ответ 7

Я реализовал Дональда Кнута очень хороший алгоритм H, в котором перечислены все разделы в Matlab

https://uk.mathworks.com/matlabcentral/fileexchange/62775-allpartitions--s-- http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz

function [ PI, RGS ] = AllPartitions( S )
    %% check that we have at least two elements
    n = numel(S);
    if n < 2
        error('Set must have two or more elements');
    end    
    %% Donald Knuth Algorith H
    % restricted growth strings
    RGS = [];
    % H1
    a = zeros(1,n);
    b = ones(1,n-1);
    m = 1;
    while true
        % H2
        RGS(end+1,:) = a;
        while a(n) ~= m            
            % H3
            a(n) = a(n) + 1;
            RGS(end+1,:) = a;
        end
        % H4
        j = n - 1;
        while a(j) == b(j)
           j = j - 1; 
        end
        % H5
        if j == 1
            break;
        else
            a(j) = a(j) + 1;
        end
        % H6
        m = b(j) + (a(j) == b (j));
        j = j + 1;
        while j < n 
            a(j) = 0;
            b(j) = m;
            j = j + 1;
        end
        a(n) = 0;
    elementsd
    %% get partitions from the restricted growth stirngs
    PI = PartitionsFromRGS(S, RGS);
end