新手笔记[笛卡尔积] - C#浅析和代码实现

编辑于:2013-06-06

做这个分析最好用大于或等于3个的元素来进行,因为2个元素太特殊了,容易搅乱思路。

假定我们有3个元素集合,list1,list2,list3,值分别为“1,2”、“a,b,c”和“C,D”

其结果应该为:

1aC,1aD,1bC,1bD,1cC,1cD

2aC,2aD,2bC,2bD,2cC,2cD

如果某一元素集合为空会怎样?那么得到的结果集合也为空

通过结果的有序排列可以发现,第一元素集合里面的第一元素"1",将分别与第二元素集合和第三元素集合里面的所有元素进行逐一组合, 换句话说就是它将与后面的所有元素集合里面的每个元素进行逐一组合。

这个特性让我们很容易想到一个名词:递归

即每次用一个元素传入下一个元素集合并和其元素进行组合,这就形成了递归组合

不做任何限制的话,这个递归出来的结果将包含1,1a,1b之类的组合,显然,他们并不符合当前元素集合所应该得到的结果。

同样,观察组合结果我们也能发现,每一个组合的长度length等于元素集合的总个数, 这样,我加入了结果返回限制:组合长度应等于元素集合总个数


实现代码如下:

static List<string> newlist = new List<string>();
string _returnstr = "";


// 设置初始数据
newlist.Add("1,2,3");
newlist.Add("a,b,c");
newlist.Add("7,8,9");
Console.WriteLine("元素个数:{0}", newlist.Count);
Console.WriteLine();


// 调用递归方法,获取有效集合
GetLists(0, "", ref _returnstr);


/// <summary>
/// 获取集合
/// </summary>
/// <param name="i">当前数据下标</param>
/// <param name="_str">临时传递值,用于组合</param>
/// <param name="returnstr">返回集合字符串</param>
static void GetLists(int i, string _str, ref string returnstr)
{
    if (i >= newlist.Count) return;
    string[] _tmplist = newlist[i].Split(',');
    string _tmpstr = "";
    for (int k = 0; k < _tmplist.Length; k++)
    {
        _tmpstr = _str + _tmplist[k];
        GetLists(i + 1, _tmpstr, ref returnstr);
        if (_tmpstr.Length == newlist.Count)
        {
            returnstr += _tmpstr + ",";
        }
    }
}

返回列表