一道算法题（二）

[原题]

        http://www.iteye.com/topic/15295

写道

假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成，同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ，那么它一定是由 a, b, c, d, e 这 5 个字母构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些字母也就确定了，唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序：

如果字母 b 在字母 a 的后面，那么序列的第一个字母就是 A （After），否则序列的第一个字母就是 B （Before）；
如果字母 c 在字母 b 的后面，那么序列的第二个字母就是 A ，否则就是 B；
如果字母 d 在字母 c 的后面，那么 …… 不用多说了吧？直到这个字符串的结束。

这规则甚是简单，不过有个问题就是同一个 AB 序列，可能有多个字符串都与之相符，比方说序列“ABA”，就有“acdb”、“cadb”等等好几种可能性。说的专业一点，这一个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的 AB 序列，问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多大？注意，只要求个数，不要求枚举所有的字符串。

       这是一个老贴子了，并且3楼帖了答案，但是我认为，这个答案是不标准的，正确与否姑且不论，题中假设的26位长的数据那个是不支持的，因为极易出内存溢出，于是我重新设计了一种算法，我认为在内存上和时间中都比原来的优秀。

其实在后面还有更好的解法，欢迎读原贴。

 

[解题思路]

       一开始，我也受到了找到数据间的数学关系的影响。别说，还真找到了一个，只是数学太差，无法表达出来，假设为5位数，那么数据的分布是1,4,3,2,2,3,4,1...1,4,3,2,2,3,4,1.....，有什么用呢，好像没用。。

      终于偶然间恍然大悟，有个最简单的规律就是，假设这是一个从a开始，每次都有A,B两种可能，但是上级已出现的概率决定了下级出现的概率，由于不需要枚举出各个数据，那么可以只要知道上级中最后的那个数出现的位置，就决定了下级有那些可能会出现的情况。

 

[代码实现]

import java.math.BigInteger;

public class Main {

	/**
	 * 数组相加
	 * 
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static BigInteger[] add(BigInteger[] arr1, BigInteger[] arr2) {
		if (arr1.length != arr2.length)
			return null;
		for (int i = 0; i < arr1.length; i++) {
			arr1[i] = arr1[i].add(arr2[i]);
		}
		return arr1;
	}

	/**
	 * 数组集体相乘一个倍数
	 * 
	 * @param arr
	 * @param num
	 * @return
	 */
	private static BigInteger[] multiply(BigInteger[] arr, BigInteger num) {
		if (arr == null)
			return null;
		for (int i = 0; i < arr.length; i++) {
			arr[i] = arr[i].multiply(num);
		}
		return arr;
	}

	/**
	 * 求解一个字符串中加入一个新的字符位置分布<br>
	 * 
	 * 对一个定长length的字符中，在一定位置index中的前后（charAt)加入一个字符<br>
	 * 其将产生一个数组，可以记录新加字符所在位置<br>
	 * 在index前加入一个字符时，从0-index之间都有一种可能<br>
	 * 在index后加入一个字符时，从index+1-length之间也有一种可能
	 * 
	 * @param length
	 * @param index
	 * @param charAt
	 * @return
	 */
	private static BigInteger[] child(int length, int index, char charAt) {
		BigInteger[] arr = new BigInteger[length + 1];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = new BigInteger("0");
		}
		if (charAt == 'A') {
			for (int i = index + 1; i <= length; i++) {
				arr[i] = new BigInteger("1");
			}
		} else {
			for (int i = 0; i <= index; i++) {
				arr[i] = new BigInteger("1");
			}
		}
		return arr;
	}

	/**
	 * 取出对应字符所在位置的分布数组<br>
	 * 
	 * 对于一个已经存在的数组分布来说，扩展一个charAt的字符，那么产生的新数组分布也是一定的<br>
	 * 遍历现存的数组分布，对其每个值进行求对应的数组分布可能，并将结果与现在记录个数相乘，累加后的结果即一个全新的数组分布
	 * 
	 * @param sizes
	 * @param charAt
	 * @return
	 */
	private static BigInteger[] step(BigInteger[] sizes, char charAt) {
		BigInteger[] newSizes = new BigInteger[sizes.length + 1];
		for (int i = 0; i < newSizes.length; i++) {
			newSizes[i] = new BigInteger("0");
		}
		for (int i = 0; i < sizes.length; i++) {
			newSizes = add(newSizes, multiply(child(sizes.length, i, charAt), sizes[i]));
		}
		return newSizes;
	}

	/**
	 * 根据AB字符串取出符合条件的个数
	 * 
	 * @param str
	 * @return
	 */
	private static BigInteger test(String str) {
		BigInteger[] sizes = new BigInteger[] { new BigInteger("1") };
		BigInteger sum = new BigInteger("0");
		for (int i = 0; i < str.length(); i++) {
			sizes = step(sizes, str.charAt(i));
		}
		for (int i = 0; i < sizes.length; i++) {
			sum = sum.add(sizes[i]);
		}
		return sum;
	}

	public static void main(String[] args) {
                System.out.println(test("AAA"));
                System.out.println(test("AAB"));
                System.out.println(test("ABA"));
                System.out.println(test("ABAA"));
                System.out.println(test("ABAB"));
                System.out.println(test("AABAAABAAABAAABAAABAAABABB"));
	}
}

 

[结论 ]

       运算结果如下：

1
3
5
9
16
23469961608638992720

 

       查看结果的前几个，还是正确的，就是无法对后面的结论进行验证了，寒。。。

       在使用BigInteger代替int后，不但可以实现对26位数据的计算，那怕是假设为62位，也是秒杀的。

       这个算法最大的好处是不占用内存，那怕对1000的数据计算时，理论上也就约占2x1000多的数组。但是数据约大，计算的时间还是成指数倍的增长了。

       PS：谁想知道1000的数据有多少种可能么？试试就知道了。我的机器上花了7分钟，居然算过来了。。

 

 

 

评论

2 楼 Mrluo 2011-10-19  

1 楼 蔡华江 2010-09-16  

晕，存草稿的，居然直接发布了