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

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]}

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。

现在，我们交换2和4以获得1 4 3 2 5。但是我们希望跳过3和2，所以我们从5开始。我们交换3和5，前3个元素给我们1 4 5。

等等。

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

从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。