我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
下面是一个简单易懂的递归c++解决方案:
#include<vector>
using namespace std;
template<typename T>
void ksubsets(const vector<T>& arr, unsigned left, unsigned idx,
vector<T>& lst, vector<vector<T>>& res)
{
if (left < 1) {
res.push_back(lst);
return;
}
for (unsigned i = idx; i < arr.size(); i++) {
lst.push_back(arr[i]);
ksubsets(arr, left - 1, i + 1, lst, res);
lst.pop_back();
}
}
int main()
{
vector<int> arr = { 1, 2, 3, 4, 5 };
unsigned left = 3;
vector<int> lst;
vector<vector<int>> res;
ksubsets<int>(arr, left, 0, lst, res);
// now res has all the combinations
}
其他回答
下面的递归算法从有序集中选取所有k元素组合:
选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。
对集合中的每一个i进行上述迭代。
为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。
简短快速的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;
}
如果你可以使用SQL语法——比如,如果你使用LINQ访问一个结构或数组的字段,或者直接访问一个数据库,其中有一个名为“Alphabet”的表,只有一个字符字段“Letter”,你可以适应以下代码:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
这将返回所有3个字母的组合,不管你在表格“字母表”中有多少个字母(它可以是3,8,10,27等)。
如果你想要的是所有的排列,而不是组合(也就是说,你想要“ACB”和“ABC”被视为不同的,而不是只出现一次),只需删除最后一行(and一行),就完成了。
Post-Edit:重新阅读问题后,我意识到需要的是通用算法,而不仅仅是选择3个项目的特定算法。Adam Hughes的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。
另一种python递归解决方案。
def combination_indicies(n, k, j = 0, stack = []):
if len(stack) == k:
yield list(stack)
return
for i in range(j, n):
stack.append(i)
for x in combination_indicies(n, k, i + 1, stack):
yield x
stack.pop()
list(combination_indicies(5, 3))
输出:
[[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]]
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表示必须从数组中的哪个位置开始选择。