.net - .NET - 使用附加规则和曲折计算组合

Question

更新：@bphelpsjr 答案提供了我正在寻找的内容。不幸的是，有人对他投了反对票，而我没有代表支持。我将他的回答标记为答案。

这是非常冗长的，但我想提供尽可能多的细节。

本质上，我想获取一组数据并根据规则（定义如下）生成列表列表。这本质上是 powerset 的过滤版本。

然后我将存储这些结果以供重复使用（类似于彩虹表）以避免不断计算相同的结果N。然后我将在应用其他逻辑之前使用变量替换（例如，A = 18，B = 30）（下面没有描述，我的问题不是必需的）。

这是我在尝试创建解决方案时尝试过的两个输入选项。您也可以使用数字代替字母。

输入选项#1

var completeList = new List<Item>
        {
            new Item('A', 'A'),
            new Item('A', 'B'),
            new Item('A', 'C'),
            new Item('A', 'D'),            
            new Item('B', 'B'),
            new Item('B', 'C'),
            new Item('B', 'D'),           
            new Item('C', 'C'),
            new Item('C', 'D'),            
            new Item('D', 'D')
        };

输入选项 #2

List<Item> aList = new List<Item> 
{
        new Item('A', 'A'),
        new Item('A', 'B'),
        new Item('A', 'C'),
        new Item('A', 'D'),            
    };

    List<Item> bList = new List<Item> 
    {
        new Item('B', 'B'),
        new Item('B', 'C'),
        new Item('B', 'D'),           
    };

    List<Item> cList = new List<Item> 
    {
        new Item('C', 'C'),
        new Item('C', 'D'),            
    };

    List<Item> dList = new List<Item> 
    {
        new Item('D', 'D')
    };

期望的输出

AA BB CC DD
AA BB CD
AA BC    DD
AA BD CC
AB    CC DD 
AB    CD
AC BB    DD
AC BD
AD BB CC
AD BC

规则

前 3 条是明确的规则，而第 4 条则更多是一种愿望。

解决方案必须能够处理N个不同的字母和项目列表

每个不同的字母必须在项目列表中至少出现一次。例子：

AA BB CC DD <-- 有效

AA BB CC <-- 无效，不包含 D

字母只能在给定项目内重复。例子：

AA BB CC DD <-- 有效

AA BA CC DD <-- 无效，A 在不同项目中重复

逻辑必须包含尽可能多的“积极过滤”和短路，以减少它将执行的迭代次数。我有一个可行的左移解决方案，但由于（我的？）无法合并过滤和短路，它无法扩展。这基本上导致了对整个 powerset 的迭代。

示例：一旦找到已包含在潜在列表项中的字母，请继续下一个可能的组合，因为该组合无效。

示例：一旦找到有效的项目列表，就开始下一轮。

接下来的两个是基于我目前将数据集按每个项目的第一个字母分组的方式的潜在示例。根据您创建的解决方案类型，它们可能不适用。

潜在示例：如果某个项目包含位于下一个列表项目中的字母，则跳过整个列表并移至下一个项目列表。

AA BC DD <-- 我们可以跳过 C 列表，因为它被 BC 覆盖

潜在示例：一旦您用尽了列表的潜在候选人（例如，最后一个列表将只有 1 个项目），您不应该（如果我的想法是正确的）再次需要该列表，直到它上面的列表 + 1 更改了项目.

AA BB CC DD <-- 找到这个之后，停止搜索包含 DD 的列表，直到到达 BC（DD + 1 上方的列表）

AA BB光盘

AA BC DD <-- 我们又需要 DD

无论项目的顺序如何，任何项目列表都不应重复。例子：

AA BB CC DD == BB AA DD CC 所以不包括 BB AA DD CC

我所做的假设：

通过它们的初始起始字母对集合进行分组会更容易（参见下面的示例数据）。如果这不是最佳方法，那也不是问题。

下面是我用来保存数据的 Item 类，只是为了方便：

public class Item
{
    public char First { get; set; }
    public char Second { get; set; }

    public Item(char first, char second)
    {
        First = first;
        Second = second;

    public List<char> DistinctCharacters()
    {
        return First == Second ? new List<char> { First } : new List<char> { First,  Second };
    }
}

score 1 · Accepted Answer

这应该有效（使用数字而不是字母）：

    private static BlockingCollection<List<int[]>> GetCombinations(int toConsider)
    {
        var allResults = new BlockingCollection<List<int[]>>();
        var possibilities = Enumerable.Range(0, toConsider).ToList();
        Parallel.ForEach(possibilities, possibility =>
        {
            GetIteratively(new List<int[]> { new[] { 0, possibility } }, allResults, possibilities.RemoveAllClone(x => x == 0 || x == possibility));
        });
        return allResults;
    }
    public static void GetIteratively(List<int[]> result, BlockingCollection<List<int[]>> allResults, List<int> possibilities)
    {
        Stack<Tuple<List<int[]>, List<int>>> stack = new Stack<Tuple<List<int[]>, List<int>>>();
        stack.Push(new Tuple<List<int[]>,List<int>>(result, possibilities));
        while (stack.Count > 0)
        {
            var pop = stack.Pop();
            if (pop.Item2.Count > 0)
                pop.Item2.ForEach(x => stack.Push(new Tuple<List<int[]>, List<int>>(new List<int[]>(result) { new int[] { pop.Item2[0], x } }, pop.Item2.RemoveAllClone(y => (y == pop.Item2[0] || y == x)))));
            else
                allResults.Add(result);
        }   
    }

这是 RemoveAllClone 的 LinqExtension

    public static List<T> RemoveAllClone<T>(this IEnumerable<T> source, Predicate<T> match)
    {
        var clone = new List<T>(source);
        clone.RemoveAll(match);
        return clone;
    }

score 0 · Accepted Answer

我没有足够的代表发表评论，所以我发布了一个不完整的答案。我有一个解决方案，但还没有完善它。它目前会吐出不完整的组合（例如 AD CC），并且可以使用一些修剪来避免查看无用的列表。

我的方法是递归的，但通过存储解决方案来避免一些计算。例如，在查看 C 列表时，使用 A 和 B 字母后剩下的组合，无论目前的组合是 AA BB 还是 AB，都是相同的。

我还没有实现Memorize()andIKnowThis()方法，但是使用哈希表应该很简单。

foreach (var combo in GenerateCombinations("", 0))   
{
    Console.WriteLine(combo);
}

private static List<string> GenerateCombinations(string used, int listIndex)
    {
        if (listIndex >= _allLists.Count || used.Length == _allLists.Count)
            return new List<string>();

        List<string> combos;

        if (!IKnowThis(used, listIndex, out combos))
        {
            if (used.Contains(_allLists[listIndex][0].First))
                return GenerateCombinations(used, listIndex + 1);

            combos = new List<string>();

            foreach (var item in _allLists[listIndex])
            {
                var newcombos = new List<string>();



                string newUsed = Combine(used, item);
                newcombos.AddRange(GenerateCombinations(newUsed, listIndex + 1));

                if (!used.Contains(item.Second) && !used.Contains(item.First))
                {
                    if (newcombos.Count == 0)
                    {
                        newcombos.Add(item.ToString());
                    }
                    else
                    {
                        for (int i = 0; i < newcombos.Count; i++)
                        {
                            newcombos[i] = item + " " + newcombos[i];
                        }
                    }
                }

                combos.AddRange(newcombos);
            }
        }

        Memorize(used, combos);
        return combos;
    }

    private static string Combine(string used, Item item)
    {
        if (!used.Contains(item.First))
            used += item.First;
        if (!used.Contains(item.Second))
            used += item.Second;

        return used;
    }        
}

public class Item
{
    public char First { get; set; }
    public char Second { get; set; }

    public Item(char first, char second)
    {
        First = first;
        Second = second;
    }
    public string DistinctCharacters()
    {
        return First == Second ? First.ToString() : this.ToString();
    }

    public override string ToString()
    {
        return First.ToString() + Second;
    }
}

score 0 · Accepted Answer

这是否可以为您提供您想要的东西？

如果我从您的completeList加号开始，则缺少向后过渡：

var completeList = new List<Item>
{
    new Item('A', 'A'),
    new Item('A', 'B'),
    new Item('A', 'C'),
    new Item('A', 'D'),
    new Item('B', 'B'),
    new Item('B', 'C'),
    new Item('B', 'D'),
    new Item('C', 'B'),
    new Item('C', 'C'),
    new Item('C', 'D'),
    new Item('D', 'B'),
    new Item('D', 'C'),
    new Item('D', 'D'),
};

然后我可以这样做：

var lookup = completeList.ToLookup(x => x.First, x => x.Second);

Func<IEnumerable<string>, IEnumerable<string>> f = null;
f = xs =>
{
    var query =
        from x in xs
        let ys = lookup[x.Last()]
            .Where(y => !x
                .Take(x.Length % 2 == 1 ? x.Length - 1 : x.Length)
                .Contains(y))
            .Select(y => x + y)
            .ToArray()
        group new { x, ys } by ys.Any();

    return query
        .Where(c => c.Key == false)
        .SelectMany(qs => qs.Select(q => q.x))
        .Concat(query
            .Where(c => c.Key == true)
            .SelectMany(ys => Generate(ys.SelectMany(y => y.ys))));
};

var results = f(new [] { "A" });

我得到这些结果：

ABCD 
ABDC 
ACBD 
ACDB 
ADBC 
ADCB 
AABBCD 
AABBDC 
AABCDD 
AABDCC 
AACBDD 
AACCBD 
AACCDB 
AACDBB 
AADBCC 
AADCBB 
AADDBC 
AADDCB 
ABCCDD 
ABDDCC 
ACBBDD 
ACDDBB 
ADBBCC 
ADCCBB 
AABBCCDD 
AABBDDCC 
AACCBBDD 
AACCDDBB 
AADDBBCC 
AADDCCBB

.net - .NET - 使用附加规则和曲折计算组合

输入选项#1

输入选项 #2

期望的输出

规则

3 回答 3

Related

Reference