我正在寻找一种算法，它以两个元素的集合T = {0, 1}和k作为输入，并按照以下方式生成所有T的k组合：
000
001
010
011
100
101
110
111
如果k较小，例如上面的例子中k=3，那么采用迭代实现很容易。有没有想法设计一种递归算法，使得算法不依赖于k。
生成有重复元素的集合的k元组组合的算法？
4
- stressed_geek
1
2这是排列，组合中顺序不重要。 - automaton
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，我们打印当前组合并返回到先前的级别。底部三行是一个循环，类似于解决问题时
k=3 的嵌套循环。通过递归动态地发生“嵌套”，您可以将下一个递归调用的级别视为另一个“循环嵌套”级别。实际上，递归解决方案可让您构建 N 嵌套循环，其中 N 只在运行时才知道。- Sergey Kalinichenko
2
你不需要使用递归算法。如果你看一下列表，你应该会看到这个“模式”。
这是从0到2^k-1的二进制数。所以简单的解决方法就是计数。
并使用 k 和空字符串作为参数进行调用。
这是从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 和空字符串作为参数进行调用。
- flolo
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的数组，并将当前ci（循环编号i索引）的值存储在索引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
这种方法可以推广到任何循环，不论是在任何基数（每个循环的不同最大值）或具有不同的起始值、步长等等……此方法也可以推广用于生成重复的词汇组合等等……请搜索odometer或查看TAOCP Knuth Volume 3 fascicle 2和3。
- Kwariz
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);
}
- vivdhiman
1
你的回答确实值得一些解释。请参考http://stackoverflow.com/help/how-to-answer。 - J. Chomel
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 的第一个块），
则将新的 combination 添加到结果列表 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]]
- ognjenkl
0
根据您提供的示例，我相信您指的是k排列，而不是组合。引用自维基百科：
组合是从一个较大的群体中选择几个事物的一种方式，与排列不同的是，顺序并不重要。
- Emmanuel Caruyer
1
这可能应该是一条注释，而不是一个答案。 - pamphlet
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接