时间戳

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

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

问题描述

基本上我想知道如何从 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 没有两个组合应该是相同的。

标签： c#

解决方案

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

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

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

该子句的最终结果：

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

...将是一个IEnumerable<string>. 你可以应用Distinct它，字符串将根据它们作为字符串的值被细化。

所以：

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

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

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

ETA：使用缓存（a 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>;
}

推荐阅读