递归地找到一组 n 个对象的所有分区到 k 个非空子集中

Question

我想找到 n 个元素到 k 个子集中的所有分区，这是我基于递归公式查找所有 Stirling second numbers

的算法

fun main(args: Array<String>) {
    val s = mutableSetOf(1, 2, 3, 4, 5)
    val partitions = 3
    val res = mutableSetOf<MutableSet<MutableSet<Int>>>()
    partition(s, partitions, res)
    //println(res)
    println("Second kind stirling number ${res.size}")
}

fun partition(inputSet: MutableSet<Int>, numOfPartitions: Int, result: MutableSet<MutableSet<MutableSet<Int>>>) {
    if (inputSet.size == numOfPartitions) {
        val sets = inputSet.map { mutableSetOf(it) }.toMutableSet()
        result.add(sets)
    }
    else if (numOfPartitions == 1) {
        result.add(mutableSetOf(inputSet))
    }
    else {
        val popped: Int = inputSet.first().also { inputSet.remove(it) }

        val r1 = mutableSetOf<MutableSet<MutableSet<Int>>>()
        partition(inputSet, numOfPartitions, r1) //add popped to each set in solution (all combinations)

        for (solution in r1) {
            for (set in solution) {
                set.add(popped)
                result.add(solution.map { it.toMutableSet() }.toMutableSet()) //deep copy
                set.remove(popped)
            }
        }
        val r2 = mutableSetOf<MutableSet<MutableSet<Int>>>()
        partition(inputSet, numOfPartitions - 1, r2) //popped is single elem set

        r2.map { it.add(mutableSetOf(popped)) }
        r2.map { result.add(it) }
    }
}

代码适用于 k = 2，但对于更大的 n 和 k，它会丢失一些分区，我在这里找不到错误。示例：n = 5 和 k = 3 个输出 Second kind stirling number 19 正确的输出应该是 25。

Answer 1

如果您可以阅读 Python 代码，请考虑下一个算法，该算法是我从我的 set partition into equal size parts 的实现中快速改编而来的。

递归函数用 N 个值填充 K 个部分。

lastfilled 参数有助于避免重复 - 它提供了每个部分的前导（最小）元素的递增序列。

empty参数是为了避免空的部分。

def genp(parts:list, empty, n, k, m, lastfilled):
    if m == n:
        print(parts)
        global c
        c+=1
        return
    if n - m == empty:
        start = k - empty
    else:
        start = 0
    for i in range(start, min(k, lastfilled + 2)):
        parts[i].append(m)
        if len(parts[i]) == 1:
            empty -= 1
        genp(parts, empty, n, k, m+1, max(i, lastfilled))
        parts[i].pop()
        if len(parts[i]) == 0:
            empty += 1


def setkparts(n, k):
    parts = [[] for _ in range(k)]
    cnts = [0]*k
    genp(parts, k, n, k, 0, -1)

c = 0
setkparts(5,3)
#setkparts(7,5)
print(c)

[[0, 1, 2], [3], [4]]
[[0, 1, 3], [2], [4]]
[[0, 1], [2, 3], [4]]
[[0, 1, 4], [2], [3]]
[[0, 1], [2, 4], [3]]
[[0, 1], [2], [3, 4]]
[[0, 2, 3], [1], [4]]
[[0, 2], [1, 3], [4]]
[[0, 2, 4], [1], [3]]
[[0, 2], [1, 4], [3]]
[[0, 2], [1], [3, 4]]
[[0, 3], [1, 2], [4]]
[[0], [1, 2, 3], [4]]
[[0, 4], [1, 2], [3]]
[[0], [1, 2, 4], [3]]
[[0], [1, 2], [3, 4]]
[[0, 3, 4], [1], [2]]
[[0, 3], [1, 4], [2]]
[[0, 3], [1], [2, 4]]
[[0, 4], [1, 3], [2]]
[[0], [1, 3, 4], [2]]
[[0], [1, 3], [2, 4]]
[[0, 4], [1], [2, 3]]
[[0], [1, 4], [2, 3]]
[[0], [1], [2, 3, 4]]
25

Answer 2

不确定，您的代码中的确切问题是什么，但是以递归方式查找所有斯特林秒数要简单得多：

private val memo = hashMapOf<Pair<Int, Int>, BigInteger>()
fun stirling2(n: Int, k: Int): BigInteger {
    val key = n to k
    return memo.getOrPut(key) {
        when {
            k == 0 || k > n -> BigInteger.ZERO
            n == k -> BigInteger.ONE
            else -> k.toBigInteger() * stirling2(n - 1, k) + stirling2(n - 1, k - 1)
        }
    }
}

Answer 3

我改进了 Kornel_S' 代码。有一个函数可以列出所有可能的组合。小心大数字:)

def Stirling2Iterate(List):
    
    Result = []
    
    def genp(parts:list, empty, n, k, m, lastfilled):
        
        if m == n:
            nonlocal Result
            nonlocal List
            Result += [ [[List[item2] for item2 in item] for item in parts] ]
            return
        
        if n - m == empty: start = k - empty
        else: start = 0
        
        for i in range(start, min(k, lastfilled + 2)):
            
            parts[i].append(m)
            if len(parts[i]) == 1: empty -= 1
            genp(parts, empty, n, k, m + 1, max(i, lastfilled))
            parts[i].pop()
            if len(parts[i]) == 0: empty += 1
    
    def setkparts(n, k):
        parts = [ [] for _ in range(k) ]
        cnts = [0] * k
        genp(parts, k, n, k, 0, -1)
    
    for i in range(len(List)): setkparts(len(List), i + 1)
    
    return Result

示例：

# EXAMPLE

print('\n'.join([f"{x}" for x in Stirling2Iterate(['A', 'B', 'X', 'Z'])]))

# OUTPUT

[['A', 'B', 'X', 'Z']]
[['A', 'B', 'X'], ['Z']]
[['A', 'B', 'Z'], ['X']]
[['A', 'B'], ['X', 'Z']]
[['A', 'X', 'Z'], ['B']]
[['A', 'X'], ['B', 'Z']]
[['A', 'Z'], ['B', 'X']]
[['A'], ['B', 'X', 'Z']]
[['A', 'B'], ['X'], ['Z']]
[['A', 'X'], ['B'], ['Z']]
[['A'], ['B', 'X'], ['Z']]
[['A', 'Z'], ['B'], ['X']]
[['A'], ['B', 'Z'], ['X']]
[['A'], ['B'], ['X', 'Z']]
[['A'], ['B'], ['X'], ['Z']]

递归地找到一组 n 个对象的所有分区到 k 个非空子集中

Recursively finding all partitions of a set of n objects into k non-empty subsets

algorithm

np-hard

kotlin