我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
还有另一个递归解决方案(你应该能够使用字母而不是数字)使用堆栈,虽然比大多数更短:
stack = []
def choose(n,x):
r(0,0,n+1,x)
def r(p, c, n,x):
if x-c == 0:
print stack
return
for i in range(p, n-(x-1)+c):
stack.append(i)
r(i+1,c+1,n,x)
stack.pop()
4选3或者我想要从0到4的所有3种数字组合
choose(4,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]
其他回答
我可以给出这个问题的递归Python解决方案吗?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
使用示例:
>>> len(list(choose_iter("abcdefgh",3)))
56
我喜欢它的简洁。
像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
#include <stdio.h>
unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;
if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}
typedef void(*printfn)(const void *, FILE *);
void print_set(const unsigned int *ar, size_t len, const void **elements,
const char *brackets, printfn print, FILE *fptr)
{
unsigned int i;
fputc(brackets[0], fptr);
for (i = 0; i < len; i++) {
print(elements[ar[i]], fptr);
if (i < len - 1) {
fputs(", ", fptr);
}
}
fputc(brackets[1], fptr);
}
int main(void)
{
unsigned int numbers[] = { 0, 1, 2 };
char *elements[] = { "a", "b", "c", "d", "e" };
const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
const unsigned int n = sizeof(elements) / sizeof(const char*);
do {
print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
putchar('\n');
} while (next_combination(numbers, n, k));
getchar();
return 0;
}
现在又出现了祖辈COBOL,一种饱受诟病的语言。
让我们假设一个包含34个元素的数组,每个元素8个字节(完全是任意选择)。其思想是枚举所有可能的4元素组合,并将它们加载到一个数组中。
我们使用4个指标,每个指标代表4个组中的每个位置
数组是这样处理的:
idx1 = 1
idx2 = 2
idx3 = 3
idx4 = 4
我们把idx4从4变到最后。对于每个idx4,我们得到一个唯一的组合 四人一组。当idx4到达数组的末尾时,我们将idx3增加1,并将idx4设置为idx3+1。然后再次运行idx4到最后。我们以这种方式继续,分别增加idx3、idx2和idx1,直到idx1的位置距离数组末端小于4。算法就完成了。
1 --- pos.1
2 --- pos 2
3 --- pos 3
4 --- pos 4
5
6
7
etc.
第一次迭代:
1234
1235
1236
1237
1245
1246
1247
1256
1257
1267
etc.
一个COBOL的例子:
01 DATA_ARAY.
05 FILLER PIC X(8) VALUE "VALUE_01".
05 FILLER PIC X(8) VALUE "VALUE_02".
etc.
01 ARAY_DATA OCCURS 34.
05 ARAY_ITEM PIC X(8).
01 OUTPUT_ARAY OCCURS 50000 PIC X(32).
01 MAX_NUM PIC 99 COMP VALUE 34.
01 INDEXXES COMP.
05 IDX1 PIC 99.
05 IDX2 PIC 99.
05 IDX3 PIC 99.
05 IDX4 PIC 99.
05 OUT_IDX PIC 9(9).
01 WHERE_TO_STOP_SEARCH PIC 99 COMP.
* Stop the search when IDX1 is on the third last array element:
COMPUTE WHERE_TO_STOP_SEARCH = MAX_VALUE - 3
MOVE 1 TO IDX1
PERFORM UNTIL IDX1 > WHERE_TO_STOP_SEARCH
COMPUTE IDX2 = IDX1 + 1
PERFORM UNTIL IDX2 > MAX_NUM
COMPUTE IDX3 = IDX2 + 1
PERFORM UNTIL IDX3 > MAX_NUM
COMPUTE IDX4 = IDX3 + 1
PERFORM UNTIL IDX4 > MAX_NUM
ADD 1 TO OUT_IDX
STRING ARAY_ITEM(IDX1)
ARAY_ITEM(IDX2)
ARAY_ITEM(IDX3)
ARAY_ITEM(IDX4)
INTO OUTPUT_ARAY(OUT_IDX)
ADD 1 TO IDX4
END-PERFORM
ADD 1 TO IDX3
END-PERFORM
ADD 1 TO IDX2
END_PERFORM
ADD 1 TO IDX1
END-PERFORM.
《计算机程序设计艺术》第4卷第3册有大量这样的内容,它们可能比我描述的更适合你的特定情况。
格雷码
你会遇到的一个问题当然是内存,很快,你会在你的集合中遇到20个元素的问题——20C3 = 1140。如果你想遍历这个集合,最好使用修改过的灰码算法,这样你就不会把它们都保存在内存中。这将从前一个组合中生成下一个组合并避免重复。有很多不同的用途。我们想要最大化连续组合之间的差异吗?最小化?等等。
一些描述灰色代码的原始论文:
Hamilton路径与最小变化算法 相邻交换组合生成算法
以下是涉及该主题的其他一些论文:
Eades、Hickey、Read相邻交换组合生成算法的高效实现(PDF, Pascal代码) 结合发电机 组合灰色编码综述(PostScript) 灰色编码的一种算法
Chase's Twiddle(算法)
菲利普·J·蔡斯,《算法382:N个对象中M个对象的组合》(1970)
该算法在C…
按字典顺序排列的组合索引(Buckles算法515)
还可以通过索引(按字典顺序)引用组合。意识到索引应该是基于索引从右到左的一些变化,我们可以构造一些应该恢复组合的东西。
So, we have a set {1,2,3,4,5,6}... and we want three elements. Let's say {1,2,3} we can say that the difference between the elements is one and in order and minimal. {1,2,4} has one change and is lexicographically number 2. So the number of 'changes' in the last place accounts for one change in the lexicographical ordering. The second place, with one change {1,3,4} has one change but accounts for more change since it's in the second place (proportional to the number of elements in the original set).
我所描述的方法是一种解构,从集合到索引,我们需要做相反的事情——这要复杂得多。这就是巴克尔斯解决问题的方法。我写了一些C来计算它们,做了一些小改动——我使用集合的索引而不是一个数字范围来表示集合,所以我们总是从0…n开始工作。 注意:
由于组合是无序的,{1,3,2}={1,2,3}——我们将它们按字典顺序排列。 该方法有一个隐式的0来开始第一个差值集。
词典顺序组合索引(麦卡弗里)
还有另一种方法:,它的概念更容易掌握和编程,但它没有Buckles的优化。幸运的是,它也不会产生重复的组合:
最大化的集合,其中。
例如:27 = C (6, 4) + C (5,3) + C (2, 2) + C(1, 1)。那么,第27个单词的字典组合是{1,2,5,6},它们是你想要查找的任何集合的索引。下面的例子(OCaml),需要选择函数,留给读者:
(* this will find the [x] combination of a [set] list when taking [k] elements *)
let combination_maccaffery set k x =
(* maximize function -- maximize a that is aCb *)
(* return largest c where c < i and choose(c,i) <= z *)
let rec maximize a b x =
if (choose a b ) <= x then a else maximize (a-1) b x
in
let rec iterate n x i = match i with
| 0 -> []
| i ->
let max = maximize n i x in
max :: iterate n (x - (choose max i)) (i-1)
in
if x < 0 then failwith "errors" else
let idxs = iterate (List.length set) x k in
List.map (List.nth set) (List.sort (-) idxs)
一个小而简单的组合迭代器
为了教学目的,提供了以下两个算法。它们实现了一个迭代器和(更通用的)文件夹整体组合。 它们尽可能快,复杂度为O(nCk)。内存消耗受k约束。
我们将从迭代器开始,它将为每个组合调用用户提供的函数
let iter_combs n k f =
let rec iter v s j =
if j = k then f v
else for i = s to n - 1 do iter (i::v) (i+1) (j+1) done in
iter [] 0 0
更通用的版本将从初始状态开始调用用户提供的函数和状态变量。因为我们需要在不同的状态之间传递状态,所以我们不使用for循环,而是使用递归,
let fold_combs n k f x =
let rec loop i s c x =
if i < n then
loop (i+1) s c @@
let c = i::c and s = s + 1 and i = i + 1 in
if s < k then loop i s c x else f c x
else x in
loop 0 0 [] x