ñ名单笛卡尔乘积 [英] Cartesian product of n lists

问题描述

我有n个特定类型的列表，我的要求是从他们创造笛卡尔乘积。我该怎么做了。

I have n lists of a specific type, my requirement is to create Cartesian product from them. How do I do it.

我能想出的名单，但静态数列表的动态数量让我感到吃惊。 鸭preciate你的帮助在此方面。

I could figure out for a static number of lists but dynamic number of lists amazes me. Appreciate your help in this regard.

推荐答案

我有一个IDEEA：使用防爆pression树动态生成code，做你所需要的：

I have an ideea : use Expression trees to dynamically generate code that does what you need:

下面是一个完整的解决方案：

Here is a full solution:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;
using System.Text;

namespace testProjectExpressions
{
class Program
{
    static void Main(string[] args)
    {
        List<int> lst1 = new List<int>()
                         {
                             1,
                             2,
                             3
                         };


        List<int> lst2 = new List<int>()
                         {
                             4,
                             5,
                             6
                         };

        List<int> lst3 = new List<int>()
                         {
                             7,
                             8
                         };

        var fnc = CartesianProduct<int>(3);

        var res = fnc(new[] {lst1, lst2, lst3 });

        foreach (var product in res)
        {
            for (int index = 0; index < product.Length; index++)
            {
                var productVar = product[index];
                if (index < product.Length - 1)
                    Console.Write(productVar + ",");
                else
                {
                    Console.WriteLine(productVar);
                }
            }
        }

        Console.ReadKey();
    }

    private static Func<List<T>[], List<T[]>> CartesianProduct<T>(int howMany)
    {
        var inputArrayOfLists = Expression.Parameter(typeof (List<T>[]), "inputArgument");
        ParameterExpression[] loopVariables = new ParameterExpression[howMany];
        for (int index = 0; index < howMany; index++)
            if (loopVariables[index] == null)
                loopVariables[index] = Expression.Variable(typeof (T));

        List<Expression> finalStatements = new List<Expression>();

        // emit the create new object
        var resultExpression = Expression.Variable(typeof (List<T[]>), "result");

        var assignExpression = Expression.Assign(resultExpression, Expression.New(typeof (List<T[]>)));
        finalStatements.Add(assignExpression);

        // the "Add" method
        MethodInfo addMethod = typeof (List<T[]>).GetMethod("Add", BindingFlags.Instance | BindingFlags.Public);

        var EnumerableType = typeof(IEnumerable<T>);
        MethodInfo GetEnumeratorMethod = EnumerableType.GetMethod("GetEnumerator"); 
        var moveNextMethod = typeof(IEnumerator).GetMethod("MoveNext");

        Expression recursiveExpression = null;

        for (int index = 0; index < howMany; index++)
        {
            var variable = loopVariables[index];
            var indexAccess = Expression.ArrayIndex(inputArrayOfLists, Expression.Constant(index));
            var currentListExpression = indexAccess;

            if (recursiveExpression == null)
            {
                var arrayVariable = Expression.Variable(typeof (T[]), "myArray");
                List<Expression> initExpressions = new List<Expression>();
                List<Expression> statements = new List<Expression>();

                var assign = Expression.Assign(arrayVariable, Expression.NewArrayInit(typeof (T), loopVariables));
                statements.Add(assign);

                Expression callAddExpression = Expression.Call(resultExpression, addMethod, arrayVariable);
                statements.Add(callAddExpression);

                recursiveExpression = Expression.Block(new[] {arrayVariable}, statements);
            }

            recursiveExpression = ForEachExpression(typeof(IEnumerator<T>), GetEnumeratorMethod, moveNextMethod,
                currentListExpression, variable, recursiveExpression);
        }

        finalStatements.Add(recursiveExpression);
        finalStatements.Add(resultExpression);

        List<ParameterExpression> blockParameters = new List<ParameterExpression>(loopVariables);
        blockParameters.Add(resultExpression);

        Expression block = Expression.Block(blockParameters, finalStatements);

        var compiled = Expression.Lambda(block, inputArrayOfLists).Compile() as Func<List<T>[], List<T[]>>;
        return compiled;
    }

    // compiles a foreach expression on the given collection!
    public static Expression ForEachExpression(
            Type enumeratorType,
            MethodInfo getEnumeratorMethod,
            MethodInfo moveNextMethod,
            Expression collection,
            ParameterExpression loopVariable,
            Expression loopContent)
    {
        var breakLabel = Expression.Label("STOP");
        var enumeratorVar = Expression.Variable(enumeratorType, "collectionEnumerator");
        var loop = Expression.Block(new[] { enumeratorVar },
            Expression.Assign(enumeratorVar, Expression.Call(collection, getEnumeratorMethod)), // var enumerator = collection.GetEnumerator ();
            Expression.Loop(
                Expression.IfThenElse(
                        Expression.Equal(Expression.Call(enumeratorVar, moveNextMethod), Expression.Constant(true)), // daca move_next e true
                        Expression.Block(new[] { loopVariable },
                            Expression.Assign(loopVariable, Expression.Property(enumeratorVar, "Current")), // loopVariable = enumeratorVar.Current
                            loopContent // do some stuff with that entity
                        ),
                    Expression.Break(breakLabel) // jmp to break
                ),
            breakLabel) // break
        );

        return loop;
    }
}
}

这篇关于ñ名单笛卡尔乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！