我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
Array.prototype.combs = function(num) {
var str = this,
length = str.length,
of = Math.pow(2, length) - 1,
out, combinations = [];
while(of) {
out = [];
for(var i = 0, y; i < length; i++) {
y = (1 << i);
if(y & of && (y !== of))
out.push(str[i]);
}
if (out.length >= num) {
combinations.push(out);
}
of--;
}
return combinations;
}
其他回答
我在c++中为组合创建了一个通用类。 它是这样使用的。
char ar[] = "0ABCDEFGH";
nCr ncr(8, 3);
while(ncr.next()) {
for(int i=0; i<ncr.size(); i++) cout << ar[ncr[i]];
cout << ' ';
}
我的库ncr[i]从1返回,而不是从0返回。 这就是为什么数组中有0。 如果你想考虑订单,只需将nCr class改为nPr即可。 用法是相同的。
结果
美国广播公司 ABD 安倍 沛富 ABG ABH 澳洲牧牛犬 王牌 ACF ACG 呵呀 正面 ADF ADG 抗利尿激素 时 AEG AEH 二自由度陀螺仪 AFH 啊 BCD 公元前 供应量 波士顿咨询公司 BCH 12 快速公车提供 BDG BDH 性能试验 求 本· 高炉煤气 BFH 使用BGH CDE 提供 CDG 鼎晖 欧共体语言教学大纲的 CEG 另一 CFG CFH 全息 DEF 度 电气设施 脱硫 干扰 DGH EFG EFH EGH FGH
下面是头文件。
#pragma once
#include <exception>
class NRexception : public std::exception
{
public:
virtual const char* what() const throw() {
return "Combination : N, R should be positive integer!!";
}
};
class Combination
{
public:
Combination(int n, int r);
virtual ~Combination() { delete [] ar;}
int& operator[](unsigned i) {return ar[i];}
bool next();
int size() {return r;}
static int factorial(int n);
protected:
int* ar;
int n, r;
};
class nCr : public Combination
{
public:
nCr(int n, int r);
bool next();
int count() const;
};
class nTr : public Combination
{
public:
nTr(int n, int r);
bool next();
int count() const;
};
class nHr : public nTr
{
public:
nHr(int n, int r) : nTr(n,r) {}
bool next();
int count() const;
};
class nPr : public Combination
{
public:
nPr(int n, int r);
virtual ~nPr() {delete [] on;}
bool next();
void rewind();
int count() const;
private:
bool* on;
void inc_ar(int i);
};
以及执行。
#include "combi.h"
#include <set>
#include<cmath>
Combination::Combination(int n, int r)
{
//if(n < 1 || r < 1) throw NRexception();
ar = new int[r];
this->n = n;
this->r = r;
}
int Combination::factorial(int n)
{
return n == 1 ? n : n * factorial(n-1);
}
int nPr::count() const
{
return factorial(n)/factorial(n-r);
}
int nCr::count() const
{
return factorial(n)/factorial(n-r)/factorial(r);
}
int nTr::count() const
{
return pow(n, r);
}
int nHr::count() const
{
return factorial(n+r-1)/factorial(n-1)/factorial(r);
}
nCr::nCr(int n, int r) : Combination(n, r)
{
if(r == 0) return;
for(int i=0; i<r-1; i++) ar[i] = i + 1;
ar[r-1] = r-1;
}
nTr::nTr(int n, int r) : Combination(n, r)
{
for(int i=0; i<r-1; i++) ar[i] = 1;
ar[r-1] = 0;
}
bool nCr::next()
{
if(r == 0) return false;
ar[r-1]++;
int i = r-1;
while(ar[i] == n-r+2+i) {
if(--i == -1) return false;
ar[i]++;
}
while(i < r-1) ar[i+1] = ar[i++] + 1;
return true;
}
bool nTr::next()
{
ar[r-1]++;
int i = r-1;
while(ar[i] == n+1) {
ar[i] = 1;
if(--i == -1) return false;
ar[i]++;
}
return true;
}
bool nHr::next()
{
ar[r-1]++;
int i = r-1;
while(ar[i] == n+1) {
if(--i == -1) return false;
ar[i]++;
}
while(i < r-1) ar[i+1] = ar[i++];
return true;
}
nPr::nPr(int n, int r) : Combination(n, r)
{
on = new bool[n+2];
for(int i=0; i<n+2; i++) on[i] = false;
for(int i=0; i<r; i++) {
ar[i] = i + 1;
on[i] = true;
}
ar[r-1] = 0;
}
void nPr::rewind()
{
for(int i=0; i<r; i++) {
ar[i] = i + 1;
on[i] = true;
}
ar[r-1] = 0;
}
bool nPr::next()
{
inc_ar(r-1);
int i = r-1;
while(ar[i] == n+1) {
if(--i == -1) return false;
inc_ar(i);
}
while(i < r-1) {
ar[++i] = 0;
inc_ar(i);
}
return true;
}
void nPr::inc_ar(int i)
{
on[ar[i]] = false;
while(on[++ar[i]]);
if(ar[i] != n+1) on[ar[i]] = true;
}
遵循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
假设你的字母数组是这样的:"ABCDEFGH"。你有三个下标(i, j, k)来表示你要用哪个字母来表示当前单词。
A B C D E F G H ^ ^ ^ i j k
首先你改变k,所以下一步看起来像这样:
A B C D E F G H ^ ^ ^ i j k
如果你到达终点,你继续改变j和k。
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k
一旦j达到G, i也开始变化。
A B C D E F G H ^ ^ ^ i j k A B C D E F G H ^ ^ ^ i j k ...
function initializePointers($cnt) {
$pointers = [];
for($i=0; $i<$cnt; $i++) {
$pointers[] = $i;
}
return $pointers;
}
function incrementPointers(&$pointers, &$arrLength) {
for($i=0; $i<count($pointers); $i++) {
$currentPointerIndex = count($pointers) - $i - 1;
$currentPointer = $pointers[$currentPointerIndex];
if($currentPointer < $arrLength - $i - 1) {
++$pointers[$currentPointerIndex];
for($j=1; ($currentPointerIndex+$j)<count($pointers); $j++) {
$pointers[$currentPointerIndex+$j] = $pointers[$currentPointerIndex]+$j;
}
return true;
}
}
return false;
}
function getDataByPointers(&$arr, &$pointers) {
$data = [];
for($i=0; $i<count($pointers); $i++) {
$data[] = $arr[$pointers[$i]];
}
return $data;
}
function getCombinations($arr, $cnt)
{
$len = count($arr);
$result = [];
$pointers = initializePointers($cnt);
do {
$result[] = getDataByPointers($arr, $pointers);
} while(incrementPointers($pointers, count($arr)));
return $result;
}
$result = getCombinations([0, 1, 2, 3, 4, 5], 3);
print_r($result);
基于https://stackoverflow.com/a/127898/2628125,但更抽象,适用于任何大小的指针。
简短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()));
一个简洁的Javascript解决方案:
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);