思想:
1、如果数组元素的长度为1的话(1),那么组合方式就是1中----(1)
2、如果数组元素的长度为2的书(1 , 2) ,那么组合的方式就是2种----(1 ,2 ) , (2 , 1)
3、如果数组元素的长度为3的话(1 , 2 ,3),那么组合的方式就是6种---(1 , 2 ,3),(1 , 3 ,2),(3 , 1 ,2),(3 , 2 ,1),(2 , 3 ,1),(2 , 1 ,3),
规律:
1、当数组长度为1时,返回的组合方式只有1种,就是它本身
2、当新加一个数组元素时,这个[color=Red]新元素就会与原来的每一种组合方式中的每个数组元素发成关系[/color],表现为:新数组元素在原来的每一种组合方式中的各个位置分别插入一次,这样就出现更多的组合方式,而这所有的组合方式的合集,就是加入新元素后的新数组的所有组合方式,
3、比如只有一个数组元素(1),我们添加一个数组元素2;[color=Red]在数组元素1之前插进去(2 , 1) ,在数组元素之后插进去(1 , 2)[/color]形成的新数组就是所有的组合
4、如果我们在上面两个元素的数组重在插入一个3(1 , 2),(2 , 1)
就要分别在(1 , 2)和(2 , 1)里面都要插入,
第一种在(1 , 2)插入,将3分别插入数组元素的前面、中间和后面得到------(3 , 1 ,2)(1 , 3 ,2),(1 , 2 ,3)
第二种在(2 , 1)插入,讲3分别插入数组元素的前面、中间和后面得到------(3 , 2 ,1),(2 , 3 ,1),(2 , 1 ,3)
这样也就是三个元素的组合方式了,以此类推:
下面用方法来实现,主函数的测试各位可自己写[code=java]public static List<int[]> GetDataArray(int[] data)
{
List<int[]> list = new List<int[]> ();
if(data ==null)
return list;
if (data.Length == 1) //如果长度为1,那么返回它的组合方式,即它本身。
{
list.Add(data);
}
else //否则,引入新的数组元素,并插入到原有的组合方式的各个位置,形成新的组合方式。
{
int[] dataSub = new int[data.Length - 1];
for (int i = 0; i < data.Length - 1; i++)
{
dataSub[i] = data[i + 1];
}
List<int[]> listOld = GetDataArray(dataSub); //获取原有的组合方式
int newNum = data[0];
int[] newData = null;
for (int i = 0; i < listOld.Count; i++) //遍历每一种原有的组合方式
{
for (int j = 0; j <= listOld[i].Length; j++) //遍历组合方式中的每个位置
{
newData = new int[listOld[i].Length + 1];
newData[j] = newNum;
int currentIndex = 0;
for (int n = 0; n < listOld[i].Length; n++)
{
if (currentIndex == j)
currentIndex++;
newData[currentIndex] = listOld[i][n];
currentIndex++;
}
list.Add(newData);
}
}
}
return list;
}[/code] |