1

我希望从大小为 n 的 r 个元素生成一个幂多集。

说功能是

public List<List<string>> PowerMultiSet (List<string> elems, int n )

示例输入：{"d1","d2",d3"}，n=2 输出：{"d1","d1"}, {"d1","d2"},{"d1","d3"} ,{"d2","d2"}, {"d2","d3"},{"d3","d3"} 说elems的大小是r，生成的元素个数是C(n+r- 1,r-1)。

我想知道如何在没有冗余操作的情况下实现这一点（即数字操作理想情况下应该是 = C(r+n-1,n-1)）

非常感谢！

4

3 回答 3

2

我认为以下代码可以解决问题：

void MultiSet(List<string> elems, int last, int n, ref List<string> set, ref List<List<string>> result)
{
    if (set.Count < n)
    {
        for (int index = last; index < elems.Count; index++)
        {
            set.Add(elems[index]);
            MultiSet(elems, index, n, ref set, ref result);
            set.RemoveAt(set.Count - 1);
        }
    }
    else
    {
        result.Add(new List<string>(set));
    }
}

List<List<string>> PowerMultiSet(List<string> elems, int n)
{
    var result = new List<List<string>>();
    var set = new List<string>();
    MultiSet(elems, 0, n, ref set, ref result);
    return result;
}
于 2012-07-18T08:00:09.053 回答
1

这可以通过递归方式实现。用空调用下面的函数start以开始递归。

public List<List<string>> PowerMultiSet (List<string> start, List<string> elems, int n )
{
    List<List<string>> output = new List<List<string>>();
    if (n > 0)
    {
        for (int i = 0; i < elems.Count; i++)
        {
            start.Add(elems[i]);
            List<List<string>> current = PowerMultiSet(start, elems.GetRange(i, elems.Count - i), n - 1);
            start.RemoveAt(start.Count - 1);
            output.AddRange(current);
        }
    }
    else
    {
        output.Add(new List<string>(start));
    }
    return output;
}

示例调用：

List<string> elems = new List<string> { "d1", "d2", "d3"};
List<string> start = new List<string>();
List<List<string>> x = PowerMultiSet(start, elems, 3);
于 2012-07-18T06:43:42.693 回答
0

这本质上是排列问题，除了每个排列的长度已经确定。为简化起见，假设我们正在打印集合并定义以下递归函数：

public void PrintPowerMultiSets(List<string> elems, int index, List<string> ps, int num_left)

其中 index 是我们要添加到 powerset 的元素的以 elems 为单位的索引，ps 是该分支中当前构建的 powerset，num_left 是我们仍然可以添加到 ps 的元素数。在对该函数的每次递归调用中，将 elems[index] 添加到 ps 并为 elems 中具有索引 <= 传入索引的每个元素调用 PrintPowerMultiSets 和 num_left-1。一旦您没有更多元素要添加到该 powerset 并打印它（或将其添加到某个列表），就停止递归。

您只需为列表中的每个元素调用一次此函数即可。如果您完成它，我相信您会发现这与您手动枚举原始问题中的输出的方式相同。

于 2012-07-18T06:33:56.963 回答