查找给定整数列表的唯一子集列表

正在寻找一种有效的方法来确定整数列表的所有唯一子集。

假设我有一个包含340个整数的整数列表。我想要一个所有可能子集的列表（每个子集有5个元素）。所有提供的整数都是唯一的，结果不应与它的子集中的任何元素重复。一个例子给出了1,2,3,4,5,6,7,8,9的输入，我正在寻找的输出

1,2,3,4,5
1,2,3,4,6
1,2,3,4,7
1,2,3,4,8
1,2,3,4,9
1,2,3,5,6
1,2,3,5,7

我必须在CSharp中这样做。这可以在LINQ中完成吗？

我已经回答了几个组合问题，在任何地方我都使用非递归无分配算法的变体。对于这种情况，它看起来是这样的：

public static class Algorithms
{
    public static IEnumerable<T[]> GetCombinations<T>(this T[] input, int N)
    {
        var result = new T[N];
        var indices = new int[N];
        for (int pos = 0, index = 0; ;)
        {
            for (; pos < N; pos++, index++)
            {
                indices[pos] = index;
                result[pos] = input[index];
            }
            yield return result;
            do
            {
                if (pos == 0) yield break;
                index = indices[--pos] + 1;
            }
            while (index > input.Length - N + pos);
        }
    }
}

与其他实现一样，该方法产生一个相同的内部缓冲区，当您只需要迭代和处理一次结果集时，这很有用。如果你需要存储组合，那么你需要在存储之前克隆返回的数组

var input = Enumerable.Range(1, 20);
var result = input
    .Distinct()
    .ToArray()
    .GetCombinations(5)
    .Select(c => (int[])c.Clone())
    .ToList();

UPDATE：GetCombinations方法基本上模拟N嵌套循环，如下所示（在伪代码中）：

for（int i₀=0；i₀<=输入。长度-N；i₀++）
for（int i₁=i₀+1；i₁<=输入。长度-N+1；i_{1_{++）
for（int i₂=i₁1；i₂<=输入。长度-N+2；i_{2_{++）
…
for（int i_N-1=i_N-2+1；i₁><=输入。长度-1；i_{N-1_{++）
产生｛input[i₀]，input[i₁】，input[i<1₂]..，input[i<2_N-1]]}}}}}}

如果是9个元素（或最大25-30个）和5个子集的可处理集合，则代码可以基于递归函数

   static void Main(string[] args)
    {
        foreach (var item in ListPerm())
        {
            Console.WriteLine(String.Join(",", item));
        }
        Console.Read();
    }

    private static List<List<int>> ListPerm(HashSet<int> mySet = null, int deep = 5)
    {
        if (mySet == null)
        {
            mySet = initSet(8);
        }
        if (deep <= 0)
        {
            return Enumerable.Empty<List<int>>().ToList();
        }
        List<List<int>> all = new List<List<int>>();
        for (int i = 0; i < mySet.Count - deep + 1; i++)
        {
            if (deep == 1)
            {
                var list = new List<int>() { mySet.ElementAt(i) };
                all.Add(list);
            }
            foreach (var item in ListPerm(new HashSet<int>(mySet.Skip(i+1)), deep - 1))
            {
                var list = new List<int>() { mySet.ElementAt(i) };
                list.AddRange(item);
                all.Add(list);
            }
        }
        return all;
    }
    private static HashSet<int> initSet(int lenght)
    {
        HashSet<int> ret = new HashSet<int>();
        for (int i = 0; i < lenght; i++)
        {
            ret.Add(i * 1  +  1); // just an example...
        };
        return ret;
    }

再造

现在，让我将上面的代码优化为一个更具性能的函数，这需要3.2秒才能在我的标准笔记本电脑上获得30中的8个整数的组合。

private static int[][] ListPerm(int[] mySet, int deep)
{
    var all = new List<int[]>();
    if (deep == 1)
    {
        return mySet.Select(x => new int[] { x }).ToArray(); 
    }
    else
    {
        var mySubSet = new int[mySet.Length - 1];
        Array.Copy(mySet, 1, mySubSet, 0, mySubSet.Length);
        var perm1st = ListPerm(mySubSet, deep - 1);
        for (int i = 0; i < mySet.Length - deep + 1; i++)
        {
            var permn = perm1st.Select(x =>
                {
                    var z = new int[x.Length + 1];
                    z[0] = mySet[i];
                    x.CopyTo(z, 1);
                    return z;
                }
            );
            all.AddRange(permn);
            int start = Array.FindIndex(perm1st, item => item[0] != mySet[i + 1]);
                if (start > 0)
                {
                    var temp_cpy = new int[perm1st.Length - start][];
                    Array.Copy(perm1st, start, temp_cpy, 0, temp_cpy.Length);
                    perm1st = temp_cpy;
                }
        }
    }
    return all.ToArray();
}

基准

这里是Ivan的、我的和社区wiki算法的比较，用于20中5个int的组合。

结果

wiki perm:00:00:00.0950055
撰写wiki perm:00:00:0.0460026
Ivan perm:00:00:00.0400023
写作Ivan perm:00:00:000260015
我的烫发时间：00:00:00.0110006
写我的烫发：00:00:00-0300017

测试代码

    var input = Enumerable.Range(1, 20);
    int deep = 5;
    var start = DateTime.Now;

    var wiki =  Algorithms.Combinations(input, deep).ToArray();
    Console.WriteLine("wiki perm: {0}", DateTime.Now - start);
    start = DateTime.Now;
    StreamWriter sw0 = new StreamWriter(@"C:devSOAlgoperm0.txt", false);
    foreach (var item in wiki)
    {
        sw0.WriteLine(String.Join(",", item));
    }
    sw0.Close();
    Console.WriteLine("writing wiki perm: {0}", DateTime.Now - start);
    start = DateTime.Now;
    start = DateTime.Now;
    var result = input
        .Distinct()
        .ToArray()
        .GetCombinations(deep)
        .Select(c => (int[])c.Clone())
        .ToList();
    Console.WriteLine("Ivan perm: {0}", DateTime.Now - start);
    start = DateTime.Now;
    StreamWriter sw1 = new StreamWriter(@"C:devSOAlgoperm1.txt", false);
    foreach (var item in result)
    {
        sw1.WriteLine(String.Join(",", item));
    }
    sw1.Close();
    Console.WriteLine("writing Ivan perm: {0}", DateTime.Now - start);
    start = DateTime.Now;

    var myPerm = ListPermSO(input.ToArray(), deep);
    Console.WriteLine("my perm: {0}", DateTime.Now - start);
    start = DateTime.Now;
    StreamWriter sw2 = new StreamWriter(@"C:devSOAlgoperm2.txt", false);
    foreach (var item in myPerm)
    {
        sw2.WriteLine(String.Join(",", item));
    }
    sw2.Close();
    Console.WriteLine("writing my perm: {0}", DateTime.Now - start);
    Console.Read();

再造

基准

相关内容

最新更新

热门标签：