我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
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)
其他回答
我有一个用于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
递归,一个很简单的答案,combo,在Free Pascal中。
procedure combinata (n, k :integer; producer :oneintproc);
procedure combo (ndx, nbr, len, lnd :integer);
begin
for nbr := nbr to len do begin
productarray[ndx] := nbr;
if len < lnd then
combo(ndx+1,nbr+1,len+1,lnd)
else
producer(k);
end;
end;
begin
combo (0, 0, n-k, n-1);
end;
“producer”处理为每个组合生成的产品数组。
我已经编写了一个类来处理处理二项式系数的常见函数,这是您的问题属于的问题类型。它执行以下任务:
Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters. This method makes solving this type of problem quite trivial. Converts the K-indexes to the proper index of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle. My paper talks about this. I believe I am the first to discover and publish this technique, but I could be wrong. Converts the index in a sorted binomial coefficient table to the corresponding K-indexes. Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers. The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to perform the 4 above methods. Accessor methods are provided to access the table. There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.
要了解这个类并下载代码,请参见将二项式系数表化。
将这个类转换为c++应该不难。
这是我用c++写的命题
我尽可能少地限制迭代器类型,所以这个解决方案假设只有前向迭代器,它可以是const_iterator。这应该适用于任何标准容器。在参数没有意义的情况下,它抛出std:: invalid_argument
#include <vector>
#include <stdexcept>
template <typename Fci> // Fci - forward const iterator
std::vector<std::vector<Fci> >
enumerate_combinations(Fci begin, Fci end, unsigned int combination_size)
{
if(begin == end && combination_size > 0u)
throw std::invalid_argument("empty set and positive combination size!");
std::vector<std::vector<Fci> > result; // empty set of combinations
if(combination_size == 0u) return result; // there is exactly one combination of
// size 0 - emty set
std::vector<Fci> current_combination;
current_combination.reserve(combination_size + 1u); // I reserve one aditional slot
// in my vector to store
// the end sentinel there.
// The code is cleaner thanks to that
for(unsigned int i = 0u; i < combination_size && begin != end; ++i, ++begin)
{
current_combination.push_back(begin); // Construction of the first combination
}
// Since I assume the itarators support only incrementing, I have to iterate over
// the set to get its size, which is expensive. Here I had to itrate anyway to
// produce the first cobination, so I use the loop to also check the size.
if(current_combination.size() < combination_size)
throw std::invalid_argument("combination size > set size!");
result.push_back(current_combination); // Store the first combination in the results set
current_combination.push_back(end); // Here I add mentioned earlier sentinel to
// simplyfy rest of the code. If I did it
// earlier, previous statement would get ugly.
while(true)
{
unsigned int i = combination_size;
Fci tmp; // Thanks to the sentinel I can find first
do // iterator to change, simply by scaning
{ // from right to left and looking for the
tmp = current_combination[--i]; // first "bubble". The fact, that it's
++tmp; // a forward iterator makes it ugly but I
} // can't help it.
while(i > 0u && tmp == current_combination[i + 1u]);
// Here is probably my most obfuscated expression.
// Loop above looks for a "bubble". If there is no "bubble", that means, that
// current_combination is the last combination, Expression in the if statement
// below evaluates to true and the function exits returning result.
// If the "bubble" is found however, the ststement below has a sideeffect of
// incrementing the first iterator to the left of the "bubble".
if(++current_combination[i] == current_combination[i + 1u])
return result;
// Rest of the code sets posiotons of the rest of the iterstors
// (if there are any), that are to the right of the incremented one,
// to form next combination
while(++i < combination_size)
{
current_combination[i] = current_combination[i - 1u];
++current_combination[i];
}
// Below is the ugly side of using the sentinel. Well it had to haave some
// disadvantage. Try without it.
result.push_back(std::vector<Fci>(current_combination.begin(),
current_combination.end() - 1));
}
}
下面是一个使用宏的Lisp方法。这适用于Common Lisp,也适用于其他Lisp方言。
下面的代码创建了'n'个嵌套循环,并为列表lst中的'n'个元素的每个组合执行任意代码块(存储在body变量中)。变量var指向一个包含用于循环的变量的列表。
(defmacro do-combinations ((var lst num) &body body)
(loop with syms = (loop repeat num collect (gensym))
for i on syms
for k = `(loop for ,(car i) on (cdr ,(cadr i))
do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
finally (return k)))
让我们看看…
(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))
(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
(LOOP FOR #:G3216 ON (CDR #:G3217) DO
(LOOP FOR #:G3215 ON (CDR #:G3216) DO
(LOOP FOR #:G3214 ON (CDR #:G3215) DO
(LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
(PROGN (PPRINT (MAPCAR #'CAR P))))))))
(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))
(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...
由于默认情况下不存储组合,因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。