求教穷举排列组合算法如何实现

Question

场景是这样子的：
需要生成唯一标志，总共8位，XXX XX XXX
前三位固定不变，4，5位可以是字母和数字，但是剔除了难以辨认的字母，如：I,O,L等，后三位只能是数字
一次请求最多能获取100个，且任何时候，获取的随机串都不能相同，请问该如何实现？

Answer 1

我第一感觉是打表。是不是acm看多了

Answer 2

public class MyPermutation { char a,b,c,d,e; List<String> resList = new ArrayList<String>();
List<String> forbiddenChars = new ArrayList<String>();
char curLetter; /**
 * 
 * @param curStr 当前最大字符串
 */
public MyPermutation(String curStr) {
forbiddenChars.add("O");
forbiddenChars.add("I");
forbiddenChars.add("L");

initParams(curStr);
}

private void initParams(String curStr) {
if (curStr != null && curStr.length() == 8) {
a = curStr.charAt(3);
b = curStr.charAt(4);
c = curStr.charAt(5);
d = curStr.charAt(6);
e = curStr.charAt(7);
}
} public char getNextLetter(char letter) {
curLetter = ++letter;
if (forbiddenChars.contains(String.valueOf(curLetter))) {
curLetter++;
getNextLetter(curLetter);
}
return curLetter;
} /**
 * 
 * @param number
 *            申请个数
 * @return
 */
public List<String> getChars(int number) { for (int i = 0; i < number; i++) {
if (e != '9') {
e++;
} else {
e = '0';
if (d != '9') {
d++;
} else {
d = '0'; if (c != '9') {
c++;
} else {
c = '0'; if (b < '9') {
b++;
} else if (b == '9') {
b = 'A';
} else if (b != 'Z') {
b = getNextLetter(b);
} else {
b = '0';
if (a < '9') {
a = getNextLetter(a);
} else if (a == '9') {
a = 'A';
} else if (a != 'Z') {
a = getNextLetter(a);
} else {
System.out.println("已经没有可用的字符串可以申请");
break;
}
}
}
}
}
String result = new StringBuffer("709").append(a).append(b)
.append(c).append(d).append(e).toString();
resList.add(result);
}
return resList;
} public static void main(String[] args) {
MyPermutation mp = new MyPermutation("709ZZ000");
System.out.println(mp.getChars(10));
}
}
大概的写了一个

Answer 3

我感觉生成的数肯定多，一次生成完了保存起来
                      每次随机取十个 然后做个标记
                      有标记的过滤掉，然后申请剩下的 一直到够了。
----------------------------------------------------
                 要不直接保存到数据库里面给个标记，每次得到的数过滤标记的，根据没标记的选择
保存起来感觉还是蛮对的，还方便查看。 yil
                                    

Answer 4

定义一个了类表示获取的元素，此类实现compator接口  存在hashset中 可以保证不重复 

Answer 5

分享一下我的思路：符合条件的排列一共有  P(23, 2) * P(10, 3) = 364320 种。问题拆解成两部分：
1 - 建立一种算法，给出 364320 之内的一个数（下标），返回一个确定的排列结果，即这种算法可以把 364320 种排列结果按固定的顺序给出1 完成以后，就可以在 364320 范围内随机取一个下标，然后得到一个随机排列了，剩下的是问题 2，如何防止一个排列被取得多于一次。你可以用一个 set 来记录被取过的下标，但这不是好的做法，随着被取过的下标越来越多，“随机一个未被取过的下标”的效率也越来越低，你需要多次随机才可能取到一个未被取过的下标。这一步有现成的排列组合算法可以实现，我这里有现成的工具类： 
http://blog.csdn.net/raistlic/article/details/78448122 - 建立一种算法，解决随机获取未被取过的下标的问题，我立刻能想到的算法是 "binary rank & select"，假如有下面的一个有序的 bit 列：
// v   0 0 0 1 0 1 1 0 ...
// i   0 1 2 3 4 5 6 7 ...
其中 i 为下标，v中 0 表示未被取过，1 表示被取过，那么问题2演化为： 设计一种算法，使得这个 bit 列可以做两种快速查询：a - 给定 bit 列的大小，快速求出有多少个 0 （这一步为你的随机 random.nextInt(int) 方法提供那个 int 参数），即 rank0(size)b - 给出一个随机数 0 <= x < rank0(size)，快速获取第x个0的下标，即 select0(x)“binary rank & select”方法可以解决这两个问题，楼主可以搜索一下，不难实现。其中的思想是建立查询表，空间换时间，理论上 a 和 b 都能达到 constant time，实际做起来可能没那么理想，不过也是非常快的，而且占用空间非常有限。

Answer 6

如果是要求依次遍历的话
首先把第4、5位允许使用的字符做成一个字符数组a[]
然后
for(int i=0;i<a.length;i++){
    for(int j=0;j<a.length;j++){
        for(int k=0;k<999;k++){
            将前三位，加上a[i]，加上a[j]，加上带有前缀0的k
        }
    }
}如果要求随机性，则在a.length*a.length*1000范围内取一个随机数，然后……同上
注：通过整除和取模获得i、j、k的值如果要求不重复，那就记录一下，用数组======================
另外，7楼给的算式是错的，怎么能用排列呢？没有谁规定不能出现像888、999这样的数字吧