Рассчитать набор составных наборов из n наборов

Question

Хорошо - я даже не уверен, что термин правильный - и я уверен, что обязательно будет термином для этого - но я сделаю все возможное, чтобы объяснить.Здесь это не совсем перекрестный продукт, и порядок результатов абсолютно важен.

Дано:

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()).

Но у меня также есть другие представления, которые сами по себе имеют другие возможныекомбинации до культуры даже не принимаются во внимание (слишком долго, чтобы вдаваться в это - но факт в том, что этот алгоритм даст целую кучу действительно крутых, которые я хочу предложить своим разработчикам!).

Я хочу создать список поиска всех допустимых имен представлений, перебирать весь лот до тех пор, пока не будет найдено наиболее конкретное совпадение (в соответствии с порядком, в котором этот алгоритм будет производить эти объединения), а затем податьвверх разрешенное частичное представление.

Результат поиска может быть впоследствии кэширован, чтобы избежать затрат на постоянное выполнение алгоритма.

У меня уже есть результату базовой версии этой работы, которая имеет только одну из перечисляемых строк.Но это совсем другой чайник морепродуктов!

Любая помощь очень ценится.

Answer 1

Это моя попытка:

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;
}

Answer 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

Answer 3

Решение кажется простым (алгоритмически)

Добавить пустую пустую строку в конце каждого массива 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]) в требуемом порядке.

РЕДАКТИРОВАТЬ: Этот код будет производить некоторые дополнительные строки.См. Комментарий ниже.