2

这不是一个问题，我觉得我有正确表达的词汇，但我有两个相同匿名类型的集合（让我们称之为'a。）

'a 定义为new {string Name, int Count}

我们称之为需求的这些集合之一。我们称之为候选者的这些集合之一。

鉴于这些集合，我想确定以下断言是否成立。

  1. 如果需求r中存在某个元素使得r.Count == 0，那么候选c中的每个元素都r.Name == c.Name必须满足c.Count == 0。对于需求中的每个此类元素，候选者中必须存在一个此类元素。

  2. 对于需求r的每个元素where ，候选cr.Count > 0中必须有一些元素的子集，例如 that和 that 。对于需求中的某些元素，用于满足此规则的候选元素的每个元素可能不会用于需求中的另一个元素。c₁.Name, c₂.Name, ..., cₓ.Name == r.Namec₁ + ... + cₓ >= r.Count

这方面的一个例子是给定的

requirements = {{"A",0}, {"B", 0}, {"C", 9}}
candidates = {{"B", 0},  {"C", 1}, {"A",0}, {"D", 2}, {"C", 4}, {"C", 4}}

这个查询会得到满足。

r={"A", 0}并且r={"B", 0}会根据规则 #1 满足c={"A", 0}和c={"B", 0}

-和-

r={"C", 9)根据规则 #2 由组gcc.Name对源自{{"C", 1}, {"C", 4}, {"C", 4}}as的集合满足gc = {"C", 9}

然而值得注意的是，如果需求包含{"C", 6}and{"C", 3}而不是{"C", 9}，则这组特定的集合将无法满足谓词。

现在终于到了这个问题。 将其形成为优先考虑速度（最少迭代）的 linq 表达式的最佳方法是什么？

未解决的子集已在此处重新询问

4

6 回答 6

1
于 2013-05-24T05:47:25.617 回答
1

这是我的 linqy 解决方案草图，但它根本没有解决 #3。它通过分组和加入名称来工作。然后，困难的部分将是确定是否存在满足该组的候选人的某些匹配要求。

void Main() {
    var requirements = new [] {
        new NameCount{ Name = "A", Count = 0 },
        new NameCount{ Name = "B", Count = 0 },
        new NameCount{ Name = "C", Count = 9 },
        new NameCount{ Name = "D", Count = 3 },
        new NameCount{ Name = "D", Count = 5 },
    };

    var candidates = new[] {
        new NameCount {Name = "B", Count = 0},
        new NameCount {Name = "C", Count = 1},
        new NameCount {Name = "A", Count = 0}, 
        new NameCount {Name = "D", Count = 2},
        new NameCount {Name = "C", Count = 4},
        new NameCount {Name = "C", Count = 4}
    };

    var matched = requirements
        .GroupBy(r => r.Name)
        .GroupJoin(candidates, rg => rg.Key, c => c.Name, 
            (rg, cg) => new { requirements = rg, candidates = cg });

    bool satisfied = matched.All( /* ??? */ );
}

struct NameCount {
    public string Name;
    public int Count;
}

对于给定的输入，匹配的将是： 在此处输入图像描述

.GroupJoin具有比candidates.Where投影更好的性能特征。

于 2013-05-23T23:13:04.183 回答
0

将在此处发布明显的答案，但我正在寻找更优雅的东西。

给定候选者为 IEnumerable<'a>，通过调用 Candidates.Where(c=>c.Count != 0).GroupBy(...) 对所有元素执行求和，从候选者中投射 IEnumerable<'a> groupedCandidates一样的名字。

然后从 Candidates.Except(groupedCandidates, (c,gc)=>c.Name == gc.Name) 中投影 simpleCandidates

过去这里变得模糊，因为候选人可能只满足一次要求。

于 2013-05-22T23:44:02.583 回答
0

我终于想出了一个可行的解决方案

        IEnumerable<Glyph> requirements = t.Objectives.Cast<Glyph>().OrderBy(k => k.Name);
        IEnumerable<Glyph> candidates = Resources.Cast<Glyph>().OrderBy(k => k.Name);

        IEnumerable<Glyph> zeroCountCandidates = candidates.Where(c => c.Count == 0);
        IEnumerable<Glyph> zeroCountRequirements = requirements.Where(r => r.Count == 0);

        List<Glyph> remainingCandidates = zeroCountCandidates.ToList();

        if (zeroCountCandidates.Count() < zeroCountRequirements.Count())
        {
            return false;
        }

        foreach (var r in zeroCountRequirements)
        {
            if (!remainingCandidates.Contains(r))
            {
                return false;
            }
            else
            {
                remainingCandidates.Remove(r);
            }
        }

        IEnumerable<Glyph> nonZeroCountCandidates = candidates.Where(c => c.Count > 0);
        IEnumerable<Glyph> nonZeroCountRequirements = requirements.Where(r => r.Count > 0);

        var perms = nonZeroCountCandidates.Permutations();

        foreach (var perm in perms)
        {
            bool isViableSolution = true;

            remainingCandidates = perm.ToList();

            foreach (var requirement in nonZeroCountRequirements)
            {
                int countThreshold = requirement.Count;
                while (countThreshold > 0)
                {
                    if (remainingCandidates.Count() == 0)
                    {
                        isViableSolution = false;
                        break;
                    }

                    var c = remainingCandidates[0];
                    countThreshold -= c.Count;

                    remainingCandidates.Remove(c);
                }
            }

            if (isViableSolution)
            {
                return true;
            }
        }

        return false;

是不是很恶心？

于 2013-05-31T20:54:30.370 回答
0

算法：

if any requirement Name doesn't exist in the candidates, return false
for any requirement having Count = 0
    if there aren't at least as many candidates 
       with the same Name and Count, return false
eliminate all exact matches between candidates and requirements
eliminate requirements (and candidates) where the requirement 
    and all higher requirements have a higher candidate available
for remaining non-zero requirements
    find the subset of candidates
    that matches the most requirements
       and eliminate the requirements (and candidates)
if there are any remaining non-zero requirements
    return false
return true because no unmatched requirements remain

示例实现：

public static bool IsValid(IEnumerable<string> requirementNames,
                           IList<int> requirementCounts,
                           IEnumerable<string> candidateNames,
                           IList<int> candidateCounts)
{
    var requirements = requirementNames
        .Select((x, i) => new
          {
              Name = x,
              Count = requirementCounts[i]
          })
        .ToList();
    var candidates = candidateNames
        .Select((x, i) => new
          {
              Name = x,
              Count = candidateCounts[i]
          })
        .ToList();

    var zeroRequirements = requirements
        .Where(x => x.Count == 0)
        .Select(x => x.Name)
        .GroupBy(x => x)
        .ToDictionary(x => x.Key, x => x.Count());
    var zeroCandidates = candidates
        .Where(x => x.Count == 0)
        .Select(x => x.Name)
        .GroupBy(x => x)
        .ToDictionary(x => x.Key, x => x.Count());
    if (zeroRequirements.Keys.Any(x => !zeroCandidates.ContainsKey(x) ||
                                       zeroCandidates[x] < zeroRequirements[x]))
    {
        return false;
    }

    var nonZeroRequirements = requirements
        .Where(x => x.Count != 0)
        .GroupBy(x => x.Name)
        .ToDictionary(x => x.Key,
                      x => x.Select(y => y.Count)
                               .GroupBy(y => y)
                               .ToDictionary(y => y.Key, y => y.Count()));
    var nonZeroCandidates = candidates
        .Where(x => x.Count != 0)
        .GroupBy(x => x.Name)
        .ToDictionary(x => x.Key,
                      x => x.Select(y => y.Count)
                               .GroupBy(y => y)
                               .ToDictionary(y => y.Key, y => y.Count()));

    foreach (var name in nonZeroRequirements.Keys.ToList())
    {
        var requirementsForName = nonZeroRequirements[name];
        Dictionary<int, int> candidatesForName;
        if (!nonZeroCandidates.TryGetValue(name, out candidatesForName))
        {
            return false;
        }
        if (candidatesForName.Sum(x => x.Value) <
            requirementsForName.Sum(x => x.Value))
        {
            return false;
        }
        if (candidatesForName.Sum(x => x.Value*x.Key) <
            requirementsForName.Sum(x => x.Value*x.Key))
        {
            return false;
        }

        EliminateExactMatches(candidatesForName, requirementsForName);
        EliminateHighRequirementsWithAvailableHigherCandidate(candidatesForName, requirementsForName);
        EliminateRequirementsThatHaveAMatchingCandidateSum(candidatesForName, requirementsForName);

        if (requirementsForName
            .Any(x => x.Value > 0))
        {
            return false;
        }
    }

    return true;
}

private static void EliminateRequirementsThatHaveAMatchingCandidateSum(
    IDictionary<int, int> candidatesForName,
    IDictionary<int, int> requirementsForName)
{
    var requirements = requirementsForName
        .Where(x => x.Value > 0)
        .OrderByDescending(x => x.Key)
        .SelectMany(x => Enumerable.Repeat(x.Key, x.Value))
        .ToList();
    if (!requirements.Any())
    {
        return;
    }

    // requirements -> candidates used
    var items = GenerateCandidateSetsThatSumToOrOverflow(
        requirements.First(),
        candidatesForName,
        new List<int>())
        .Concat(new[] {new KeyValuePair<int, IList<int>>(0, new List<int>())})
        .Select(x => new KeyValuePair<IList<int>, IList<int>>(
                         new[] {x.Key}, x.Value));

    foreach (var count in requirements.Skip(1))
    {
        var count1 = count;
        items = (from i in items
                 from o in GenerateCandidateSetsThatSumToOrOverflow(
                     count1,
                     candidatesForName,
                     i.Value)
                 select
                     new KeyValuePair<IList<int>, IList<int>>(
                     i.Key.Concat(new[] {o.Key}).OrderBy(x => x).ToList(),
                     i.Value.Concat(o.Value).OrderBy(x => x).ToList()))
            .GroupBy(
                x => String.Join(",", x.Key.Select(y => y.ToString()).ToArray()) + ">"
                     + String.Join(",", x.Value.Select(y => y.ToString()).ToArray()))
            .Select(x => x.First());
    }

    var bestSet = items
        .OrderByDescending(x => x.Key.Count(y => y > 0)) // match the most requirements
        .ThenByDescending(x => x.Value.Count) // use the most candidates
        .ToList();
    var best = bestSet.First();

    foreach (var requirementCount in best.Key.Where(x => x > 0))
    {
        requirementsForName[requirementCount] -= 1;
    }

    foreach (var candidateCount in best.Value.Where(x => x > 0))
    {
        candidatesForName[candidateCount] -= 1;
    }
}

private static void EliminateHighRequirementsWithAvailableHigherCandidate(
    IDictionary<int, int> candidatesForName,
    IDictionary<int, int> requirementsForName)
{
    foreach (var count in requirementsForName
        .Where(x => x.Value > 0)
        .OrderByDescending(x => x.Key)
        .Select(x => x.Key)
        .ToList())
    {
        while (requirementsForName[count] > 0)
        {
            var count1 = count;
            var largerCandidates = candidatesForName
                .Where(x => x.Key > count1)
                .OrderByDescending(x => x.Key)
                .ToList();
            if (!largerCandidates.Any())
            {
                return;
            }

            var largerCount = largerCandidates.First().Key;
            requirementsForName[count] -= 1;
            candidatesForName[largerCount] -= 1;
        }
    }
}

private static void EliminateExactMatches(
    IDictionary<int, int> candidatesForName,
    IDictionary<int, int> requirementsForName)
{
    foreach (var count in requirementsForName.Keys.ToList())
    {
        int numberOfCount;
        if (candidatesForName.TryGetValue(count, out numberOfCount) &&
            numberOfCount > 0)
        {
            var toRemove = Math.Min(numberOfCount, requirementsForName[count]);
            requirementsForName[count] -= toRemove;
            candidatesForName[count] -= toRemove;
        }
    }
}

private static IEnumerable<KeyValuePair<int, IList<int>>> GenerateCandidateSetsThatSumToOrOverflow(
    int sumNeeded,
    IEnumerable<KeyValuePair<int, int>> candidates,
    IEnumerable<int> usedCandidates)
{
    var usedCandidateLookup = usedCandidates
        .GroupBy(x => x)
        .ToDictionary(x => x.Key, x => x.Count());
    var countToIndex = candidates
        .Select(x => Enumerable.Range(
            0,
            usedCandidateLookup.ContainsKey(x.Key)
                ? x.Value - usedCandidateLookup[x.Key]
                : x.Value)
                         .Select(i => new KeyValuePair<int, int>(x.Key, i)))
        .SelectMany(x => x)
        .ToList();

    // sum to List of <count,index>
    var sumToElements = countToIndex
        .Select(a => new KeyValuePair<int, IList<KeyValuePair<int, int>>>(
                         a.Key, new[] {a}))
        .ToList();

    countToIndex = countToIndex.Where(x => x.Key < sumNeeded).ToList();

    while (sumToElements.Any())
    {
        foreach (var set in sumToElements
            .Where(x => x.Key >= sumNeeded))
        {
            yield return new KeyValuePair<int, IList<int>>(
                sumNeeded,
                set.Value.Select(x => x.Key).ToList());
        }

        sumToElements = (from a in sumToElements.Where(x => x.Key < sumNeeded)
                         from b in countToIndex
                         where !a.Value.Any(x => x.Key == b.Key && x.Value == b.Value)
                         select new KeyValuePair<int, IList<KeyValuePair<int, int>>>(
                             a.Key + b.Key,
                             a.Value.Concat(new[] {b})
                                 .OrderBy(x => x.Key)
                                 .ThenBy(x => x.Value)
                                 .ToList()))
            .GroupBy(x => String.Join(",", x.Value.Select(y => y.Key.ToString()).ToArray()))
            .Select(x => x.First())
            .ToList();
    }
}


private static IEnumerable<int> GetAddendsFor(int sum, Random random)
{
    var values = new List<int>();
    while (sum > 0)
    {
        var addend = random.Next(1, sum);
        sum -= addend;
        values.Add(addend);
    }
    return values;
}

测试：

[Test]
public void ABCC_0063__with_candidates__BCADCC_010244__should_return_false()
{
    var requirementNames = "ABCC".Select(x => x.ToString()).ToArray();
    var requirementCounts = new[] {0, 0, 6, 3};

    var candidateNames = "BCADCC".Select(x => x.ToString()).ToArray();
    var candidateCounts = new[] {0, 1, 0, 2, 4, 4};

    var actual = IsValid(requirementNames, requirementCounts, candidateNames, candidateCounts);
    actual.ShouldBeFalse();
}

[Test]
public void ABC_003__with_candidates__BCADCC_010244__should_return_true()
{
    var requirementNames = "ABC".Select(x => x.ToString()).ToArray();
    var requirementCounts = new[] {0, 0, 3};

    var candidateNames = "BCADCC".Select(x => x.ToString()).ToArray();
    var candidateCounts = new[] {0, 1, 0, 2, 4, 4};

    var actual = IsValid(requirementNames, requirementCounts, candidateNames, candidateCounts);
    actual.ShouldBeTrue();
}

[Test]
public void ABC_003__with_candidates__BCAD_0102__should_return_false()
{
    var requirementNames = "ABC".Select(x => x.ToString()).ToArray();
    var requirementCounts = new[] {0, 0, 3};

    var candidateNames = "BCAD".Select(x => x.ToString()).ToArray();
    var candidateCounts = new[] {0, 1, 0, 2};

    var actual = IsValid(requirementNames, requirementCounts, candidateNames, candidateCounts);
    actual.ShouldBeFalse();
}

[Test]
public void ABC_009__with_candidates__BCADCC_010244__should_return_true()
{
    var requirementNames = "ABC".Select(x => x.ToString()).ToArray();
    var requirementCounts = new[] {0, 0, 9};

    var candidateNames = "BCADCC".Select(x => x.ToString()).ToArray();
    var candidateCounts = new[] {0, 1, 0, 2, 4, 4};

    var actual = IsValid(requirementNames, requirementCounts, candidateNames, candidateCounts);
    actual.ShouldBeTrue();
}

[Test]
public void FuzzTestIt()
{
    var random = new Random();
    const string names = "ABCDE";

    for (var tries = 0; tries < 10000000; tries++)
    {
        var numberOfRequirements = random.Next(5);
        var shouldPass = true;
        var requirementNames = new List<string>();
        var requirementCounts = new List<int>();
        var candidateNames = new List<string>();
        var candidateCounts = new List<int>();
        for (var i = 0; i < numberOfRequirements; i++)
        {
            var name = names.Substring(random.Next(names.Length), 1);
            switch (random.Next(6))
            {
                case 0: // zero-requirement with corresponding candidate
                    requirementNames.Add(name);
                    requirementCounts.Add(0);
                    candidateNames.Add(name);
                    candidateCounts.Add(0);
                    break;
                case 1: // zero-requirement without corresponding candidate
                    requirementNames.Add(name);
                    requirementCounts.Add(0);
                    shouldPass = false;
                    break;
                case 2: // non-zero-requirement with corresponding candidate
                    {
                        var count = random.Next(1, 10);
                        requirementNames.Add(name);
                        requirementCounts.Add(count);
                        candidateNames.Add(name);
                        candidateCounts.Add(count);
                    }
                    break;
                case 3: // non-zero-requirement with matching sum of candidates
                    {
                        var count = random.Next(1, 10);
                        requirementNames.Add(name);
                        requirementCounts.Add(count);
                        foreach (var value in GetAddendsFor(count, random))
                        {
                            candidateNames.Add(name);
                            candidateCounts.Add(value);
                        }
                    }
                    break;
                case 4: // non-zero-requirement with matching overflow candidate
                    {
                        var count = random.Next(1, 10);
                        requirementNames.Add(name);
                        requirementCounts.Add(count);
                        candidateNames.Add(name);
                        candidateCounts.Add(count + 2);
                    }
                    break;
                case 5: // non-zero-requirement without matching candidate or sum or candidates
                    {
                        var count = random.Next(10, 20);
                        requirementNames.Add(name);
                        requirementCounts.Add(count);
                        shouldPass = false;
                    }
                    break;
            }
        }

        try
        {
            var actual = IsValid(requirementNames, requirementCounts, candidateNames, candidateCounts);
            actual.ShouldBeEqualTo(shouldPass);
        }
        catch (Exception e)
        {
            Console.WriteLine("Requirements: " + String.Join(", ", requirementNames.ToArray()));
            Console.WriteLine("              " +
                              String.Join(", ", requirementCounts.Select(x => x.ToString()).ToArray()));
            Console.WriteLine("Candidates:   " + String.Join(", ", candidateNames.ToArray()));
            Console.WriteLine("              " +
                              String.Join(", ", candidateCounts.Select(x => x.ToString()).ToArray()));
            Console.WriteLine(e);
            Assert.Fail();
        }
    }
}
于 2013-05-30T23:35:20.620 回答
0

编辑：此解决方案不符合修订后的要求。

我不熟悉 LINQ，但看起来你可以在 O(n) 中解决这个问题，除非我误解了一些东西。完成这个问题需要三个步骤。

首先，构造一个列表或哈希表counter并通过迭代来填充它c。如果我们使用哈希表，哈希表的大小将是长度，c因此我们不必调整哈希表的大小。

for candidate in c:
    counter[candidate.name] += candidate.count

我们一次性完成。O(m) 其中 m 是 c 的长度。

通过counter构造，我们通过迭代来构造一个哈希表r。

for requirement in r:
    if not h[requirement.name] or not requirement.count >= h[requirement.name]:
        h[requirement.name] = requirement.count

然后，我们简单地遍历counter并比较计数。

for sum in counter:
    assert h[sum.name] and h[sum.name] >= sum.count

我们一次性完成：O(p) 其中 p 是计数器的长度。

如果这个算法成功终止，我们的约束就满足了，我们已经在 O(m) + O(o) + O(p) 中完成了它

于 2013-05-23T20:10:03.097 回答