我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
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;
}
其他回答
也许我错过了重点(你需要的是算法,而不是现成的解决方案),但看起来scala已经开箱即用了(现在):
def combis(str:String, k:Int):Array[String] = {
str.combinations(k).toArray
}
使用这样的方法:
println(combis("abcd",2).toList)
会产生:
List(ab, ac, ad, bc, bd, cd)
基于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);
简短快速的c#实现
public static IEnumerable<IEnumerable<T>> Combinations<T>(IEnumerable<T> elements, int k)
{
return Combinations(elements.Count(), k).Select(p => p.Select(q => elements.ElementAt(q)));
}
public static List<int[]> Combinations(int setLenght, int subSetLenght) //5, 3
{
var result = new List<int[]>();
var lastIndex = subSetLenght - 1;
var dif = setLenght - subSetLenght;
var prevSubSet = new int[subSetLenght];
var lastSubSet = new int[subSetLenght];
for (int i = 0; i < subSetLenght; i++)
{
prevSubSet[i] = i;
lastSubSet[i] = i + dif;
}
while(true)
{
//add subSet ad result set
var n = new int[subSetLenght];
for (int i = 0; i < subSetLenght; i++)
n[i] = prevSubSet[i];
result.Add(n);
if (prevSubSet[0] >= lastSubSet[0])
break;
//start at index 1 because index 0 is checked and breaking in the current loop
int j = 1;
for (; j < subSetLenght; j++)
{
if (prevSubSet[j] >= lastSubSet[j])
{
prevSubSet[j - 1]++;
for (int p = j; p < subSetLenght; p++)
prevSubSet[p] = prevSubSet[p - 1] + 1;
break;
}
}
if (j > lastIndex)
prevSubSet[lastIndex]++;
}
return result;
}
不需要进行集合操作。这个问题几乎和循环K个嵌套循环一样,但你必须小心索引和边界(忽略Java和OOP的东西):
public class CombinationsGen {
private final int n;
private final int k;
private int[] buf;
public CombinationsGen(int n, int k) {
this.n = n;
this.k = k;
}
public void combine(Consumer<int[]> consumer) {
buf = new int[k];
rec(0, 0, consumer);
}
private void rec(int index, int next, Consumer<int[]> consumer) {
int max = n - index;
if (index == k - 1) {
for (int i = 0; i < max && next < n; i++) {
buf[index] = next;
next++;
consumer.accept(buf);
}
} else {
for (int i = 0; i < max && next + index < n; i++) {
buf[index] = next;
next++;
rec(index + 1, next, consumer);
}
}
}
}
像这样使用:
CombinationsGen gen = new CombinationsGen(5, 2);
AtomicInteger total = new AtomicInteger();
gen.combine(arr -> {
System.out.println(Arrays.toString(arr));
total.incrementAndGet();
});
System.out.println(total);
获得预期的结果:
[0, 1]
[0, 2]
[0, 3]
[0, 4]
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
10
最后,将索引映射到您可能拥有的任何数据集。
遵循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