logo标签列表

计算n个集合的连接集合的集合。

c#.netalgorithm
5

好的 - 我甚至不确定术语是否正确 - 而且我确信这里一定有个术语 - 但我会尽力解释。这不完全是一个叉积，结果的顺序非常关键。

假设：

IEnumerable<IEnumerable<string>> sets = 
      new[] { 
              /* a */ new[] { "a", "b", "c" },
              /* b */ new[] { "1", "2", "3" },
              /* c */ new[] { "x", "y", "z" }
            };

每个内部可枚举都代表一条指令，用于生成以下的连接集合（这里的顺序很重要）：

set a* = new string[] { "abc", "ab", "a" };
set b* = new string[] { "123", "12", "1" };
set c* = new string[] { "xyz", "xy", "x" };

我希望能按照以下方式生成一组有序的连接结果：
set final = new string { a*[0] + b*[0] + c*[0], /* abc123xyz */
                         a*[0] + b*[0] + c*[1], /* abc123xy  */
                         a*[0] + b*[0] + c*[2], /* abc123x   */
                         a*[0] + b*[0],         /* abc123    */
                         a*[0] + b*[1] + c*[0], /* abc12xyz  */
                         a*[0] + b*[1] + c*[1], /* abc12xy   */
                         a*[0] + b*[1] + c*[2], /* abc12x    */
                         a*[0] + b*[1],         /* abc12     */
                         a*[0] + b*[2] + c*[0], /* abc1xyz   */
                         a*[0] + b*[2] + c*[1], /* abc1xy    */
                         a*[0] + b*[2] + c*[2], /* abc1x     */
                         a*[0] + b*[2],         /* abc1      */
                         a*[0],                 /* abc       */
                         a*[1] + b*[0] + c*[0], /* ab123xyz  */

                         /* and so on for a*[1] */
                         /* ... */

                         a*[2] + b*[0] + c*[0], /* a123xyz   */

                         /* and so on for a*[2] */
                         /* ... */

                         /* now lop off a[*] and start with b + c */

                         b*[0] + c*[0],         /* 123xyz    */

                         /* rest of the combinations of b + c
                            with b on its own as well */

                         /* then finally */
                         c[0],
                         c[1],
                         c[2]};

显然，有很多组合的可能性！

我可以看出与数字进位（由于顺序也很重要）有相似之处，我确信在这里潜伏着排列组合。

问题是 - 如何编写这样的算法，以应对任意数量的字符串集？无论是 Linq 还是非 Linq; 我都不介意。

为什么我要这样做？

的确，为什么呢！？

在 Asp.Net MVC 中 - 我希望有局部视图可以为给定的后端/前端文化和语言组合重新定义。最基本的是，对于给定的基本视图 View，我们可以拥有 View-en-GB、View-en、View-GB 和 View，按照优先级的顺序（当然要认识到这种情况下，语言/文化代码可能相同，所以一些组合可能是相同的 - 通过 Distinct() 来解决这个问题）。

但我还有其他视图，在考虑文化因素之前，它们本身就有其他可能的组合（时间太长了 - 但事实是，这个算法将使我能够提供许多我想要向开发人员提供的真正酷的功能！）。

我希望产生一个可接受的视图名称的搜索列表，遍历整个列表，直到找到最具体的匹配项（由这个算法产生这些连接的顺序所控制），然后提供已解析的局部视图。

搜索的结果后续可以缓存，以避免一直运行算法的开销。

我已经有一个非常基本的版本，只有一个字符串可枚举。但这是一大堆海鲜！

任何帮助都将不胜感激。

3个回答
3

这是我的尝试：

void Main()
{
    IEnumerable<IEnumerable<string>> sets = 
          new[] { 
                  /* a */ new[] { "a", "b", "c" },
                  /* b */ new[] { "1", "2", "3" },
                  /* c */ new[] { "x", "y", "z" }
                };

    var setCombinations = from set in sets
                          select (from itemLength in Enumerable.Range(1, set.Count()).Reverse()
                                  select string.Concat(set.Take(itemLength).ToArray()));

    IEnumerable<string> result = new[] { string.Empty };

    foreach (var list in setCombinations) {
        result = GetCombinations(result, list);
    }
    // do something with the result
}

IEnumerable<string> GetCombinations(IEnumerable<string> root, IEnumerable<string> append) {
    return from baseString in root
           from combination in ((from str in append select baseString + str).Concat(new [] { baseString }))
           select combination;
}
1
工作得很好 - 它包括将原始输入数组转换为它们的连接集的代码 - 非常好，谢谢！ - Andras Zoltan
我将此标记为答案，主要是因为它代表了从输入数组到输出的完整往返。还因为Linq的使用而被赞赏; 很巧妙 :) - Andras Zoltan
2
这应该能够产生您想要的结果：
using System;
using System.Linq;
using System.Collections.Generic;

namespace SO3014119
{
    class Program
    {
        private static IEnumerable<string> GetStringCombinations(
            string prefix, 
            IEnumerable<string>[] collections, int startWithIndex)
        {
            foreach (var element in collections[startWithIndex])
            {
                if (startWithIndex < collections.Length - 1)
                {
                    foreach (var restCombination in
                        GetStringCombinations(prefix + element, collections,
                            startWithIndex + 1))
                    {
                        yield return restCombination;
                    }
                }

                yield return prefix + element;
            }
        }

        public static IEnumerable<string> GetStringCombinations(
            params IEnumerable<string>[] collections)
        {
            while (collections.Length > 0)
            {
                foreach (var comb in GetStringCombinations("", collections, 0))
                    yield return comb;

                // "lop off" head and iterate
                collections = collections.Skip(1).ToArray();
            }
        }

        static void Main(string[] args)
        {
            var a = new string[] { "a1", "a2", "a3" };
            var b = new string[] { "b1", "b2", "b3" };
            var c = new string[] { "c1", "c2", "c3" };

            foreach (string combination in GetStringCombinations(a, b, c))
            {
                Console.Out.WriteLine(combination);
            }
        }
    }
}

这将产生以下结果（请注意，我更改了输入集合中的条目，以便更容易看到它们是如何组合的）：
a1b1c1
a1b1c2
a1b1c3
a1b1
a1b2c1
a1b2c2
a1b2c3
a1b2
a1b3c1
a1b3c2
a1b3c3
a1b3
a1
a2b1c1
a2b1c2
a2b1c3
a2b1
a2b2c1
a2b2c2
a2b2c3
a2b2
a2b3c1
a2b3c2
a2b3c3
a2b3
a2
a3b1c1
a3b1c2
a3b1c3
a3b1
a3b2c1
a3b2c2
a3b2c3
a3b2
a3b3c1
a3b3c2
a3b3c3
a3b3
a3
b1c1
b1c2
b1c3
b1
b2c1
b2c2
b2c3
b2
b3c1
b3c2
b3c3
b3
c1
c2
c3
谢谢你的回答。很有趣 - 我会复制/粘贴并测试; 但是它缺少一些内容; 因为它应该以"a1a2a3b1b2b3c1c2c3"开头，所有的c都会掉落，然后'b3'掉落，我们再次应用所有的C，如此反复（真的！） - Andras Zoltan
抱歉，我只能回答被问到的问题，而不是你本应该问的问题。你明确列出了你想要的输出，我恰好产生了那个输出。如果你想要不同的输出，那么你需要改变问题。 - Lasse V. Karlsen
我刚刚在我的原始输入集“abc”，“123”，“xyz”上运行了代码。在问题中，我明确说明第一个条目应该是“abc123xyz”;但是这段代码却产生了“a1x”。可能是因为我在之前使用了a*[0]，b*[0]，c*[0]——它们是由原始a、b和c产生的连接数组。再次感谢您所付出的努力。 - Andras Zoltan
啊——这段代码唯一缺失的是将a、b、c；1、2、3；x、y、z转换为abc、ab、c；123、12、1；xyz、xy、x —— 如果我将它们输入到你的算法中，那么它就能完成工作了。我所需要做的就是先生成a、b和c*数组。非常聪明。谢谢！ - Andras Zoltan
1

解决方案似乎很简单（从算法角度来看）

在每个数组a*，b*，c*的末尾添加一个额外的空字符串

string[] a* = { "abc","ab","a","" };
string[] b* = { "123","12","1","" };
string[] c* = { "xyz","xy","x","" };

List<string> final = new List<string>();

现在对这三个数组进行嵌套循环

foreach(string aMember in a*)
foreach(string bMember in b*)
foreach(string cMember in c*)
final.add(aMember+bMember+cMember);

在a*、b*和c*的末尾添加额外的空字符串将按照所需的顺序生成特殊字符串，例如a[0]（= a[0]+b[3] + c[3]）。

编辑：此代码将产生一些额外的字符串。请参见下面的评论。

它还会生成a[0]+b[3]+c[0]，即“abcxyz”，结果中没有b*值的部分。 - Lasse V. Karlsen
添加空字符串 - 是的，我意识到这可能是简化解决方案的一部分；但是，虽然该算法对于恰好三个字符串集合可能有效，但无法应用于未知数量的字符串集合。 - Andras Zoltan
@Lasse：感谢你指出那个错误。我错过它真是太愚蠢了。 - apoorv020
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接