我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
赶时髦,发布另一个解决方案。这是一个通用的Java实现。输入:(int k)是要选择的元素数量,(List<T> List)是要选择的列表。返回一个组合列表(list < list <T>>)。
public static <T> List<List<T>> getCombinations(int k, List<T> list) {
List<List<T>> combinations = new ArrayList<List<T>>();
if (k == 0) {
combinations.add(new ArrayList<T>());
return combinations;
}
for (int i = 0; i < list.size(); i++) {
T element = list.get(i);
List<T> rest = getSublist(list, i+1);
for (List<T> previous : getCombinations(k-1, rest)) {
previous.add(element);
combinations.add(previous);
}
}
return combinations;
}
public static <T> List<T> getSublist(List<T> list, int i) {
List<T> sublist = new ArrayList<T>();
for (int j = i; j < list.size(); j++) {
sublist.add(list.get(j));
}
return sublist;
}
其他回答
下面的递归算法从有序集中选取所有k元素组合:
选择组合中的第一个元素I 将I与从大于I的元素集中递归选择的k-1个元素的组合组合。
对集合中的每一个i进行上述迭代。
为了避免重复,您必须选择比i大的其余元素。这样[3,5]将只被选中一次,即[3]与[5]结合,而不是两次(该条件消除了[5]+[3])。没有这个条件,你得到的是变化而不是组合。
像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
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)
简短的java解决方案:
import java.util.Arrays;
public class Combination {
public static void main(String[] args){
String[] arr = {"A","B","C","D","E","F"};
combinations2(arr, 3, 0, new String[3]);
}
static void combinations2(String[] arr, int len, int startPosition, String[] result){
if (len == 0){
System.out.println(Arrays.toString(result));
return;
}
for (int i = startPosition; i <= arr.length-len; i++){
result[result.length - len] = arr[i];
combinations2(arr, len-1, i+1, result);
}
}
}
结果将是
[A, B, C]
[A, B, D]
[A, B, E]
[A, B, F]
[A, C, D]
[A, C, E]
[A, C, F]
[A, D, E]
[A, D, F]
[A, E, F]
[B, C, D]
[B, C, E]
[B, C, F]
[B, D, E]
[B, D, F]
[B, E, F]
[C, D, E]
[C, D, F]
[C, E, F]
[D, E, F]
我想提出我的解决方案。在next中没有递归调用,也没有嵌套循环。 代码的核心是next()方法。
public class Combinations {
final int pos[];
final List<Object> set;
public Combinations(List<?> l, int k) {
pos = new int[k];
set=new ArrayList<Object>(l);
reset();
}
public void reset() {
for (int i=0; i < pos.length; ++i) pos[i]=i;
}
public boolean next() {
int i = pos.length-1;
for (int maxpos = set.size()-1; pos[i] >= maxpos; --maxpos) {
if (i==0) return false;
--i;
}
++pos[i];
while (++i < pos.length)
pos[i]=pos[i-1]+1;
return true;
}
public void getSelection(List<?> l) {
@SuppressWarnings("unchecked")
List<Object> ll = (List<Object>)l;
if (ll.size()!=pos.length) {
ll.clear();
for (int i=0; i < pos.length; ++i)
ll.add(set.get(pos[i]));
}
else {
for (int i=0; i < pos.length; ++i)
ll.set(i, set.get(pos[i]));
}
}
}
用法示例:
static void main(String[] args) {
List<Character> l = new ArrayList<Character>();
for (int i=0; i < 32; ++i) l.add((char)('a'+i));
Combinations comb = new Combinations(l,5);
int n=0;
do {
++n;
comb.getSelection(l);
//Log.debug("%d: %s", n, l.toString());
} while (comb.next());
Log.debug("num = %d", n);
}