有多少种不同的方法可以从大小为n但没有重复的数组中选择K个元素

Question

基本上，我想知道如何从n个的数组中选择k来删除重复项

这是我的代码，它显示了所有可能的组合，例如32、32、33、22、23、23的重复：

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Techniques
{
public static class Program
{
    private static void Main()
    {
        int[] data = { 3, 2, 2, 3 };
        int k = 2;
        foreach (string comb in CombinationsOfK(data, k).Select(c => string.Join(" ", c)))
        {
            Console.WriteLine(comb);
        }
    }
    public static IEnumerable<IEnumerable<T>> CombinationsOfK<T>(T[] data, int k)
    {
        int size = data.Length;
        IEnumerable<IEnumerable<T>> Runner(IEnumerable<T> list, int n)
        {
            int skip = 1;
            foreach (var headList in list.Take(size - k + 1).Select(h => new T[] { h }))
            {
                if (n == 1 )
                    yield return headList;
                else
                {
                    foreach (var tailList in Runner(list.Skip(skip), n - 1))
                    {
                        
                       
                            yield return headList.Concat(tailList);
                        
                    }
                    skip++;
                }
            }
        }
        return Runner(data, k);
    }
}
}

我想知道如何从我得到的组合中删除重复项，例如23、22、33没有两个组合应该是相同的。

Answer 1

我的建议，对于问答；D解决方案：

你有这个代码，打印出组合：

foreach (string comb in CombinationsOfK(data, k).Select(c => string.Join(" ", c)))
{
    Console.WriteLine(comb);
}

本条款的最终结果：

CombinationsOfK(data, k).Select(c => string.Join(" ", c))

将是CCD_ 1。您可以将Distinct应用于此，字符串将根据其作为字符串的值进行稀疏处理。

因此：

var combStrings = CombinationsOfK(data, k).Select(c => string.Join(" ", c));
foreach (var comb in combStrings.Distinct())
{
    Console.WriteLine(comb);
}

不过，免责声明是：我在内存中执行此操作，无法测试这台机器上的代码。

此外：如果这是一项课程作业，并且作业的一部分是为了防止重复，你的老师可能会认为这是一个无效的解决方案，因为它利用了字符串处理的一个特点，而不是改进你的算法。

ETA：使用缓存(HashSet<T>(的答案：

您将不得不对代码进行一定程度的重组，或者在多个位置(在每个yield之前(对缓存进行检查。

基本上，每次您知道想要yield的值时，请将其与缓存进行比较。

在某处定义缓存(可能在定义size之后(：

var cache = HashSet<string>();

您将在缓存中使用字符串，因为涉及它们的比较使用基于值的比较。早些时候，当我认为int[]也是如此时，我错了。

然后，无论你在哪里有yield return，都用这个包裹：

var cacheValue = <whatever you were going to return>.Select(c => string.Join(" ", c));
if(!cache.Contains(cacheValue))
{
   cache.Add(cacheValue);
   yield return <whatever you were going to return>;
}