我正在寻找一种算法，该算法将一组两个元素作为输入T = {0, 1}，k并生成如下k的所有组合：T
000
001
010
011
100
101
110
111
像上面的例子一样，当k很小时迭代实现很简单。k=3任何想法如何设计递归算法以使算法独立于k.
问问题
3921 次
6 回答
6
您可以递归地执行此操作。假设这是一个学习练习，我会给你伪代码而不是 C 程序：
generate (int pos, int element[T], int current[N])
if pos == N
print (current)
return
for i : 0..T
current[pos] = element[i]
generate(pos+1, element, current)
end
前三行是基本情况。pos从零开始，并指示current数组中需要由递归调用的当前级别填充的位置。一旦pos达到N，我们打印当前组合并返回到之前的级别。
下面三行是一个循环，类似于问题 when 的解决方案中的嵌套循环k=3。“嵌套”通过递归动态发生：您可以将递归调用的下一级视为另一级“循环嵌套”。本质上，递归解决方案允许您构建N嵌套循环，其中N只有在运行时才知道。
于 2012-09-18T10:38:04.003 回答
2
如果您在设计时知道 k，则很容易使用 k 循环生成所有 k 组合，即如果您想要所有 4 组合，则可以使用 4 循环来完成：
for c1=0 to 1
for c2=0 to 1
for c3=0 to 1
for c4=0 to 1
print c1,c2,c3,c4
如果您在设计时不知道 k，您将需要一种模拟 k 循环的方法。这很简单，创建一个大小为 k 的数组并在索引 i 处存储 ci 的当前值（循环编号 i 索引）。
c : array[1..k]
fill(c,0) // initialize all the cells with 0
do
for i=1 to k
print c[i]
while increment(c) // get next values
increment如果所有值都已使用，则获取下一个值并返回 false，否则返回 true。
increment(c : array[1..k])
begin
i=k
do
c[i]=c[i]+1;
if c[i]=2 // i.e. MAX+1
c[i]=0
i=i-1 // incerment previous position
else
return true // increment done
end if
while (i>1)
// here we need to increment the first position
c[i]=c[i]+1
if c[i]=2 // we looped thru all the values
c[i]=0
return false
end if
return true
end
这种方法可以推广到任何基数的任何循环（=每个循环的不同最大值）或具有不同的起始值、步骤等......这个方法也可以推广到生成具有重复等的字典组合...... google for里程表或查看 TAOCP Knuth 第 3 卷分册 2 和 3。
于 2012-09-18T10:59:26.203 回答
2
您不需要递归算法。如果您查看您的列表，您应该会看到“模式”。
那是从 0 到 2^k-1 的二进制数。因此，简单的解决方案就是数数。
for (i = 0; i < (1<<k); i++) {
// generate the binary representation of i
for (c = k-1 ; c >= 0; c--) {
r = i >> c;
printf((r & 1) ? "1" : "0");
}
printf("\n");
}
编辑：如果你需要一个递归方法，你可以通过在长度上递归来轻松地做到这一点，我给出了一些伪代码（因为在我看来，递归只有在它是一些作业/作业时才有意义，然后你应该自己做一些事情） ：
print_all_combos(int k, char* prefix) {
if (k == 0) {
printf("%s\n", prefix);
return;
}
append(prefix, "0");
print_all_combos(k - 1 , prefix);
remove_last_char(prefix);
append(prefix, "1");
remove_last_char(k - 1, prefix);
}
并用 k 和一个空字符串作为参数调用它。
于 2012-09-18T10:43:21.113 回答
0
根据您提供的示例，我相信您指的是 k 排列，而不是组合。引用自维基百科：
组合是从更大的组中选择多个事物的一种方式，其中（与排列不同）顺序无关紧要。
于 2013-07-02T19:07:44.217 回答
0
#include<stdio.h>
#include<conio.h>
void calAns(int idx, int f[3]);
int main()
{
int f[3];
calAns(0,f);
getch();
return 0;
}
void calAns(int idx, int f[3])
{
if(idx == 3)
{
int i;
for(i = 0; i<3; i++)
printf("%d",f[i]);
printf("\n");
return;
}
f[idx] = 0;
calAns(idx+1, f);
f[idx] = 1;
calAns(idx+1, f);
}
于 2016-09-20T15:52:38.170 回答
0
感谢@Sergey Kalinichenko，我制作了一个小递归应用程序。尽管这是 Java 代码，但我希望它会对某人有所帮助。
关键方法是generateCombinationsRecursively。
测试类：
public class CombinationOKTest {
CombinationOK combinationOK;
@BeforeEach
void setUp() {
combinationOK = new CombinationOK();
}
@Test
void allCombinationsWithTwoElementsAndLengthThreeBinary() {
List<Integer> elementList = List.of(0, 1);
int combinationLength = 3;
List<List<Integer>> combinationList =
combinationOK.getAllCombinations(elementList, combinationLength);
assertEquals(8, combinationList.size());
assertEquals(List.of(
List.of(0, 0, 0),
List.of(0, 0, 1),
List.of(0, 1, 0),
List.of(0, 1, 1),
List.of(1, 0, 0),
List.of(1, 0, 1),
List.of(1, 1, 0),
List.of(1, 1, 1)),
combinationList);
}
}
实现类：
public class CombinationOK {
public List<List<Integer>> getAllCombinations(List<Integer> elementList,
int combinationLength) {
List<List<Integer>> combinationList = new ArrayList<>();
Integer[] combination = new Integer[combinationLength];
generateCombinationsRecursively(elementList, combinationList, combination, 0);
System.out.println();
System.out.println(combinationList);
return combinationList;
}
public class CombinationOK {
public List<List<Integer>> getAllCombinations(List<Integer> elementList,
int combinationLength) {
List<List<Integer>> combinationList = new ArrayList<>();
Integer[] combination = new Integer[combinationLength];
generateCombinationsRecursively(elementList, combinationList, combination, 0);
System.out.println();
System.out.println(combinationList);
return combinationList;
}
/**
*
* Magic is done in this recursive method <code>generateCombinationsRecursively</code>.
*
* @param elementList elements that combinations are made of (T)
* @param combinationList is resulting list of combinations as a result of recursive method
* @param combination is array of elements, single combination with variable length (k)
* @param position of one element from the list <code>elementList</code> in the <code>combination</code> array
*
*/
private void generateCombinationsRecursively(List<Integer> elementList,
List<List<Integer>> combinationList,
Integer[] combination,
int position) {
if (position == combination.length) {
System.out.println(Arrays.asList(combination));
combinationList.add(new ArrayList<>(Arrays.asList(combination)));
return;
}
for (int i = 0; i < elementList.size(); i++) {
combination[position] = elementList.get(i);
generateCombinationsRecursively(
elementList, combinationList, combination, position + 1);
}
}
}
概括：
主要功能在这种递归方法generateCombinationsRecursively中。
参数position是可变的，取决于递归函数的深度。position参数的最大值是combination列表大小 (k)。如果达到最大值 (k)（方法的第一个块generateCombinationsRecursively），则将 newcombination添加到结果combinationList列表中并完成递归。
该方法的第二个块generateCombinationsRecursively是for循环遍历列表中的所有元素elementList。根据position值，combination列表由elementList(T) 中的元素填充。接下来，调用递归方法generateCombinationsRecursively
并在参数上加上重音，该position参数递增，因此它指向 中的下一个位置combination，该递归方法将填充下一个元素（来自 T）。
输出组合：
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]
输出结果combinationList列表：
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
于 2021-10-17T22:00:44.170 回答