算法-有n个数从中取出r个数

Question

比如1,2,3,4,5,6,6个数，取出3个数
1-2-3，1-2-4，1-2-5，1-2-6，1-3-4，1-3-5，1-3-6，1-4-5，1-4-6，1-5-6
2-3-4，2-3-5，2-3-6，2-4-5，2-4-6，2-5-6
3-4-5，3-4-6
4-5-6
找出其中的所有可能组合，要求不重复，无顺序要求

Answer 1

首先构造一个n个节点的有向图，用邻接表表示，为表达方便，顶点编号为0，n-1。
做深度优先搜索，当深度达到m是，表示找到一个满足要求的组合。否则回溯。
这个算法不能打出m=1的情况。

#!/usr/bin/env python
import sys
class Digraph(object):
def __init__( self, n, m ):
self.v = [ [ j for j in xrange( i + 1 , n ) ] for i in xrange( 0, n ) ]
self.m = m
self.queue = []

def dfs(self):
for i, adj in enumerate( self.v ):
self.queue.append( i )
self.dfs_from_one( i )
self.queue.pop()
def dfs_from_one( self, v ):
for j in self.v[v]:
self.queue.append( j )
if len( self.queue ) == self.m:
print self.queue
else:
self.dfs_from_one( j )
self.queue.pop()

def printDigraph(self):
print "Digraph:"
for i, adj in enumerate( self.v ):
print str(i) + "-->" + str(adj)

if __name__ == "__main__":
n, m = int( sys.argv[1] ), int( sys.argv[2] )
g = Digraph( n, m )
g.printDigraph()
print "m elements out of n:"
g.dfs()

$ ./nm.py 6 3
Digraph:
0-->[1, 2, 3, 4, 5]
1-->[2, 3, 4, 5]
2-->[3, 4, 5]
3-->[4, 5]
4-->[5]
5-->[]
m elements out of n:
[0, 1, 2]
[0, 1, 3]
[0, 1, 4]
[0, 1, 5]
[0, 2, 3]
[0, 2, 4]
[0, 2, 5]
[0, 3, 4]
[0, 3, 5]
[0, 4, 5]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]

Answer 2

通过一个额外的含有r个元素的数组来保存中间查找的结果，然后在某一个组合的所有数字完全查找到之后，就可以输出该组合了，然后进行下一个组合的查找了。
迭代对于这个问题很有帮助。find(index, num)表示从原始数组a中的第index项开始查找出num个数。通过调用find(0, r)即可完成所有组合的查找。具体实现代码如下，里面有很详细的注释。

 private int n = 6;
private int r = 3;
private int a[] = {1, 2, 3, 4, 5, 6}; //原数组
private int b[] = new int[r]; //存储组合结果的数组

/**
*
* @param index 从数组a中第index项开始查找
* @param num 还需要查找的个数，当num==1时，说明本次查找
* 是某一个组合的最后一个数字的查找了，
* 此时查找到数字了之后，就可以输出该组合并进行下一组合的查找了
*/
public void find(int index, int num) {
for (int i = index; i < a.length - num + 1; i++) {
b[r - num] = a[i]; //本次查找到的数，保存在组合数组b对应的位置上
if (num == 1) { //某一个组合的所有数字已经全部查找完毕，可以输出了
for (int j = 0; j < r; j++) {
System.out.print(b[j] + "-");
}
System.out.println();
} else {
find(i + 1, num - 1); //继续本次组合的下一个数的查找
}
}
}

Answer 3

递归深搜。

定义函数 Search（int i， int k）
Search 要完成的任务是，从数组arr的第i个元素开始，找到第k个输出元素的所有情况，每次将其输出到tmp数组的第k个元素上，然后递归下去。

#include <stdio.h>

int r=3;
int n=6;
int arr[] = {1,2,3,4,5,6};
int tmp[3] = {0};

void Search(int i, int k)
{
for (int idx = i; idx < n; ++idx)
{
tmp[k] = arr[idx];
if (k+1 == r){
// PRINT TMP ARRAY
}
else if (k+1 < r){
Search(idx+1, k+1);
}
}
}

int main() {
Search(0,0);
}

Answer 4

$data = array(1,2,3,4,5,6);
foreach ($data as $item){
return2($item);
}
function return2($key){
global $data;
foreach ($data as $item){
if ($key>=$item) continue;
return3($key,$item);
}
}
function return3($key,$key1){
global $data;
foreach ($data as $item){
if ($item <= $key || $item <= $key1 ) continue;
echo $key.'-'.$key1.'-'.$item.'<br/>';
}
}
也可以递归整理一下,不过这样容易看懂.