我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
这是我对javascript的贡献(没有递归)
set = ["q0", "q1", "q2", "q3"]
collector = []
function comb(num) {
results = []
one_comb = []
for (i = set.length - 1; i >= 0; --i) {
tmp = Math.pow(2, i)
quotient = parseInt(num / tmp)
results.push(quotient)
num = num % tmp
}
k = 0
for (i = 0; i < results.length; ++i)
if (results[i]) {
++k
one_comb.push(set[i])
}
if (collector[k] == undefined)
collector[k] = []
collector[k].push(one_comb)
}
sum = 0
for (i = 0; i < set.length; ++i)
sum += Math.pow(2, i)
for (ii = sum; ii > 0; --ii)
comb(ii)
cnt = 0
for (i = 1; i < collector.length; ++i) {
n = 0
for (j = 0; j < collector[i].length; ++j)
document.write(++cnt, " - " + (++n) + " - ", collector[i][j], "<br>")
document.write("<hr>")
}
其他回答
这是一个c++解决方案,我提出使用递归和位移位。它也可以在C语言中工作。
void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
你可以在这里找到这是如何工作的解释。
像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
在c#中:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
用法:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
结果:
123
124
125
134
135
145
234
235
245
345
这里你有一个用c#编写的该算法的惰性评估版本:
static bool nextCombination(int[] num, int n, int k)
{
bool finished, changed;
changed = finished = false;
if (k > 0)
{
for (int i = k - 1; !finished && !changed; i--)
{
if (num[i] < (n - 1) - (k - 1) + i)
{
num[i]++;
if (i < k - 1)
{
for (int j = i + 1; j < k; j++)
{
num[j] = num[j - 1] + 1;
}
}
changed = true;
}
finished = (i == 0);
}
}
return changed;
}
static IEnumerable Combinations<T>(IEnumerable<T> elements, int k)
{
T[] elem = elements.ToArray();
int size = elem.Length;
if (k <= size)
{
int[] numbers = new int[k];
for (int i = 0; i < k; i++)
{
numbers[i] = i;
}
do
{
yield return numbers.Select(n => elem[n]);
}
while (nextCombination(numbers, size, k));
}
}
及测试部分:
static void Main(string[] args)
{
int k = 3;
var t = new[] { "dog", "cat", "mouse", "zebra"};
foreach (IEnumerable<string> i in Combinations(t, k))
{
Console.WriteLine(string.Join(",", i));
}
}
希望这对你有帮助!
另一种版本,迫使所有前k个组合首先出现,然后是所有前k+1个组合,然后是所有前k+2个组合,等等。这意味着如果你对数组进行排序,最重要的在最上面,它会把它们逐渐扩展到下一个——只有在必须这样做的时候。
private static bool NextCombinationFirstsAlwaysFirst(int[] num, int n, int k)
{
if (k > 1 && NextCombinationFirstsAlwaysFirst(num, num[k - 1], k - 1))
return true;
if (num[k - 1] + 1 == n)
return false;
++num[k - 1];
for (int i = 0; i < k - 1; ++i)
num[i] = i;
return true;
}
例如,如果你在k=3, n=5上运行第一个方法("nextCombination"),你会得到:
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
但如果你跑
int[] nums = new int[k];
for (int i = 0; i < k; ++i)
nums[i] = i;
do
{
Console.WriteLine(string.Join(" ", nums));
}
while (NextCombinationFirstsAlwaysFirst(nums, n, k));
你会得到这个(为了清晰起见,我添加了空行):
0 1 2
0 1 3
0 2 3
1 2 3
0 1 4
0 2 4
1 2 4
0 3 4
1 3 4
2 3 4
它只在必须添加时才添加“4”,而且在添加“4”之后,它只在必须添加时再添加“3”(在执行01、02、12之后)。
我有一个用于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