计算从N个数字中取K个数字的结果集


一般情况下，如果从N个数字中抽取K个数字，使用下列公式得到结果
计算公式：
[ N * (N-1)* (N-2) * ... * ( N -K + 1) ] / ( 1*2*3*...*K)
例，从1~50之间的数字中抽取6个数字来抽奖，那么可能的结果会是：
( 50 * 49 * 48 * 47 * 46 * 45 ) / (1 * 2 * 3 * 4 * 5 * 6  ) 

哈，申请了这个blog好久也没有在上面写东西（太懒），今天回答了一个问题觉得字挺多的，搬到这里来。
原贴地址：http://community.csdn.net/Expert/topic/4746/4746331.xml?temp=.4790308
哈这个问题有点意思，我自认为小学的时候数学还可以哈哈，来讨论一下。
可以模拟手算的算法：
先简化问题，从2/3问题开始
先排序1.2.3
取出1然后还需要再取一个数字可以是2.可以是3这样我们得到[1.2][1.3]所有含有1的二元组已经取到。
然后我们列举所有含2的二元组，取出2还要再取一个数字，注意这里有一个要点我们只可以向后取不可以向前取，这是为了不产生重复的二元组，理解这个要点对解决这个问题很重要。所以这里只可以取3得到[2.3]
下面我们取所有含有3的组合，取出3根据向后取的原则，我们发现已经没有可以取到的数字了。这样这个问题就结束了我们得到结果[1.2][1.3][2.3]
下面我们把这个问题扩展一下变成3/4问题
排序:1.2.3.4
先列举含有1的三元组，取出1，这里另外一个要点来了，我们的任务转化成为要在2.3.4中取出所有的2元组然后和1组成三元组这样这里转化为2/3问题，之后我们取所有含2的三元组，注意只能向后取的原则，问题转化为在3.4中取2元组的2/2问题
看到这里我们应该可以理解手算的操作方法了。
要把这个操作改写成计算机算法并不复杂。
result_array fn(source_array,start,end,n)
实现这样一个递归函数就可以了
result_array 是一个list内容是所有要求的n元组,source_array是原始的元素集合，start,end表明了区间，n是n元组的n,这样做是为了节省空间，免得每次递归都要复制出一个array作为取值元素集合。
方法里面的内容：
哈哈大家补充，不复杂的。
基本上是一个循环
先判断n是否=1 是就把所有元素放到一个list中返回，如果不是的话
对每一个元素如果他右面的元素>=n-1那么就对右面的元素调用fn(source_array,当前位置+1,末尾,n-1)那返回结果和元素组合放进一个list中，如果小于n-1了那么跳出循环返回这个list。
就这样了。

python四个数中取三个数组成互不相同且没有重复数字的三位数
问：有1，2，3，4四个数字，能够组成多少个互不相同而且无重复数字的三位数？都是多少？
最简单就是下面的这种：
nums=[]
 for i in range(1,5):
      for j in range(1,5):
           for k in range(1,5):
             if i!=j and i!=k and j!=k:
                 num=i*100+j*10+k
                 if num not in nums:
                     nums.append(num)
 print(nums)
 

输出结果：
[123, 124, 132, 134, 142, 143, 213, 214, 231, 234, 241, 243, 312, 314, 321, 324, 341, 342, 412, 413, 421, 423, 431, 432]

当然可以加一个count来计数：

方法1：
要从M个数字中随机取N个数，最直接的想法把已经取得的随机数存储起来，
每次随机取一个数，
在存储的随机数中如果能够找到，就要重新再取，
直到取到足够数量的随机数。
这个方法的好处是容易理解，容易实现。
但它的时间性能是O(N2)，因为存在一个2重循环。如果样本较多，时间会急剧增加。


方法2：
在外层循环难以避免的情况下，把内层循环换成固定时间的算法。代码如下：
即：每次生成随机数后，会进行一次交换。使得已生成随机数的序号与未生成随机数的序号分离开来。
而序号与数值仍然保持一一对应。代码如下：

    public static void getRandom(int[] buffer) {
        final int n = buffer.length;
        for(int ii = 0;ii < n;ii ++) {
            buffer[ii] = ii;
        }

        Random random = new Random();
        final int half = n/2;
        for(int jj = 0;jj < half;jj ++) {
            int pos = random.nextInt(n - jj) + jj;
            int tmp = buffer[jj];
            buffer[jj] = buffer[pos];
            buffer[pos] = tmp;
        }
    }