相关疑难解决方法(0)

powerset {1, 2, 3}是:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

假设我有一个SetJava语言:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

如何以最佳的复杂度顺序编写函数getPowerset？(我想它可能是O(2 ^ n).)

我希望将ac#方法重构为ac函数以试图获得一些速度,然后在c#中调用c dll以允许我的程序使用该功能.

目前,c#方法采用整数列表并返回整数列表的列表.该方法计算了整数的幂集,因此3个int的输入将产生以下输出(在此阶段,int的值不重要,因为它用作内部加权值)

1
2
3
1,2
1,3
2,3
1,2,3

每行代表一个整数列表.输出指示第一个列表的索引(偏移量为1),而不是值.因此1,2表示索引0和1处的元素是幂集的元素.

我不熟悉c,那么对于允许c#访问返回数据的数据结构,我最好的选择是什么？

提前致谢

更新

谢谢大家到目前为止的评论.以下是问题本质的背景知识.

用于计算集合的幂集的迭代方法是相当直接的.真正有两个循环和一点点操作.它只是被称为..很多(事实上,如果集合的大小足够大,数十亿次).

我对使用c(c ++,正如人们所指出的)的看法是,它为性能调优提供了更多的空间.直接端口可能不会提供任何增加,但它为更多涉及的方法开辟了道路,以便从中获得更高的速度.即使每次迭代的小幅增加也等同于可测量的增长.

我的想法是移植直接版本,然后努力增加它.然后随着时间的推移重构它(在SO的每个人的帮助下).

更新2

来自jalf的另一个公平点,我不必使用list或equivelent.如果有更好的方法,那么我愿意接受建议.列表的唯一原因是每组结果的大小不同.

到目前为止的代码......

public List<List<int>> powerset(List<int> currentGroupList)
{
    _currentGroupList = currentGroupList;
    int max;
    int count;

    //Count the objects in the group
    count = _currentGroupList.Count;
    max = (int)Math.Pow(2, count);

    //outer loop
    for (int i = 0; i < max; i++)
    {
        _currentSet = new List<int>();

        //inner loop
        for (int j = 0; j < count; j++)
        {              
            if ((i & (1 << …

编辑:我的意思是组合,而不是PERMUTATIONS

是否有有效的算法可以返回给定数组中的所有不同的排列？["A","B","C","D","E","F","G","H","I","J","K",......]

例如:AB,AC,AD,..,DE,..,HI,..,ABC,ABD,...,DEF,..,CDEFG,...,ABCDEFGHIJK,....

我发现了一些算法,但它们返回所有排列而不是不同的排列.通过不同我的意思是:

1. AB&BA是相同的排列

2. DEF&FED和EFD&DFE是相同的排列,