已知有36个数值对，如下图所示：
01 02 03 04 05 06 07 08
12 13 14 15 16 17 18
23 24 25 26 27 28
34 35 36 37 38
45 46 47 48
56 57 58
67 68
78
现要求输出4组 0-8 不重复的随机数，每组9个数，顺序不确定，
要求第1个数和第2个数（1-2），第2个数和第3个数（2-3），3-4,4-5,5-6,6-7, 1-5,2-9,4-8 两两组合，位置可以颠倒，组成的数值对在已知的36个数值对中存在。例如如下数组：
6 1 4 3 7 5 0 2 8
1-2 可以组成16 存在
2-3 可以组成14 存在
3-4 可以组成34 存在
4-5 可以组成37 存在
5-6 可以组成57 存在
6-7 可以组成05 存在
1-5 可以组成67 存在
2-9 可以组成18 存在
4-8 可以组成23 存在
那么这个随机数组就成立，这个数组中组成的数值对（16 14 34 37 57 05 67 18 23）从36个数值对中移除掉，然后输出第二组，第二组的数组也要满足
两两组合后的数字存在于剩下的27个数值对中，都满足后，然后把第二个数组可以组成的数值对从剩下的27个数组中移除掉，以此类推，输出四组数如
0, 1, 2, 3, 4, 5, 6, 7, 8,
1, 6, 4, 2, 5, 7, 0, 8, 3,
2, 7, 4, 8, 0, 5, 3, 6, 1,
0, 6, 7, 8, 3, 1, 4, 5, 2
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
public class com
{
private static long factorial(int n)
{
return (n > 1) ? n * factorial(n - 1) : 1;
}
/**
* 计算排列数，即A(n, m) = n!/(n-m)!
*
* @param n
* @param m
* @return
*/
public static long arrangement(int n, int m)
{
return (n >= m) ? factorial(n) / factorial(n - m) : 0;
}
/**
* 排列选择（从列表中选择n个排列）
*
* @param dataList
* 待选列表
* @param n
* 选择个数
*/
public static List<String> arrangementSelect(String[] dataList, int n)
{
System.out.println(String.format("A(%d, %d) = %d", dataList.length, n,
arrangement(dataList.length, n)));
String[] res = new String[n];
List<String> total = new ArrayList<>();
arrangementSelect(dataList, res, 0, total);
return total;
}
/**
* 排列选择
*
* @param dataList
* 待选列表
* @param resultList
* 前面（resultIndex-1）个的排列结果
* @param resultIndex
* 选择索引，从0开始
*/
private static void arrangementSelect(String[] dataList, String[] resultList,
int resultIndex, List<String> total)
{
int resultLen = resultList.length;
if (resultIndex >= resultLen)
{ // 全部选择完时，输出排列结果
String re = "";
for (String s : resultList)
{
re += s;
}
total.add(re);
return;
}
// 递归选择下一个
for (int i = 0; i < dataList.length; i++)
{
// 判断待选项是否存在于排列结果中
boolean exists = false;
for (int j = 0; j < resultIndex; j++)
{
if (dataList[i].equals(resultList[j]))
{
exists = true;
break;
}
}
if (!exists)
{ // 排列结果不存在该项，才可选择
resultList[resultIndex] = dataList[i];
arrangementSelect(dataList, resultList, resultIndex + 1, total);
}
}
}
// 36个数值对
public static List<String> getList()
{
List<String> list = new ArrayList<>();
list.add("01");
list.add("02");
list.add("03");
list.add("04");
list.add("05");
list.add("06");
list.add("07");
list.add("08");
list.add("12");
list.add("13");
list.add("14");
list.add("15");
list.add("16");
list.add("17");
list.add("18");
list.add("23");
list.add("24");
list.add("25");
list.add("26");
list.add("27");
list.add("28");
list.add("34");
list.add("35");
list.add("36");
list.add("37");
list.add("38");
list.add("45");
list.add("46");
list.add("47");
list.add("48");
list.add("56");
list.add("57");
list.add("58");
list.add("67");
list.add("68");
list.add("78");
return list;
}
public static List<String> getData()
{
List<String> list = new ArrayList<>();
list.add("0");
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
list.add("7");
list.add("8");
return list;
}
private static List<String> deleteIn(List<String> data, String deletString)
{
List<String> sor = new ArrayList<>();
for (String str : data)
{
if (!deletString.equals(str))
{
sor.add(str);
}
}
return sor;
}
private static void filerData(List<String> isLockdata, List<String> data,
List<String> randDatas, int endsign, List<String> ends, int loopsige)
{
if (endsign == 6)
{
if (isLockdata.contains((randDatas.get(0) + randDatas.get(4)))|| isLockdata.contains((randDatas.get(4) + randDatas.get(0))))
{
isLockdata = deleteIn(isLockdata,(randDatas.get(0) + randDatas.get(4)));
isLockdata = deleteIn(isLockdata,(randDatas.get(4) + randDatas.get(0)));
for (String str : data)
{
if (isLockdata.contains(randDatas.get(3) + str)|| isLockdata.contains(str + randDatas.get(3)))
{
isLockdata = deleteIn(isLockdata, (randDatas.get(3) + str));
isLockdata = deleteIn(isLockdata, (str + randDatas.get(3)));
data = deleteIn(data, str);
randDatas.add(str);
if (data.size() == 0)
{
break;
}
if (isLockdata.contains(randDatas.get(1) + data.get(0))|| isLockdata.contains(data.get(0) + randDatas.get(1)))
{
randDatas.add(data.get(0));
// System.out.println(randDatas);
ends.addAll(randDatas);
if (loopsige == 4)
{
System.out.println(ends);// ok好了
return;
}
isLockdata = deleteIn(isLockdata,
(randDatas.get(1) + data.get(0)));
isLockdata = deleteIn(isLockdata,
(data.get(0) + randDatas.get(1)));
List<String> newends = new ArrayList<>();
for (String d : ends)
{
newends.add(d);
}
List<String> newisLockdata = new ArrayList<>();
List<String> newisLockdata2 = new ArrayList<>();
for (String d : isLockdata)
{
newisLockdata.add(d);
newisLockdata2.add(d);
}
int newloopsign = loopsige + 1;
getNmber(newisLockdata, newisLockdata2, ends, newloopsign);
return;
}
}
}
}
}
if (randDatas == null || randDatas.size() == 0)
{
return;
}
String endchar = randDatas.get(randDatas.size() - 1);
List<String> old = new ArrayList<>();
for (String d : data)
{
old.add(d);
}
for (String d : old)
{
String next = endchar + d;
String renext = d + endchar;
if (isLockdata.contains(next) || isLockdata.contains(renext))
{
List tempdata = deleteIn(data, d);
List olddata = new ArrayList<>();
for (String lockdata : isLockdata)
{
olddata.add(lockdata);
}
olddata = deleteIn(olddata, next);
olddata = deleteIn(olddata, renext);
List<String> newrandDatas = new ArrayList<>();
for (String rand : randDatas)
{
newrandDatas.add(rand);
}
newrandDatas.add(d);
int newendsign = endsign + 1;
List<String> endsDatas = new ArrayList<>();
for (String rand : ends)
{
endsDatas.add(rand);
}
filerData(olddata, tempdata, newrandDatas, newendsign, endsDatas,
loopsige);
}
}
}
private static void getNmber(List<String> res, List<String> isLockdata,
List<String> ends, int loopsign)
{
for (String tString : res)
{
List<String> data = getData();
List<String> randDatas = new ArrayList<>();
char[] cs = tString.toCharArray();
for (char s : cs)
{
data = deleteIn(data, String.valueOf(s));
randDatas.add(String.valueOf(s));
}
List<String> newisLockdata = new ArrayList<>();
for (String str : isLockdata)
{
newisLockdata.add(str);
}
newisLockdata = deleteIn(newisLockdata, tString);
newisLockdata = deleteIn(newisLockdata,
String.valueOf(cs[1]) + String.valueOf(cs[0]));
filerData(newisLockdata, data, randDatas, 1, ends, loopsign);
}
}
public static void main(String[] args)
{
List<String> res = arrangementSelect(new String[]
{ "0", "1", "2", "3", "4", "5", "6", "7", "8" }, 2);
List<String> ends = new ArrayList<>();
getNmber(res, getList(), ends, 1);
}
}
网友评论