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

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。

然后我们分别用4和5交换3，
前 3 个元素给我们 1 2 4 和 1 2 5。

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

现在我们想要 1 3 X 形式的集合，所以我们交换 2 和 3 得到 1 3 2 4 5。但是我们已经有了包含 1 和 2 的集合，所以这里我们想跳过 2。所以我们分别用 4 和 5 交换 2，前 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 循环。

因为我们永远不会在更深的循环中倒退，所以使用数组的开头作为元素的存储是安全的，只要我们在完成迭代后还原更改即可。