我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由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
其他回答
这里你有一个用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之后)。
c#简单算法。 (我发布它是因为我试图使用你们上传的那个，但由于某种原因我无法编译它——扩展一个类?所以我自己写了一个，以防别人遇到和我一样的问题)。 顺便说一下，除了基本的编程，我对c#没什么兴趣，但是这个工作得很好。
public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
{
List<List<int>> lSubsets = new List<List<int>>();
GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
return lSubsets;
}
public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
{
if (lCurrSet.Count == k)
{
lSubsets.Add(lCurrSet);
return;
}
if (i >= lInputSet.Count)
return;
List<int> lWith = new List<int>(lCurrSet);
List<int> lWithout = new List<int>(lCurrSet);
lWith.Add(lInputSet[i++]);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
}
GetSubsetsOfSizeK(set of type List<int>， integer k)
您可以修改它以遍历您正在处理的任何内容。
好运！
在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
现在又出现了祖辈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.
简单但缓慢的c++回溯算法。
#include <iostream>
void backtrack(int* numbers, int n, int k, int i, int s)
{
if (i == k)
{
for (int j = 0; j < k; ++j)
{
std::cout << numbers[j];
}
std::cout << std::endl;
return;
}
if (s > n)
{
return;
}
numbers[i] = s;
backtrack(numbers, n, k, i + 1, s + 1);
backtrack(numbers, n, k, i, s + 1);
}
int main(int argc, char* argv[])
{
int n = 5;
int k = 3;
int* numbers = new int[k];
backtrack(numbers, n, k, 0, 1);
delete[] numbers;
return 0;
}
