我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
由于没有提到编程语言,我假设列表也是可以的。下面是一个OCaml版本,适用于短列表(非尾递归)。给定一个包含任意类型元素的列表l和一个整数n,如果我们假设结果列表中元素的顺序被忽略,它将返回一个包含l的n个元素的所有可能列表的列表,即list ['a';'b']与['b';'a']相同,并且将报告一次。因此,结果列表的大小将是((list。长度l)选择n)。
递归的直观原理如下:取列表的头,然后进行两次递归调用:
递归调用1 (RC1):到列表的尾部,但选择n-1个元素 递归调用2 (RC2):到列表的尾部,但选择n个元素
要组合递归结果,list-乘(请使用奇数名称)列表的头部与RC1的结果,然后附加(@)RC2的结果。List-multiply是如下操作lmul:
a lmul [ l1 ; l2 ; l3] = [a::l1 ; a::l2 ; a::l3]
Lmul在下面的代码中实现
List.map (fun x -> h::x)
当列表的大小等于您想要选择的元素数量时,递归将终止,在这种情况下,您只需返回列表本身。
下面是OCaml中实现上述算法的四行代码:
let rec choose l n = match l, (List.length l) with
| _, lsize when n==lsize -> [l]
| h::t, _ -> (List.map (fun x-> h::x) (choose t (n-1))) @ (choose t n)
| [], _ -> []
其他回答
我有一个用于project euler的排列算法,用python编写:
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
If
n<len(l)
你应该有所有你需要的组合,没有重复,你需要吗?
它是一个生成器,所以你可以这样使用它:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
作为迭代器对象实现的MetaTrader MQL4非常快速的组合。
代码很容易理解。
我对很多算法进行了基准测试,这个算法真的非常快——大约比大多数next_combination()函数快3倍。
class CombinationsIterator { private: int input_array[]; // 1 2 3 4 5 int index_array[]; // i j k int m_elements; // N int m_indices; // K public: CombinationsIterator(int &src_data[], int k) { m_indices = k; m_elements = ArraySize(src_data); ArrayCopy(input_array, src_data); ArrayResize(index_array, m_indices); // create initial combination (0..k-1) for (int i = 0; i < m_indices; i++) { index_array[i] = i; } } // https://stackoverflow.com/questions/5076695 // bool next_combination(int &item[], int k, int N) bool advance() { int N = m_elements; for (int i = m_indices - 1; i >= 0; --i) { if (index_array[i] < --N) { ++index_array[i]; for (int j = i + 1; j < m_indices; ++j) { index_array[j] = index_array[j - 1] + 1; } return true; } } return false; } void getItems(int &items[]) { // fill items[] from input array for (int i = 0; i < m_indices; i++) { items[i] = input_array[index_array[i]]; } } };
测试上述迭代器类的驱动程序:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // driver program to test above class #define N 5 #define K 3 void OnStart() { int myset[N] = {1, 2, 3, 4, 5}; int items[K]; CombinationsIterator comboIt(myset, K); do { comboIt.getItems(items); printf("%s", ArrayToString(items)); } while (comboIt.advance()); }
输出: 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
为此,我在SQL Server 2005中创建了一个解决方案,并将其发布在我的网站上:http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
下面是一个例子来说明用法:
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
结果:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
下面是一个方法,它从一个随机长度的字符串中给出指定大小的所有组合。类似于昆玛斯的解,但适用于不同的输入和k。
代码可以更改为换行,即'dab'从输入'abcd' w k=3。
public void run(String data, int howMany){
choose(data, howMany, new StringBuffer(), 0);
}
//n choose k
private void choose(String data, int k, StringBuffer result, int startIndex){
if (result.length()==k){
System.out.println(result.toString());
return;
}
for (int i=startIndex; i<data.length(); i++){
result.append(data.charAt(i));
choose(data,k,result, i+1);
result.setLength(result.length()-1);
}
}
"abcde"的输出:
ABC abd ace ade BCD bce bde cde
#include <stdio.h>
unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;
if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}
typedef void(*printfn)(const void *, FILE *);
void print_set(const unsigned int *ar, size_t len, const void **elements,
const char *brackets, printfn print, FILE *fptr)
{
unsigned int i;
fputc(brackets[0], fptr);
for (i = 0; i < len; i++) {
print(elements[ar[i]], fptr);
if (i < len - 1) {
fputs(", ", fptr);
}
}
fputc(brackets[1], fptr);
}
int main(void)
{
unsigned int numbers[] = { 0, 1, 2 };
char *elements[] = { "a", "b", "c", "d", "e" };
const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
const unsigned int n = sizeof(elements) / sizeof(const char*);
do {
print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
putchar('\n');
} while (next_combination(numbers, n, k));
getchar();
return 0;
}