我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
基于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);
其他回答
我有一个用于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
遵循Haskell代码同时计算组合数和组合,由于Haskell的惰性,您可以得到其中的一部分而无需计算另一部分。
import Data.Semigroup
import Data.Monoid
data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)
instance Semigroup Comb where
(MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)
instance Monoid Comb where
mempty = MkComb 0 []
addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)
comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))
它是这样工作的:
*Main> comb 0 1
MkComb {count = 0, combinations = []}
*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}
*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}
*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}
*Main> count (comb 10 5)
252
Here's some simple code that prints all the C(n,m) combinations. It works by initializing and moving a set of array indices that point to next valid combination. The indices are initialized to point to the lowest m indices (lexicographically the smallest combination). Then on, starting with the m-th index, we try to move the indices forward. if an index has reached its limit, we try the previous index (all the way down to index 1). If we can move an index forward, then we reset all greater indices.
m=(rand()%n)+1; // m will vary from 1 to n
for (i=0;i<n;i++) a[i]=i+1;
// we want to print all possible C(n,m) combinations of selecting m objects out of n
printf("Printing C(%d,%d) possible combinations ...\n", n,m);
// This is an adhoc algo that keeps m pointers to the next valid combination
for (i=0;i<m;i++) p[i]=i; // the p[.] contain indices to the a vector whose elements constitute next combination
done=false;
while (!done)
{
// print combination
for (i=0;i<m;i++) printf("%2d ", a[p[i]]);
printf("\n");
// update combination
// method: start with p[m-1]. try to increment it. if it is already at the end, then try moving p[m-2] ahead.
// if this is possible, then reset p[m-1] to 1 more than (the new) p[m-2].
// if p[m-2] can not also be moved, then try p[m-3]. move that ahead. then reset p[m-2] and p[m-1].
// repeat all the way down to p[0]. if p[0] can not also be moved, then we have generated all combinations.
j=m-1;
i=1;
move_found=false;
while ((j>=0) && !move_found)
{
if (p[j]<(n-i))
{
move_found=true;
p[j]++; // point p[j] to next index
for (k=j+1;k<m;k++)
{
p[k]=p[j]+(k-j);
}
}
else
{
j--;
i++;
}
}
if (!move_found) done=true;
}
void combine(char a[], int N, int M, int m, int start, char result[]) {
if (0 == m) {
for (int i = M - 1; i >= 0; i--)
std::cout << result[i];
std::cout << std::endl;
return;
}
for (int i = start; i < (N - m + 1); i++) {
result[m - 1] = a[i];
combine(a, N, M, m-1, i+1, result);
}
}
void combine(char a[], int N, int M) {
char *result = new char[M];
combine(a, N, M, M, 0, result);
delete[] result;
}
在第一个函数中,m表示还需要选择多少个,start表示必须从数组中的哪个位置开始选择。
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;
}
}