IEnumerable、Where 和 Object.ReferenceEquals 问题

Question

正在尝试解决运动问题（多米诺骨牌）。在这个问题中，我试图创建一个有效的多米诺骨牌链，使得数字相互接触并且第一个和最后一个数字相同。

示例：[1|2], [3,1], [3,2] -> [1|2][2|3][3|1]

我正在使用蛮力尝试所有组合。为此，我使用以下代码启动包含所有可能组合的链：

using System;
using System.Collections.Generic;
using System.Linq;

public static class Dominoes
{
    private class Domino
    {
        public readonly int First;
        public readonly int Last;

        public Domino(int first, int last)
        {
            First = first;
            Last = last;
        }

        public Domino Flip() => new Domino(Last, First);
    }

    private class Chain
    {
        private readonly List<Domino> chained = new List<Domino>();

        private readonly List<Domino> remaining = new List<Domino>();

        private int First => chained[0].First;

        private int Last => chained[chained.Count - 1].Last;

        public bool Complete => remaining.Count == 0 && First == Last;

        private Chain(Domino domino, IEnumerable<Domino> remaining, IEnumerable<Domino> chained = null)
        {
            if (chained != null)
            {
                this.chained.AddRange(chained);
            }

            this.chained.Add(domino);

            this.remaining.AddRange(remaining);
        }

        public static IEnumerable<Chain> Start(IEnumerable<Domino> dominoes)
        {
            var chains = new List<Chain>();

            foreach (var domino in dominoes)
            {
                var remaining = dominoes.Where(d => d != domino);

                chains.Add(new Chain(domino, remaining));
                chains.Add(new Chain(domino.Flip(), remaining));
            }

            return chains;
        }

        public IEnumerable<Chain> Extend()
        {
            var chains = new List<Chain>();

            foreach (var domino in this.remaining)
            {
                var remaining = this.remaining.Where(d => d != domino);

                if (domino.First == Last)
                {
                    chains.Add(new Chain(domino, remaining, chained));
                }

                if (domino.Last == Last)
                {
                    chains.Add(new Chain(domino.Flip(), remaining, chained));
                }
            }

            return chains;
        }
    }

    public static bool CanChain(IEnumerable<(int, int)> dominoes)
    {
        var chains = Chain.Start(dominoes.Select(d => new Domino(d.Item1, d.Item2)));

        return chains.Any() ? Iterate(chains) : true;
    }

    private static bool Iterate(IEnumerable<Chain> chains)
    {
        var newChains = new List<Chain>();

        foreach (var chain in chains)
        {
            if (chain.Complete) return true;

            newChains.AddRange(chain.Extend());
        }

        if (newChains.Count == 0) return false;

        return Iterate(newChains);
    }
}

测试代码

using System;
using Xunit;

public class DominoesTests
{
    [Fact]
    public void Singleton_that_cant_be_chained()
    {
        var dominoes = new[] { (1, 2) };
        Assert.False(Dominoes.CanChain(dominoes));
    }
}

运行使用 dotnet test

Chain.Start 中 remaining 的过滤似乎不起作用。

示例（使用 new [] { (1, 2) } 作为 CanChain 的输入）

# Expected: `Chain: [1|2] Remaining:`
# Actual:   `Chain: [1|2] Remaining: [1|2]`

如果我在 CanChain 中的 dominoes.Select(d => new Domino(d)) 上调用 .ToList()，它就会开始工作。

编辑：添加了更多信息

Answer 1

问题是Select的枚举没有立即执行，而是延迟执行。这意味着每次您 accessing/using 由 Select() 方法返回的 IEnumerable<> 时，您将获得一个新的新列表。但这也意味着您一直在创建新的 Domino 对象。由于您没有覆盖 Equals() 方法，因此每个 Domino 对象都会不同，即使它们具有相同的值。

要显示问题，请检查以下代码：

private class Foobar {
    private readonly int value;

    public Foobar(int v) {
        Console.WriteLine("## CONSTRUCTOR ## Foobar object created with value: "+v);
        this.value = v;
    }

    public override string ToString() {
        return "Foobar("+this.value+")";
    }
}

public static void Main(string[] args) {
    int[] numbers = new [] { 1, 5};
    IEnumerable<Foobar> range = numbers.Select(i => new Foobar(i));

    Console.WriteLine(range.Count());
    foreach (Foobar entry in range) {
        Console.WriteLine("Build an enumerable without "+entry);
        IEnumerable<Foobar> remaining = range.Where(it => it != entry);
        Console.WriteLine("The length of the remaining: "+remaining.Count());
        foreach (Foobar remainingEntry in remaining) {
            Console.WriteLine("Entry of remaining: "+remainingEntry);
        }
    }
}

当你运行这段代码时你会得到以下输出：

## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
2
## CONSTRUCTOR ## Foobar object created with value: 1
Build an enumerable without Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
The length of the remaining: 2
## CONSTRUCTOR ## Foobar object created with value: 1
Entry of remaining: Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 5
Entry of remaining: Foobar(5)
## CONSTRUCTOR ## Foobar object created with value: 5
Build an enumerable without Foobar(5)
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
The length of the remaining: 2
## CONSTRUCTOR ## Foobar object created with value: 1
Entry of remaining: Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 5
Entry of remaining: Foobar(5)

如您所见，过于频繁地调用构造函数。每次有人使用 Select() 调用中的 IEnumerable 时，它将再次生成可枚举列表，因此它不会干扰同一数据上的其他并行运行ning 迭代。但是，由于您在 Select() 语句中创建了新对象，因此每次创建 Select() 的 IEnumerable 都会获得新对象。

正如您已经注意到的那样，要解决您使用 ToList() 之类的问题，并且 evaluate/create 一次 Domino 对象。使用一个 ToList() 调用输出更改如下：

## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
2
Build an enumerable without Foobar(1)
The length of the remaining: 1
Entry of remaining: Foobar(5)
Build an enumerable without Foobar(5)
The length of the remaining: 1
Entry of remaining: Foobar(1)

你看，只创建了两个对象，!= 将按预期工作，因为只有这两个对象。

IEnumerable、Where 和 Object.ReferenceEquals 问题

Issue with IEnumerable, Where, and Object.ReferenceEquals

c#

ienumerable

.net-core

.net-core-3.0