我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
你可以使用Asif算法来生成所有可能的组合。这可能是最简单和最有效的方法。你可以在这里查看媒体文章。
让我们看看JavaScript中的实现。
function Combinations( arr, r ) {
// To avoid object referencing, cloning the array.
arr = arr && arr.slice() || [];
var len = arr.length;
if( !len || r > len || !r )
return [ [] ];
else if( r === len )
return [ arr ];
if( r === len ) return arr.reduce( ( x, v ) => {
x.push( [ v ] );
return x;
}, [] );
var head = arr.shift();
return Combinations( arr, r - 1 ).map( x => {
x.unshift( head );
return x;
} ).concat( Combinations( arr, r ) );
}
// Now do your stuff.
console.log( Combinations( [ 'a', 'b', 'c', 'd', 'e' ], 3 ) );
其他回答
作为迭代器对象实现的MetaTrader MQL4非常快速的组合。
代码很容易理解。
我对很多算法进行了基准测试，这个算法真的非常快——大约比大多数next_combination()函数快3倍。
class CombinationsIterator { private: int input_array[]; // 1 2 3 4 5 int index_array[]; // i j k int m_elements; // N int m_indices; // K public: CombinationsIterator(int &src_data[], int k) { m_indices = k; m_elements = ArraySize(src_data); ArrayCopy(input_array, src_data); ArrayResize(index_array, m_indices); // create initial combination (0..k-1) for (int i = 0; i < m_indices; i++) { index_array[i] = i; } } // https://stackoverflow.com/questions/5076695 // bool next_combination(int &item[], int k, int N) bool advance() { int N = m_elements; for (int i = m_indices - 1; i >= 0; --i) { if (index_array[i] < --N) { ++index_array[i]; for (int j = i + 1; j < m_indices; ++j) { index_array[j] = index_array[j - 1] + 1; } return true; } } return false; } void getItems(int &items[]) { // fill items[] from input array for (int i = 0; i < m_indices; i++) { items[i] = input_array[index_array[i]]; } } };
测试上述迭代器类的驱动程序:
//+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ // driver program to test above class #define N 5 #define K 3 void OnStart() { int myset[N] = {1, 2, 3, 4, 5}; int items[K]; CombinationsIterator comboIt(myset, K); do { comboIt.getItems(items); printf("%s", ArrayToString(items)); } while (comboIt.advance()); }
输出: 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
你可以使用Asif算法来生成所有可能的组合。这可能是最简单和最有效的方法。你可以在这里查看媒体文章。
让我们看看JavaScript中的实现。
function Combinations( arr, r ) {
// To avoid object referencing, cloning the array.
arr = arr && arr.slice() || [];
var len = arr.length;
if( !len || r > len || !r )
return [ [] ];
else if( r === len )
return [ arr ];
if( r === len ) return arr.reduce( ( x, v ) => {
x.push( [ v ] );
return x;
}, [] );
var head = arr.shift();
return Combinations( arr, r - 1 ).map( x => {
x.unshift( head );
return x;
} ).concat( Combinations( arr, r ) );
}
// Now do your stuff.
console.log( Combinations( [ 'a', 'b', 'c', 'd', 'e' ], 3 ) );
我在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;
}
像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
下面是我的Scala解决方案:
def combinations[A](s: List[A], k: Int): List[List[A]] =
if (k > s.length) Nil
else if (k == 1) s.map(List(_))
else combinations(s.tail, k - 1).map(s.head :: _) ::: combinations(s.tail, k)
