不规则二维数组遍历组合(笛卡尔积)算法(非递归)

作者：V君发布于：2014-5-12 14:14 Monday 分类：挖坑经验

最近需要用到生成一定规则的URL, 于是整了个算法.

由于网上找来的参差不齐, 各种参考后自己改出个总算能用的来.

思想很简单:

1. 定义一个索引(也可以称作游标吧)数组用来按索引拼接

2. 索引数组最后一位自增

3. 检查进位

4. 最高位到达后退出循环

给C#的默认参数以及扩展方法点两个赞!

受惠于扩展方法, 系统集成功能不带类似js的array.join -- 自己写!

默认参数给调用提升了灵活性!

下面是代码和示例

public static string[] MakeCrossCombine(this string[][] me)
{
    if (me.Length == 0 || me.Any(p => p.Length == 0))
        throw new ArgumentException("empty array!");

    List<string> lstResult = new List<string>(
        me.Select(p => p.Length)
         .Aggregate((p, n) => p * n)
    );

    int[] arrIndex = new int[me.Length];

    bool flg_incomplete = true;

    do
    {
        //get a result by current arrIndex
        lstResult.Add(
             me.Select((p, i) => me[i][arrIndex[i]])
              .Join("")
        );

        //inc. lastDigit
        arrIndex[me.Length - 1]++;

        //dig.  rtl-check up
        for (int digRight = me.Length - 1;

digRight >= 0;

               digRight--)
        {
            int ixC = arrIndex[digRight];
            int meC = me[digRight].Length;

            if (ixC == meC) //cycle complete
            {
                if (digRight == 0) //array complete
                {
                    flg_incomplete = false;
                    break;
                }

                arrIndex[digRight - 1]++; //dig.up
                arrIndex[digRight] = 0;
                continue;
            }

            break;

        }//end for

    } while (flg_incomplete);

    return lstResult.ToArray();
}

public static string Join(this IEnumerable<string> source

, string separator = ",", string ifnull = "")

{
    return string.Join(
        separator
        , source
            .Select(p => p ?? ifnull)
            .ToArray()
    );
}

示例:

var arr2d=new String[][]{
    new String[]{"1","2"},
    new String[]{"A","B","C","D"},
    new String[]{"甲","乙","丙"},
    new String[]{"来","去","停"},
};

foreach(var item in arr2d.MakeCrossCombine())
   Console.WriteLine(item);

输出:

1A甲来

1A甲去

1A甲停

1A乙来

1A乙去

1A乙停

1A丙来

1A丙去

1A丙停

1B甲来

1B甲去

1B甲停

1B乙来

1B乙去

1B乙停

1B丙来

1B丙去

1B丙停

1C甲来

1C甲去

1C甲停

1C乙来

1C乙去

1C乙停

1C丙来

1C丙去

1C丙停

1D甲来

1D甲去

1D甲停

1D乙来

1D乙去

1D乙停

1D丙来

1D丙去

1D丙停

2A甲来

2A甲去

2A甲停

2A乙来

2A乙去

2A乙停

2A丙来

2A丙去

2A丙停

2B甲来

2B甲去

2B甲停

2B乙来

2B乙去

2B乙停

2B丙来

2B丙去

2B丙停

2C甲来

2C甲去

2C甲停

2C乙来

2C乙去

2C乙停

2C丙来

2C丙去

2C丙停

2D甲来

2D甲去

2D甲停

2D乙来

2D乙去

2D乙停

2D丙来

2D丙去

2D丙停

3A甲来

3A甲去

3A甲停

3A乙来

3A乙去

3A乙停

3A丙来

3A丙去

3A丙停

3B甲来

3B甲去

3B甲停

3B乙来

3B乙去

3B乙停

3B丙来

3B丙去

3B丙停

3C甲来

3C甲去

3C甲停

3C乙来

3C乙去

3C乙停

3C丙来

3C丙去

3C丙停

3D甲来

3D甲去

3D甲停

3D乙来

3D乙去

3D乙停

3D丙来

3D丙去

3D丙停

标签: 软件开发 C# 算法字符串处理

« 令人抓狂的糟糕代码 | 凶残的阿拉伯数字转大写算法(正则/ASCII)»

引用地址:

评论：

(垃圾网址已删除)
2014-05-12 21:27

楼主还在上学？

V君
2014-05-12 21:43

@(垃圾网址已删除)：啊哈评论功能才恢复不到半天SPAM就来了乂D

发表评论：

V君的博客

中二死宅无脑码农　中二御宅コーダー　Chuuni Otaku Coder　　　　　　　　TOPCL = The Open Productivity Creative Laboratory ?