我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由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
简单但缓慢的c++回溯算法。
#include <iostream>
void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;
return;
}
if (s > n)
{
return;
}
numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}
int main(int argc, char* argv[])
{
int n = 5;
int k = 3;
int* numbers = new int[k];
backtrack(numbers, n, k, 0, 1);
delete[] numbers;
return 0;
}
简短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()));
Python中的简短示例:
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
为了解释,递归方法用下面的例子描述:
示例:A B C D E 3的所有组合是:
A与其余2的所有组合(B C D E) B与其余2的所有组合(C D E) C与其余2的所有组合(D E)
这里你有一个用c#编写的该算法的惰性评估版本:
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
及测试部分:
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
希望这对你有帮助!
另一种版本,迫使所有前k个组合首先出现,然后是所有前k+1个组合,然后是所有前k+2个组合,等等。这意味着如果你对数组进行排序,最重要的在最上面,它会把它们逐渐扩展到下一个——只有在必须这样做的时候。
private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
return true;
if (num[k - 1] + 1 == n)
return false;
++num[k - 1];
for (int i = 0; i < k - 1; ++i)
num[i] = i;
return true;
}
例如,如果你在k=3, n=5上运行第一个方法("nextCombination"),你会得到:
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
但如果你跑
int[] nums = new int[k];
for (int i = 0; i < k; ++i)
nums[i] = i;
do
{
Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));
你会得到这个(为了清晰起见,我添加了空行):
0 1 2
0 1 3
0 2 3
1 2 3
0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4
它只在必须添加时才添加“4”,而且在添加“4”之后,它只在必须添加时再添加“3”(在执行01、02、12之后)。