我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。

假设您提供了一个包含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;

其他回答

简短javascript版本(es5)

令combine = (list, n) => N == 0 ? [[]]: 列表。flatMap((e, i) => 结合( 列表。切片(i + 1) N - 1 ).Map (c => [e].concat(c)) ); Let res = combine([1,2,3,4], 3); res.forEach(e => console.log(e.join()));

如果你可以使用SQL语法——比如,如果你使用LINQ访问一个结构或数组的字段,或者直接访问一个数据库,其中有一个名为“Alphabet”的表,只有一个字符字段“Letter”,你可以适应以下代码:

SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter

这将返回所有3个字母的组合,不管你在表格“字母表”中有多少个字母(它可以是3,8,10,27等)。

如果你想要的是所有的排列,而不是组合(也就是说,你想要“ACB”和“ABC”被视为不同的,而不是只出现一次),只需删除最后一行(and一行),就完成了。

Post-Edit:重新阅读问题后,我意识到需要的是通用算法,而不仅仅是选择3个项目的特定算法。Adam Hughes的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。

static IEnumerable<string> Combinations(List<string> characters, int length)
{
    for (int i = 0; i < characters.Count; i++)
    {
        // only want 1 character, just return this one
        if (length == 1)
            yield return characters[i];

        // want more than one character, return this one plus all combinations one shorter
        // only use characters after the current one for the rest of the combinations
        else
            foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
                yield return characters[i] + next;
    }
}

在Python中,利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合,这将占用大量内存,但其优点是初始集合可以是一个复杂的对象。它只会找到唯一的组合。

import copy

def find_combinations( length, set, combinations = None, candidate = None ):
    # recursive function to calculate all unique combinations of unique values
    # from [set], given combinations of [length].  The result is populated
    # into the 'combinations' list.
    #
    if combinations == None:
        combinations = []
    if candidate == None:
        candidate = []

    for item in set:
        if item in candidate:
            # this item already appears in the current combination somewhere.
            # skip it
            continue

        attempt = copy.deepcopy(candidate)
        attempt.append(item)
        # sorting the subset is what gives us completely unique combinations,
        # so that [1, 2, 3] and [1, 3, 2] will be treated as equals
        attempt.sort()

        if len(attempt) < length:
            # the current attempt at finding a new combination is still too
            # short, so add another item to the end of the set
            # yay recursion!
            find_combinations( length, set, combinations, attempt )
        else:
            # the current combination attempt is the right length.  If it
            # already appears in the list of found combinations then we'll
            # skip it.
            if attempt in combinations:
                continue
            else:
                # otherwise, we append it to the list of found combinations
                # and move on.
                combinations.append(attempt)
                continue
    return len(combinations)

你可以这样使用它。传递'result'是可选的,所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。

size = 3
set = [1, 2, 3, 4, 5]
result = []

num = find_combinations( size, set, result ) 
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)

您应该从测试数据中得到以下输出:

size 3 results in 10 sets
result: [[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]]

如果你的集合是这样的,它也会工作得很好:

set = [
    [ 'vanilla', 'cupcake' ],
    [ 'chocolate', 'pudding' ],
    [ 'vanilla', 'pudding' ],
    [ 'chocolate', 'cookie' ],
    [ 'mint', 'cookie' ]
]

基于java解决方案的短php算法返回k元素从n(二项式系数)的所有组合:

$array = array(1,2,3,4,5);

$array_result = NULL;

$array_general = NULL;

function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
    if($len == 0)
    {
        $general_array[] = $result_array;
        return;
    }

    for ($i = $start_position; $i <= count($array) - $len; $i++)
    {
        $result_array[$result_len - $len] = $array[$i];
        combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
    }
} 

combinations($array, 3, 0, $array_result, 3, $array_general);

echo "<pre>";
print_r($array_general);
echo "</pre>";

相同的解决方案,但在javascript:

var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];

function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
    if(len === 0) {
        var tempArray = [];
        resultArray.forEach(value => tempArray.push(value));
        arrayGeneral.push(tempArray);
        return;
    }
    for (var i = startPosition; i <= newArray.length - len; i++) {
        resultArray[resultLen - len] = newArray[i];
        combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
    }
} 

combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);

console.log(arrayGeneral);