我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
算法:
从1数到2^n。 将每个数字转换为二进制表示。 根据位置,将每个“on”位转换为集合中的元素。
在c#中:
void Main()
{
var set = new [] {"A", "B", "C", "D" }; //, "E", "F", "G", "H", "I", "J" };
var kElement = 2;
for(var i = 1; i < Math.Pow(2, set.Length); i++) {
var result = Convert.ToString(i, 2).PadLeft(set.Length, '0');
var cnt = Regex.Matches(Regex.Escape(result), "1").Count;
if (cnt == kElement) {
for(int j = 0; j < set.Length; j++)
if ( Char.GetNumericValue(result[j]) == 1)
Console.Write(set[j]);
Console.WriteLine();
}
}
}
为什么它能起作用?
在n元素集的子集和n位序列之间存在双射。
这意味着我们可以通过数数序列来计算出有多少个子集。
例如,下面的四个元素集可以用{0,1}X {0,1} X {0,1} X{0,1}(或2^4)个不同的序列表示。
我们要做的就是从1数到2^n来找到所有的组合。(我们忽略空集。)接下来,将数字转换为二进制表示。然后将集合中的元素替换为“on”位。
如果只需要k个元素的结果,则只在k位为“on”时打印。
(如果你想要所有的子集,而不是k长度的子集,删除cnt/kElement部分。)
(有关证明,请参阅麻省理工学院免费课件计算机科学数学,雷曼等,第11.2.2节。https://ocw.mit.edu/courses/electrical -工程-和-计算机- science/6 - 042 j -数学- -计算机科学-下降- 2010/readings/)
其他回答
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表示必须从数组中的哪个位置开始选择。
我在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;
}
下面是我的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)
这是我对javascript的贡献(没有递归)
set = ["q0", "q1", "q2", "q3"]
collector = []
function comb(num) {
results = []
one_comb = []
for (i = set.length - 1; i >= 0; --i) {
tmp = Math.pow(2, i)
quotient = parseInt(num / tmp)
results.push(quotient)
num = num % tmp
}
k = 0
for (i = 0; i < results.length; ++i)
if (results[i]) {
++k
one_comb.push(set[i])
}
if (collector[k] == undefined)
collector[k] = []
collector[k].push(one_comb)
}
sum = 0
for (i = 0; i < set.length; ++i)
sum += Math.pow(2, i)
for (ii = sum; ii > 0; --ii)
comb(ii)
cnt = 0
for (i = 1; i < collector.length; ++i) {
n = 0
for (j = 0; j < collector[i].length; ++j)
document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
document.write("<hr>")
}
下面是Clojure版本,它使用了我在OCaml实现答案中描述的相同算法:
(defn select
([items]
(select items 0 (inc (count items))))
([items n1 n2]
(reduce concat
(map #(select % items)
(range n1 (inc n2)))))
([n items]
(let [
lmul (fn [a list-of-lists-of-bs]
(map #(cons a %) list-of-lists-of-bs))
]
(if (= n (count items))
(list items)
(if (empty? items)
items
(concat
(select n (rest items))
(lmul (first items) (select (dec n) (rest items)))))))))
它提供了三种调用方法:
(a)按问题要求,选出n项:
user=> (count (select 3 "abcdefgh"))
56
(b) n1至n2个选定项目:
user=> (select '(1 2 3 4) 2 3)
((3 4) (2 4) (2 3) (1 4) (1 3) (1 2) (2 3 4) (1 3 4) (1 2 4) (1 2 3))
(c)在0至所选项目的集合大小之间:
user=> (select '(1 2 3))
(() (3) (2) (1) (2 3) (1 3) (1 2) (1 2 3))