C# 多维笛卡尔积、组合算法

2022年11月2日 2076点热度 0人点赞 0条评论
内容目录

有以下 N 个因子:

        new List<string>{"A","B","C"},      // 位置 0
        new List<string>{"1","2","3"},      // 位置 1
        new List<string>{"①","②","③"},
        new List<string>{"Ⅰ","Ⅱ","Ⅲ"},
        new List<string>{"一","二","三"},

可以组成多个 n 长度的数组,如:

A   1   ①   Ⅰ   一

M * N * Z * X * Y

file

每个因子类型的位置都是固定的,现在要计算每一种组合并输出,并且最终有序。

方法一

从方法是从别人 Go 语言中的代码中学到,然后笔者使用 C# 编写实现的。
Go 版本地址:https://www.codetd.com/article/11896053

void Main()
{

    List<List<string>> sourceElements = new List<List<string>>()
    {
        new List<string>{"A","B","C"},
        new List<string>{"1","2","3"},
        new List<string>{"①","②","③"},
        new List<string>{"Ⅰ","Ⅱ","Ⅲ"},
        new List<string>{"一","二","三"},
    };

    IEnumerable<string[]> targetElments = Product(sourceElements);
    foreach (var item in targetElments)
    {
        Console.WriteLine(JsonSerializer.Serialize(item));
    }
}

public List<string[]> Product(List<List<string>> sets)
{
    Func<int, int> lens = (i => sets[i].Count);
    var product = new List<string[]>();

    for (var ix = new int[sets.Count]; ix[0] < lens(0); NextIndex(ix, lens))
    {
        var r = new List<string>();
        for (int j = 0; j < ix.Length; j++)
        {
            var k = ix[j];
            r.Add(sets[j][k]);
        }
        product.Add(r.ToArray());
    }
    return product;
}

public void NextIndex(int[] ix, Func<int, int> lens)
{
    for (int j = ix.Length - 1; j >= 0; j--)
    {
        ix[j]++;
        if (j == 0 || ix[j] < lens(j))
        {
            return;
        }
        ix[j] = 0;
    }
}

方法二

缺点多,产生了大量的对象、数组,这是笔者第一个版本写的,然后使用了第一种方法做优化。

void Main()
{
    List<List<string>> sourceElements = new List<List<string>>()
    {
        new List<string>{"A","B","C"},
        new List<string>{"1","2","3"},
        new List<string>{"①","②","③"},
        new List<string>{"Ⅰ","Ⅱ","Ⅲ"},
        new List<string>{"一","二","三"},
    };

    List<string[]> targetElments = new List<string[]>();
    var length = sourceElements.Count;
    // 无效的数量
    var invalidCount = 0;
    for (var i = 0; i < length; i++)
    {
        // A、B、C 
        // 1、2、3
        var sourceElment = sourceElements[i];
        var sourceCount = sourceElment.Count;
        if (targetElments.Count == 0)
        {
            foreach (var item in sourceElment)
            {
                var array = new string[length];
                array[0] = item;
                targetElments.Add(array);
            }
        }
        else
        {
            // A , null, null, null, null 
            var targetCount = targetElments.Count;
            for (int j = 0; j < targetCount; j++)
            {
                var targetElment = targetElments[j];
                // 当前因素所在位置
                var position = i;
                for (int k = 0; k < sourceCount; k++)
                {
                    // A , null, null, null, null | 1 | "1"
                    Build(targetElments, targetElment, position, sourceElment[k]);
                }
            }
            targetElments.RemoveRange(0,targetCount);
        }
    }
    foreach (var item in targetElments)
    {
        Console.WriteLine(JsonSerializer.Serialize(item));
    }

}

public void Build(List<string[]> elments, string[] source, int position, string value)
{
    var newArray = new string[source.Length];
    Array.Copy(source, newArray, source.Length);
    newArray[position] = value;
    elments.Add(newArray);
}

然后在实际场景中根据算法对部分代码进行优化。

痴者工良

高级程序员劝退师

文章评论