与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运行

remaining在Chain.Start中的筛选似乎不起作用。

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

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

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

编辑:添加更多信息

Answer 1

问题是Select的枚举不是立即执行的，而是延迟执行的。这意味着每次访问/使用由IEnumerable<>方法返回的Select()时，都会得到一个新的列表。但这也意味着您一直在创建新的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)

正如您所看到的，构造函数通常被称为()。每次有人从IEnumerable调用中使用Select()时，它都会再次生成可枚举列表，这样就不会干扰对相同数据的其他并行运行迭代。但是，由于在Select()语句中创建了新对象，因此每次创建IEnumerable of Select()都会获得新的对象。

正如您已经注意到的，要解决这个问题，您可以使用类似ToList()的工具，并计算/创建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)

您可以看到，只创建了两个对象，并且!=将按预期工作，因为只有这两个对象。