查找一组值的所有唯一子集 [英] Find all unique subsets of a set of values
问题描述
我遇到算法问题。我正在尝试从较大的一组值中查找所有唯一的值子集。
I have an algorithm problem. I am trying to find all unique subset of values from a larger set of values.
例如，说我有一组 {1,3， 7,9} 。我可以使用什么算法找到3个子集？
For example say I have the set {1,3,7,9}. What algorithm can I use to find these subsets of 3?
{1,3,7}
{1,3,9}
{1,7,9}
{3,7,9}
子集不应重复，并且顺序无关紧要，为此，集合{1,2,3}与集合{3,2,1}相同。鼓励使用伪代码（或常规类型的伪代码）。
Subsets should not repeat, and order is unimportant, set {1,2,3} is the same as set {3,2,1} for these purposes. Psudocode (or the regular kind) is encouraged.
强力方法显然是可能的，但不是所希望的。
A brute force approach is obviously possible, but not desired.
例如，这种蛮力方法如下。
For example such a brute force method would be as follows.
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个元素的子集。
Unfortunately this requires an additional loop for each element desired in the subset, which is undesirable if, for example, you want a subset of 8 elements.
推荐答案
使用递归的某些Java代码。
Some Java code using recursion.
基本思想是尝试将每个元素与当前位置交换，然后递归到下一个位置（但我们还需要在这里 startPos 来指示我们最后一个位置是什么）与was交换，否则我们将获得一个简单的置换生成器）。一旦有了足够的元素，我们将打印所有这些元素并返回。
The basic idea is to try to swap each element with the current position and then recurse on the next position (but we also need startPos here to indicate what the last position that we swapped with was, otherwise we'll get a simple permutation generator). Once we've got enough elements, we print all those and return.
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
更详细的解释（通过示例）：
首先要注意的是-在上面的代码中，元素通过与自身进行交换而保持在相同的位置-它什么也没做，只是使代码更简单。
First things first - in the above code, an element is kept in the same position by performing a swap with itself - it doesn't do anything, just makes the code a bit simpler.
说我们输入了 1 2 3 4 5 ，我们想要找到大小为3的子集。
Say we have input 1 2 3 4 5 and we want to find subsets of size 3.
首先，我们只获取前三个元素- 1 2 3 。
First we just take the first 3 elements - 1 2 3.
然后我们将 3 交换为 4 和 5 ，
和前三个元素给我们 1 2 4 和 1 2 5 。
Then we swap the 3 with 4 and 5 respectively,
and the first 3 elements gives us 1 2 4 and 1 2 5.
请注意，我们刚刚完成了所有包含 1 和 2 一起。
Note that we've just finished doing all sets containing 1 and 2 together.
现在我们想要格式为 1 3 X 的集合，因此我们交换 2 和 3 并获得 1 3 2 4 5 。但是我们已经有包含 1 和 2 的集合，因此在这里我们要跳过 2 。因此，我们分别将 2 交换为 4 和 5 ，并且前三个元素给我们 1 3 4 和 1 3 5 。
Now we want sets of the form 1 3 X, so we swap 2 and 3 and get 1 3 2 4 5. But we already have sets containing 1 and 2 together, so here we want to skip 2. So we swap 2 with 4 and 5 respectively, and the first 3 elements gives us 1 3 4 and 1 3 5.
现在我们将 2 和 4 交换以获得 1 4 3 2 5 。但是我们要跳过 3 和 2 ，所以我们从 5 。我们将 3 和 5 交换，前3个元素给我们 1 4 5 。
Now we swap 2 and 4 to get 1 4 3 2 5. But we want to skip 3 and 2, so we start from 5. We swap 3 and 5, and the first 3 elements gives us 1 4 5.
等等。
此处的跳过元素可能是最复杂的部分。请注意，每当我们跳过元素时，它只涉及从交换位置开始（当我们交换 2 和 4 ，我们从 4 之后开始。这是正确的，因为在没有处理的情况下无法将元素移到要交换的位置的左侧，在处理后的元素也不能移至该位置的右侧，因为我们从左到右处理所有元素。
Skipping elements here is perhaps the most complex part. Note that whenever we skip elements, it just involves continuing from after the position we swapped with (when we swapped 2 and 4, we continued from after the 4 was). This is correct because there's no way an element can get to the left of the position we're swapping with without having been processed, nor can a processed element get to the right of that position, because we process all the elements from left to right.
考虑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循环。
Each recursive step would represent a for-loop.
startPos 是 0 ， i + 1 和 j + 1 。
深度是多少个for循环。
depth is how many for-loops there are.
pos 是我们当前所在的for循环。
pos is which for-loop we're currently at.
由于我们绝不会在更深的循环中向后走，因此可以安全地使用数组作为元素的存储空间，只要我们在完成迭代后还原更改即可。
Since we never go backwards in a deeper loop, it's safe to use the start of the array as storage for our elements, as long as we revert the changes when we're done with an iteration.
这篇关于查找一组值的所有唯一子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
