查找一组值的所有唯一子集

Question

我有一个算法问题。我正在尝试从更大的一组值中找到所有独特的值子集。

例如说我有套{1,3,7,9}。我可以使用什么算法来查找这些3的子集？

 
{1,3,7} 
{1,3,9} 
{1,7,9} 
{3,7,9} 

亚群不应重复，和顺序是不重要的，设置{1,2,3}是相同的集合{3,2,1}用于这些目的。 Psudocode（或普通类）受到鼓励。

---

蛮力的方法显然是可能的，但不是理想的。

例如，这样的暴力方法如下。

 
for i = 0 to size 
    for j = i + 1 to size 
    for k = j + 1 to size 
     subset[] = {set[i],set[j],set[k]} 

不幸的是，这需要对于所述子集中期望的每个元素，如果，例如，要8个元素的子集这是不希望的额外循环。

Answer 1

一些使用递归的Java代码。

基本想法是尝试交换每个元素与当前位置，然后递归下一个位置（但我们也需要startPos这里指示我们交换的最后一个位置是什么，否则我们会得到一个简单置换生成器）。一旦我们有足够的元素，我们打印所有这些并返回。

static void subsets(int[] arr, int pos, int depth, int startPos) 
{ 
    if (pos == depth) 
    { 
     for (int i = 0; i < depth; i++) 
     System.out.print(arr[i] + " "); 
     System.out.println(); 
     return; 
    } 
    for (int i = startPos; i < arr.length; i++) 
    { 
     // optimization - not enough elements left 
     if (depth - pos + i > arr.length) 
     return; 

     // swap pos and i 
     int temp = arr[pos]; 
     arr[pos] = arr[i]; 
     arr[i] = temp; 

     subsets(arr, pos+1, depth, i+1); 

     // swap pos and i back - otherwise things just gets messed up 
     temp = arr[pos]; 
     arr[pos] = arr[i]; 
     arr[i] = temp; 
    } 
} 

public static void main(String[] args) 
{ 
    subsets(new int[]{1,3,7,9}, 0, 3, 0); 
} 

打印：

1 3 7 
1 3 9 
1 7 9 
3 7 9 

更详细的说明（通过实施例）：

首先第一件事情 - 在上面的代码中，元件通过执行保持在相同的位置与自己交换 - 它什么都不做，只是让代码变得简单一些。

另请注意，在每一步我们都会恢复所有交换。

说我们有输入1 2 3 4 5，我们希望找到大小3

的子集首先，我们只取前3种元素 - 1 2 3。

然后我们交换3与4和5分别
和第3个元素为我们提供了1 2 4和1 2 5。

请注意，我们刚刚完成了包含1和2的所有集合。

现在我们想要成套的表格1 3 X，所以我们换了2和3并得到1 3 2 4 5。但是我们已经将1和2组合在一起，所以我们在这里想要跳过2。因此，我们分别交换2与4和5，与前3个元素给我们1 3 4和1 3 5。我们将2和4换成1 4 3 2 5。但我们想跳过3和2，所以我们从5开始。我们交换3和5，前3个元素给我们1 4 5。

依此类推。

跳绳元素在这里也许是最复杂的部分。请注意，每当我们跳过元素，它只涉及从我们交换的位置后继续（当我们交换了2和4，我们继续从4之后）。这是正确的，因为没有处理过的元素可以到达我们交换位置的左侧，也不能处理元素到达该位置的右侧，因为我们从左到右处理所有元素。

认为在方面for循环

这也许是最简单的for循环的角度考虑的算法。

for i = 0 to size 
    for j = i + 1 to size 
    for k = j + 1 to size 
     subset[] = {set[i],set[j],set[k]} 

每个递归步骤将代表一个for循环。

startPos分别是0,i+1和j+1。

depth是多少for循环也有。

pos是for循环，我们当前所处。

因为我们从来不会后退去更深的循环，它是安全的使用数组的开始作为存储我们的元素，只要我们恢复的变化，当我们用一个迭代完成。

Answer 2

如果您只对大小为3的子集感兴趣，则可以使用三个简单的嵌套for循环来完成此操作。

for (int i = 0; i < arr.size(); i++) 
    for (int j = i+1; j < arr.size(); j++) 
    for (int k = j+1; k < arr.size(); k++) 
     std::cout << "{ " << arr[i] <<"," << arr[j] <<"," << arr[k] <<" }"; 

对于更一般的情况，您将不得不使用递归。

void recur(set<int> soFar, set<int> remaining, int subSetSize) { 
    if (soFar.size() == subSetSize) { 
    print soFar; 
    return; 
    } 

    for (int I = 0; I < remaining.size(); I++) { 
    //take out Ith element from remaining and push it in soFar. 
    // recur(newSofar, newRemaining, subSetSize); 
    } 
}