ABC三个整数，取值0到2，求所有情况

Question

嘿嘿，被我骗进来的不好意思啦，题目是下面问题的简化情况。设有n个数x0、x1、x2、x(n-1)，每个数可取的值由类型为T的range[]定义，求所有情况。（当然是用泛型咯）例如，n=3，T=int，range[]={0,1}，我要得到
x y z <--这是随意的，只是代表一下。不必包含在输出中。
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1例如n=2，T=string，range[]={"+","-"}，我要得到
x y
+ +
+ -
- +
- -得到的所有情况我希望存在T类型的result[i][j]中，其中i表示例子中的一行。这样的形式方便我之后的处理。

Answer 1

http://topic.csdn.net/u/20090217/21/f41ed9f6-f929-451c-a5c9-80d2e408422a.html?seed=784894353

Answer 2

回答过了
http://topic.csdn.net/u/20081015/09/524C5D5F-D4C8-4715-BFBB-C8076D921FA5.htmlnamespace WindowsApplication9
{
    public partial class Form1 : Form
    {
        String Result = String.Empty;
        public Form1()
        {
            String S = "ABCDEFGH";
            int Count = 3;
            String TempResult = String.Empty;
            GetIt(S, Count, ref TempResult);
            MessageBox.Show(Result);
        }        void GetIt(String S, int Count, ref String TempResult)
        {
            if (Count == 0)
            {
                Result += TempResult + " ";
                return;
            }
            for (int i = 0; i < S.Length; i++)
            {
                String C = S.Substring(i, 1);
                String T = S.Remove(i, 1);
                TempResult += C;
                GetIt(T, Count - 1, ref TempResult);
                TempResult = TempResult.Remove(TempResult.Length - 1, 1);
            }
        }
    }
}输出结果： 
ABC ABD ABE ABF ABG ABH ACB ACD ACE ACF ACG ACH ADB ADC ADE ADF ADG ADH AEB AEC AED AEF AEG AEH AFB AFC AFD AFE AFG AFH AGB AGC AGD AGE AGF AGH AHB AHC AHD AHE AHF AHG BAC BAD BAE BAF BAG BAH BCA BCD BCE BCF BCG BCH BDA BDC BDE BDF BDG BDH BEA BEC BED BEF BEG BEH BFA BFC BFD BFE BFG BFH BGA BGC BGD BGE BGF BGH BHA BHC BHD BHE BHF BHG CAB CAD CAE CAF CAG CAH CBA CBD CBE CBF CBG CBH CDA CDB CDE CDF CDG CDH CEA CEB CED CEF CEG CEH CFA CFB CFD CFE CFG CFH CGA CGB CGD CGE CGF CGH CHA CHB CHD CHE CHF CHG DAB DAC DAE DAF DAG DAH DBA DBC DBE DBF DBG DBH DCA DCB DCE DCF DCG DCH DEA DEB DEC DEF DEG DEH DFA DFB DFC DFE DFG DFH DGA DGB DGC DGE DGF DGH DHA DHB DHC DHE DHF DHG EAB EAC EAD EAF EAG EAH EBA EBC EBD EBF EBG EBH ECA ECB ECD ECF ECG ECH EDA EDB EDC EDF EDG EDH EFA EFB EFC EFD EFG EFH EGA EGB EGC EGD EGF EGH EHA EHB EHC EHD EHF EHG FAB FAC FAD FAE FAG FAH FBA FBC FBD FBE FBG FBH FCA FCB FCD FCE FCG FCH FDA FDB FDC FDE FDG FDH FEA FEB FEC FED FEG FEH FGA FGB FGC FGD FGE FGH FHA FHB FHC FHD FHE FHG GAB GAC GAD GAE GAF GAH GBA GBC GBD GBE GBF GBH GCA GCB GCD GCE GCF GCH GDA GDB GDC GDE GDF GDH GEA GEB GEC GED GEF GEH GFA GFB GFC GFD GFE GFH GHA GHB GHC GHD GHE GHF HAB HAC HAD HAE HAF HAG HBA HBC HBD HBE HBF HBG HCA HCB HCD HCE HCF HCG HDA HDB HDC HDE HDF HDG HEA HEB HEC HED HEF HEG HFA HFB HFC HFD HFE HFG HGA HGB HGC HGD HGE HGF 

Answer 3

现在再看，不用ref可以更简单

Answer 4

写了个循环的using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            //int类型测试
            Pro<int> pInt = new Pro<int>(3, new int[] { 0, 1, 2 });
            pInt.FillResult();
            foreach (int[] i in pInt.result)
            {
                int n = i.Length;
                for (int j = 0; j < n; ++j)
                {
                    Console.Write("{0}\t", i[j]);
                }
                Console.WriteLine();
            }
            //string类型测试
            Pro<String> pString = new Pro<string>(3, new string[] { "a", "b", "c", "d", "e", "f" });
            pString.FillResult();
            foreach (string[] i in pString.result)
            {
                int n = i.Length;
                for (int j = 0; j < n; ++j)
                {
                    Console.Write("{0}\t", i[j]);
                }
                Console.WriteLine();
            }
        }
    }    class Pro<T>
    {
        public T[] x;
        public T[] range;
        public List<T[]> result;
        /// <summary>
        /// </summary>
        /// <param name="n">变量的个数</param>
        /// <param name="range">变量取值的集合(无重复值)</param>
        public Pro(int n, T[] range)
        {
            this.x = new T[n];
            this.range = range;
            for (int i = 0; i < n; ++i) x[i] = range[0];
            this.result = new List<T[]>();
        }
        public void FillResult()    //得到结果集
        {
            int i, j, k = x.Length - 1, n = range.Length, m;
            T[] l;
            while (true)
            {
                //对最后一个变量进行循环,并把得到的一种排列加入结果集.
                for (i = 0; i < n; ++i) 
                {
                    x[k] = range[i];
                    l = new T[k + 1];
                    x.CopyTo(l, 0);
                    result.Add(l);
                }
                //循环结束后对前面的变量进行进位操作
                j = k - 1;
                m = Array.IndexOf(range, x[j]) + 1;
                while (true)
                {
                    if (m < n)
                    {
                        x[j] = range[m];
                        break;
                    }
                    else
                    {
                        x[j--] = range[0];
                        if (j < 0) return;
                        m = Array.IndexOf(range, x[j]) + 1;
                    }
                }
            }
        }
    }
}输出结果:0       0       0
0       0       1
0       0       2
0       1       0
0       1       1
0       1       2
0       2       0
0       2       1
0       2       2
1       0       0
1       0       1
1       0       2
1       1       0
1       1       1
1       1       2
1       2       0
1       2       1
1       2       2
2       0       0
2       0       1
2       0       2
2       1       0
2       1       1
2       1       2
2       2       0
2       2       1
2       2       2
a       a       a
a       a       b
a       a       c
a       a       d
a       a       e
a       a       f
a       b       a
a       b       b
a       b       c
a       b       d
a       b       e
a       b       f
a       c       a
a       c       b
a       c       c
a       c       d
a       c       e
a       c       f
a       d       a
a       d       b
a       d       c
a       d       d
a       d       e
a       d       f
a       e       a
a       e       b
a       e       c
a       e       d
a       e       e
a       e       f
a       f       a
a       f       b
a       f       c
a       f       d
a       f       e
a       f       f
b       a       a
b       a       b
b       a       c
b       a       d
b       a       e
b       a       f
b       b       a
b       b       b
b       b       c
b       b       d
b       b       e
b       b       f
b       c       a
b       c       b
b       c       c
b       c       d
b       c       e
b       c       f
b       d       a
b       d       b
b       d       c
b       d       d
b       d       e
b       d       f
b       e       a
b       e       b
b       e       c
b       e       d
b       e       e
b       e       f
b       f       a
b       f       b
b       f       c
b       f       d
b       f       e
b       f       f
c       a       a
c       a       b
c       a       c
c       a       d
c       a       e
c       a       f
c       b       a
c       b       b
c       b       c
c       b       d
c       b       e
c       b       f
c       c       a
c       c       b
c       c       c
c       c       d
c       c       e
c       c       f
c       d       a
c       d       b
c       d       c
c       d       d
c       d       e
c       d       f
c       e       a
c       e       b
c       e       c
c       e       d
c       e       e
c       e       f
c       f       a
c       f       b
c       f       c
c       f       d
c       f       e
c       f       f
d       a       a
d       a       b
d       a       c
d       a       d
d       a       e
d       a       f
d       b       a
d       b       b
d       b       c
d       b       d
d       b       e
d       b       f
d       c       a
d       c       b
d       c       c
d       c       d
d       c       e
d       c       f
d       d       a
d       d       b
d       d       c
d       d       d
d       d       e
d       d       f
d       e       a
d       e       b
d       e       c
d       e       d
d       e       e
d       e       f
d       f       a
d       f       b
d       f       c
d       f       d
d       f       e
d       f       f
e       a       a
e       a       b
e       a       c
e       a       d
e       a       e
e       a       f
e       b       a
e       b       b
e       b       c
e       b       d
e       b       e
e       b       f
e       c       a
e       c       b
e       c       c
e       c       d
e       c       e
e       c       f
e       d       a
e       d       b
e       d       c
e       d       d
e       d       e
e       d       f
e       e       a
e       e       b
e       e       c
e       e       d
e       e       e
e       e       f
e       f       a
e       f       b
e       f       c
e       f       d
e       f       e
e       f       f
f       a       a
f       a       b
f       a       c
f       a       d
f       a       e
f       a       f
f       b       a
f       b       b
f       b       c
f       b       d
f       b       e
f       b       f
f       c       a
f       c       b
f       c       c
f       c       d
f       c       e
f       c       f
f       d       a
f       d       b
f       d       c
f       d       d
f       d       e
f       d       f
f       e       a
f       e       b
f       e       c
f       e       d
f       e       e
f       e       f
f       f       a
f       f       b
f       f       c
f       f       d
f       f       e
f       f       f

Answer 5

我想到了个方法，用了些数学方法，个人认为不错，大家来评判下。/// <summary>
        /// 根据指定参数创建序列
        /// </summary>
        /// <typeparam name="T">序列中可选用的符号的类型</typeparam>
        /// <param name="range">序列中可选用的符号</param>
        /// <param name="amount">使用那些符号的元素个数</param>
        /// <returns>[x][y]：x表示行，y表示列</returns>
        public static T[][] Create<T>(T[] range, int n)
        {
            //初始化arr，它将包含所有信息，并作为返回值。
            int lines = Convert.ToInt32(Math.Pow(range.Length, n));
            T[][] arr = new T[lines][];
            for (int i = 0; i < arr.Length; i++)
                arr[i] = new T[n];            /*
                0 0 0 
                0 0 1 
                0 1 0 
                0 1 1 
                1 0 0 
                1 0 1 
                1 1 0 
                1 1 1                 从列来看，
                第三列的变化就是0101，周期为1（每个值用一次）；
                第二列的变化是00110011，周期为2（每个值用2次）；
                第一列的变化是00001111，周期为4=2的2次方。                所以对于n列（即有n个变量）的表，第i（i>0）列的周期是range.Length的（N-i）次方。
             */
            int period, use, times;//period表示该列的周期，times记录字母剩余可用的次数（用完就要换字母了），use表示正在使用的字母的下标。
            for (int y = arr[0].Length - 1; y >= 0; y--)//循环列
            {
                period = Convert.ToInt32(Math.Pow(range.Length, arr[0].Length - y - 1));
                use = 0;
                times = period;
                for (int x = 0; x < arr.Length; x++)//循环行
                {
                    arr[x][y] = range[use];
                    times--;
                    if (times == 0)
                    {
                        times = period;
                        use++;
                        if (use == range.Length)
                            use = 0;
                    }
                }
            }            return arr;
        }
    }

Answer 6

我试了下，SolaWing的方法速度是我的2/3。大家帮我看看我的到底慢在哪里呢？

Answer 7

楼主能想到这个方法的确不错,总的来说较慢的原因如下:
若有n个数,可选用的符号个数为m;
我每产生一条记录循环一次,总共循环m^n次,楼主循环次数为n*(m^n);n值越大,速度差会越明显.(这是主要原因)
另外楼主的一些习惯不太好,对于经常调用的方法返回值不变或变化规律,应当尽量把这值保存下来,而不是再调用方法.(通过变量直接访问值要比通过对象调用方法或属性得到值快很多)
现帮楼主代码修改如下:
/// <summary> 
        /// 根据指定参数创建序列 
        /// </summary> 
        /// <typeparam name="T">序列中可选用的符号的类型 </typeparam> 
        /// <param name="range">序列中可选用的符号 </param> 
        /// <param name="amount">使用那些符号的元素个数 </param> 
        /// <returns>[x][y]：x表示行，y表示列 </returns> 
        public static T[][] Create <T>(T[] range, int n) 
        { 
            //初始化arr，它将包含所有信息，并作为返回值。
            int m=range.Length;
            int lines = Convert.ToInt32(Math.Pow(m, n)); 
            T[][] arr = new T[lines][]; 
            for (int i = 0; i < lines; i++) 
                arr[i] = new T[n];             /* 
                0 0 0 
                0 0 1 
                0 1 0 
                0 1 1 
                1 0 0 
                1 0 1 
                1 1 0 
                1 1 1                 从列来看， 
                第三列的变化就是0101，周期为1（每个值用一次）； 
                第二列的变化是00110011，周期为2（每个值用2次）； 
                第一列的变化是00001111，周期为4=2的2次方。                 所以对于n列（即有n个变量）的表，第i（i>0）列的周期是range.Length的（N-i）次方。 
            */ 
            int period=1, use, times;//period表示该列的周期，times记录字母剩余可用的次数（用完就要换字母了），use表示正在使用的字母的下标。 
            for (int y = n- 1; y >= 0; y--)//循环列 
            { 
//删掉移到下边..因为整形取不了0.5
//period = Convert.ToInt32(Math.Pow(range.Length, arr[0].Length - y - 1)); 
                use = 0; 
                times = period; 
                for (int x = 0; x < lines; x++)//循环行 
                  { 
                    arr[x][y] = range[use]; 
                    times--; 
                    if (times == 0) 
                    { 
                        times = period; 
                        use++; 
                        if (use == m) 
                            use = 0; 
                    } 
                } 
                period *=m;
            }             return arr; 
        } 
    }另外我改了下我的代码,主要是将结果集变成了数组,另外为数的取值添加索引,避免返复调用Array.IndexOf方法.
using System;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime d1 = DateTime.Now;
            //int类型测试 
            Pro<int> pInt = new Pro<int>(8, new int[] { 0, 1, 2,3,4,5,6,7 });
            pInt.FillResult();
            DateTime d2 = DateTime.Now;
            Console.WriteLine(d2 - d1);
            //foreach (int[] i in pInt.result)
            //{
             //   int n = i.Length;
             //   for (int j = 0; j < n; ++j)
             //   {
             //       Console.Write("{0}\t", i[j]);
            //    }
            //    Console.WriteLine();
            //}
            //string类型测试 
            d1 = DateTime.Now;
            Pro<String> pString = new Pro<string>(8, new string[] { "a", "b", "c", "d", "e", "f","g","h" });
            pString.FillResult();
            d2 = DateTime.Now;
            Console.WriteLine(d2 - d1);
            //foreach (string[] i in pString.result)
            //{
            //    int n = i.Length;
           //     for (int j = 0; j < n; ++j)
           //     {
           //         Console.Write("{0}\t", i[j]);
            //    }
            //    Console.WriteLine();
            //}
        }
    }    class Pro<T>
    {
        public T[] range;
        public T[][] result;
        public int[] index;
        /// <summary> 
        /// </summary> 
        /// <param name="n">变量的个数>0 </param> 
        /// <param name="range">变量取值的集合(无重复值) </param> 
        public Pro(int n, T[] range)
        {
            this.index = new int[n-1];
            this.range = range;
            for (int i = 0; i < n-1; ++i)
            {
                index[i] = 0;
            }
            this.result = new T[(int)(Math.Pow(range.Length,n))][];
        }
        public void FillResult()    //得到结果集 
        {
            int i, j=0, k = index.Length, n = range.Length;
            int l=0;
            while (true)
            {
                //对最后一个变量进行循环,并把得到的一种排列加入结果集. 
                for (i = 0; i < n; ++i)
                {
                    result[l] = new T[k + 1];
                    for (j = 0; j < k; ++j) 
                    {
                        result[l][j] = range[index[j]];
                    }
                    result[l++][j] = range[i];
                }
                //循环结束后对前面的变量进行进位操作 
                try
                {
                    while ((++index[--j]) == n)
                    {
                        if (j == 0) return;
                        index[j] = 0;
                    }
                }
                catch (IndexOutOfRangeException) { return; }
            }
        }
    }
}
我觉得性能应该会提升,但经过实际测试,
int类型时原代码和新代码时间基本一样为10.4s,到是把新代码的result变成List<T[]>并默认初始化的集合反而快了1s为9.4s.
string类型时原代码和result为默认初始化的List<T[]>集合时基本一样为21.7s,T[][]数组的新代码又反而快了1.5s为20.2s.
想不通为什么会这样,借贴向高手问下.
难道List在超出默认长度进行自动加长时没有额外的运算量开销的吗?