将N个元素的每个子集划分为K个存储桶的算法 [英] Algorithm to partition every subset of N elements into K buckets

问题描述

我要实现的方法类似于

/*
    e.g. {1, 2, 3}, k = 2

    ---> 

        [ (), () ],
        [ (1), () ],
        [ (), (1) ],
        [ (2), () ],
        [ (), (2) ],
        [ (3), () ],
        [ (), (3) ],
        [ (1), (2) ],
        [ (2), (1) ],
        [ (1), (3) ],
        [ (3), (1) ],
        [ (2), (3) ],
        [ (3), (2) ],
        [ (1,2), () ],
        [ (2,3), () ],
        [ (1,3), () ],
        [ (), (1,2) ],
        [ (), (1,3) ],
        [ (), (2,3) ],
        [ (1,2), (3) ],
        [ (2,3), (1) ],
        [ (1,3), (2) ],
        [ (3), (1,2) ],
        [ (1), (2,3) ],
        [ (2), (1,3) ],
        [ (1,2,3), () ],
        [ (), (1,2,3,) ]

*/

    public static List<List<T>> SpecialPartition<T>(this List<T> source, int k)
    {
        throw new NotImplementedException();
    }

我首先想知道是否存在某些已知的（Donald Knuth？）算法这样做。请注意存储桶的顺序如何重要，例如我认为（1,2），（3）和（3），（1,2）是单独的结果。

I'm first wondering whether there's some known (Donald Knuth?) algorithm for doing this. Note how the order of the buckets matters, e.g. I consider (1,2), (3) and (3), (1,2) as separate results.

推荐答案

请注意，每个元素都可以占据（K + 1）位置（K个桶，任何桶中只有一个）。

Note that every element could occupy one of (K+1) places (K buckets and one place out of any bucket).

所以有 M =（K + 1）^ N 个组合（此处（ 2 + 1）^ 3 = 27个变体），范围 0..M-1 中的每个数字都对应唯一的组合（一对一一个映射）。

So there are M=(K+1)^N combinations (here (2+1)^3=27 variants) and every number in range 0..M-1 corresponds to unique combination (one-to-one mapping).

生成所有组合的简单方法是对范围 0..M-1 并表示（K + 1）进制数字系统中的循环计数器

So simple way to generate all combinations is to make loop for range 0..M-1 and represent loop counter in (K+1)-ary numeral system

for C = 0..M-1
   d = C
   for i = 0..N-1
     Bucket for i-th element = d %% (K+1)
     d = d / (K+1)

例如，21 ₁₀ = 210 ₃ 被映射：第二个存储桶中的第一个元素，第一个存储桶中的第二个元素，第三个元素关闭： [（2），（1）]

For example, 21₁₀=210₃ might be mapped: the first element in the 2nd bucket, second element in the 1st bucket, and the third element is off: [ (2), (1) ]

16 ₁₀ = 121 ₃ ： [（1,3），（2）]

16₁₀=121₃: [ (1,3), (2) ]

这篇关于将N个元素的每个子集划分为K个存储桶的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！