【欢迎挑战】两个数组交织排列算法，本组元素不相邻

【欢迎挑战】两个数组交叉排列算法，本组元素不相邻
string[] en = { "A", "B", "C" };
string[] num = { "1", "2", "3" };

两个数组交叉排列组合，字母和字母隔开，数字和数字不相邻，有多少种排法? 请用编程输出所有结果
输出结果示例：

A 1  B  2  C  3 

A 1  B  3  C  2 

A 2  B  1  C  3

A 2  B  3  C  1

A 3  B  1  C  2

A 3  B  2  C  1


A 1  C  2  B  3 

A 1  C  3  B  2 

A 2  C  1  B  3

A 2  C  3  B  1

A 3  C  1  B  2

A 3  C  2  B  1


B 1  A  2  C  3

B 1  A  3  C  2

B 2  A  1  C  3

B 2  A  3  C  1

B 3  A  1  C  2

B 3  A  2  C  1


B 1  C  2  A  3

B 1  C  3  A  2

B 2  C  1  A  3

B 2  C  3  A  1

B 3  C  1  A  2

B 3  C  2  A  1

...

我觉得至少有72种，数学忘完了，悲剧。。。
------解决方案--------------------

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;


namespace ConsoleApplication1

{

    class Program

    {

        static void Main(string[] args)

        {