我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
在c++中，以下例程将生成range [first,last)之间的长度距离(first,k)的所有组合:
#include <algorithm>
template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Mark Nelson http://marknelson.us */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator i1 = first;
Iterator i2 = last;
++i1;
if (last == i1)
return false;
i1 = last;
--i1;
i1 = k;
--i2;
while (first != i1)
{
if (*--i1 < *i2)
{
Iterator j = k;
while (!(*i1 < *j)) ++j;
std::iter_swap(i1,j);
++i1;
++j;
i2 = k;
std::rotate(i1,j,last);
while (last != j)
{
++j;
++i2;
}
std::rotate(k,i2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
它可以这样使用:
#include <string>
#include <iostream>
int main()
{
std::string s = "12345";
std::size_t comb_size = 3;
do
{
std::cout << std::string(s.begin(), s.begin() + comb_size) << std::endl;
} while (next_combination(s.begin(), s.begin() + comb_size, s.end()));
return 0;
}
这将打印以下内容:
123
124
125
134
135
145
234
235
245
345
其他回答
如果你可以使用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的答案是完整的，不幸的是我还不能投票。这个答案很简单，但只适用于你想要三样东西的时候。
static IEnumerable<string> Combinations(List<string> characters, int length)
{
for (int i = 0; i < characters.Count; i++)
{
// only want 1 character, just return this one
if (length == 1)
yield return characters[i];
// want more than one character, return this one plus all combinations one shorter
// only use characters after the current one for the rest of the combinations
else
foreach (string next in Combinations(characters.GetRange(i + 1, characters.Count - (i + 1)), length - 1))
yield return characters[i] + next;
}
}
下面是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))
这个答案怎么样……这将打印所有长度为3的组合…它可以推广到任何长度… 工作代码…
#include<iostream>
#include<string>
using namespace std;
void combination(string a,string dest){
int l = dest.length();
if(a.empty() && l == 3 ){
cout<<dest<<endl;}
else{
if(!a.empty() && dest.length() < 3 ){
combination(a.substr(1,a.length()),dest+a[0]);}
if(!a.empty() && dest.length() <= 3 ){
combination(a.substr(1,a.length()),dest);}
}
}
int main(){
string demo("abcd");
combination(demo,"");
return 0;
}
我有一个用于project euler的排列算法，用python编写:
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
If
n<len(l)
你应该有所有你需要的组合，没有重复，你需要吗?
它是一个生成器，所以你可以这样使用它:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
