我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
下面是我的JavaScript解决方案,通过使用reduce/map,它消除了几乎所有变量,功能更强大
function combinations(arr, size) { var len = arr.length; if (size > len) return []; if (!size) return [[]]; if (size == len) return [arr]; return arr.reduce(function (acc, val, i) { var res = combinations(arr.slice(i + 1), size - 1) .map(function (comb) { return [val].concat(comb); }); return acc.concat(res); }, []); } var combs = combinations([1,2,3,4,5,6,7,8],3); combs.map(function (comb) { document.body.innerHTML += comb.toString() + '<br />'; }); document.body.innerHTML += '<br /> Total combinations = ' + combs.length;
其他回答
这是我想出的解决这个问题的算法。它是用c++编写的,但是可以适应几乎任何支持位操作的语言。
void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
你可以在这里看到它如何工作的解释。
我的实现在c/c++
#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
int opt = -1, min_len = 0, max_len = 0;
char ofile[256], fchar[2], tchar[2];
ofile[0] = 0;
fchar[0] = 0;
tchar[0] = 0;
while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
{
switch(opt)
{
case 'o':
strncpy(ofile, optarg, 255);
break;
case 'f':
strncpy(fchar, optarg, 1);
break;
case 't':
strncpy(tchar, optarg, 1);
break;
case 'l':
min_len = atoi(optarg);
break;
case 'L':
max_len = atoi(optarg);
break;
default:
printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
}
}
if(max_len < 1)
{
printf("error, length must be more than 0\n");
return 1;
}
if(min_len > max_len)
{
printf("error, max length must be greater or equal min_length\n");
return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
printf("error, invalid range specified\n");
return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
printf("failed to open input file with error: %s\n", strerror(errno));
return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
char buf[cur_len];
for(int i = 0; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
while(buf[0] != (tchar[0]+1))
{
while(buf[cur_len-1] < tchar[0])
{
(int)buf[cur_len-1]++;
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
if(cur_len < 2)
break;
if(buf[0] == tchar[0])
{
bool stop = true;
for(int i = 1; i < cur_len; i++)
{
if(buf[i] != tchar[0])
{
stop = false;
break;
}
}
if(stop)
break;
}
int u = cur_len-2;
for(; u>=0 && buf[u] >= tchar[0]; u--)
;
(int)buf[u]++;
for(int i = u+1; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
cur_len++;
}
fclose(out);
return 0;
}
这里我的实现在c++,它写所有的组合到指定的文件,但行为可以改变,我在生成各种字典,它接受最小和最大长度和字符范围,目前只有ANSI支持,它足以满足我的需求
像Andrea Ambu一样用Python写的,但不是硬编码来选择三个。
def combinations(list, k):
"""Choose combinations of list, choosing k elements(no repeats)"""
if len(list) < k:
return []
else:
seq = [i for i in range(k)]
while seq:
print [list[index] for index in seq]
seq = get_next_combination(len(list), k, seq)
def get_next_combination(num_elements, k, seq):
index_to_move = find_index_to_move(num_elements, seq)
if index_to_move == None:
return None
else:
seq[index_to_move] += 1
#for every element past this sequence, move it down
for i, elem in enumerate(seq[(index_to_move+1):]):
seq[i + 1 + index_to_move] = seq[index_to_move] + i + 1
return seq
def find_index_to_move(num_elements, seq):
"""Tells which index should be moved"""
for rev_index, elem in enumerate(reversed(seq)):
if elem < (num_elements - rev_index - 1):
return len(seq) - rev_index - 1
return None
简短的java解决方案:
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
结果将是
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]
为此,我在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)