给定一个包含 n 个元素的集合 {1,2,3,4,5...n}，我们需要找到所有长度为 k 的子集。
例如，如果 n = 4 并且 k = 2，则输出结果应为 {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}。
我甚至不知道如何开始解决这个问题。我们不需要使用类似 next_permutation 等内置库函数。
需要 C/C++ 或 Java 语言实现算法。
16个回答
53
对于这个任务，递归是你的朋友。
对于每个元素-“猜测”它是否在当前子集中，并用你可以选择的较小超集进行递归调用。对于“是”和“否”两种猜测都要这样做-将会得到所有可能的子集。
通过停止条件轻松地限制自己的长度。
Java代码：
private static void getSubsets(List<Integer> superSet, int k, int idx, Set<Integer> current,List<Set<Integer>> solution) {
//successful stop clause
if (current.size() == k) {
solution.add(new HashSet<>(current));
return;
}
//unseccessful stop clause
if (idx == superSet.size()) return;
Integer x = superSet.get(idx);
current.add(x);
//"guess" x is in the subset
getSubsets(superSet, k, idx+1, current, solution);
current.remove(x);
//"guess" x is not in the subset
getSubsets(superSet, k, idx+1, current, solution);
}
public static List<Set<Integer>> getSubsets(List<Integer> superSet, int k) {
List<Set<Integer>> res = new ArrayList<>();
getSubsets(superSet, k, 0, new HashSet<Integer>(), res);
return res;
}
使用以下方式调用：
List<Integer> superSet = new ArrayList<>();
superSet.add(1);
superSet.add(2);
superSet.add(3);
superSet.add(4);
System.out.println(getSubsets(superSet,2));
将产生以下结果：
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
- amit
11
2@sTEAK：子集的数量呈指数级增长，所以我恐怕无法提供高效的解决方案。祝你好运！ - amit
对于给定的n和k（这是问题所在），子集的数量是多项式级别的，大约为O（n^k）。 - Adar Hefer
2@AdarHefer 不，它是关于输入k的指数函数，而不是常数。因此n^k绝对不是多项式。 - amit
1@Nimrod 这个答案是针对“集合”（无序）的。基本上，您需要跟踪您已经使用过的元素（以不允许多次使用） - 在“猜测”步骤中，您有更多的选项而不仅仅是“使用”和“不使用”，您需要迭代所有未使用的值。 - amit
1@Nimrod 尽管我不记得4年前我当时在想什么，但今天我可能仍然会使用set，因为它更易读。尽管算法会处理不重复的情况，但是使用类型
Set使其更易读和理解。 - amit显示剩余6条评论
3
使用位向量表示集合，并使用类似于 std::next_permutation 在 0000.1111 (n-k 个零，k 个一) 上的算法。每个排列对应于一个大小为 k 的子集。
- Simple
3
8这个回答极其无助，没有足够的信息让人们实际运用你所描绘的算法。 - Nick Bailey
1他的回答非常好，但你是对的@NickBailey - 没有足够的细节。我在另一个线程中实现了这个（但我直到现在才看到这个线程）https://dev59.com/9nVC5IYBdhLWcg3w-mVO#42190945 - jacoblambert
我相信这个答案是迄今为止更好的答案。int n = 3;
std::string s = "ABCDEFGH";
std::vector<int> mask = {0,0,0,0,0,1,1,1};
std::setstd::string sets;
do {
sets.insert(calculate_set(mask, s));
} while(std::next_permutation(mask.begin(),mask.end()));其中calculate_set函数行为如下：ABCDEFGH
01010010-> 返回 BDG - Alessandro Teruzzi
2
这是Python。抱歉用了西班牙语的注释；）
from pprint import pprint
conjunto = [1,2,3,4, 5,6,7,8,9,10]
k = 3
lista = []
iteraciones = [0]
def subconjuntos(l, k):
if k == len(l):
if not l in lista:
lista.append(l)
return
for i in l:
aux = l[:]
aux.remove(i)
result = subconjuntos(aux, k)
iteraciones[0] += 1
if not result in lista and result:
lista.append( result)
subconjuntos(conjunto, k)
print (lista)
print ('cant iteraciones: ' + str(iteraciones[0]))
- josemontesp
1
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v;
vector<vector<int> > result;
void subset(int arr[],int k,int n,int idx){
if(idx==n)
return;
if(k==1){
for(int i=idx;i<n;i++)
{
v.push_back(arr[i]);
result.push_back(v);
v.pop_back();
}
}
for(int j=idx;j<n;j++) {
v.push_back(arr[j]);
subset(arr,k-1,n,j+1);
v.pop_back();
}
}
int main(){
int arr[] = {1,2,3,4,5,6,7};
int k = 4;
int n =sizeof(arr)/sizeof(arr[0]);
subset(arr,k,n,0);
for(int i = 0;i<result.size();i++)
{
for(int j = 0;j<result[i].size();j++)
{
cout << result[i][j] << " ";
}
cout << endl;
}
}
- Vishal Yadav
1
以下是一个简单的算法，按字典序枚举所有 [n]={0,...,n-1} 中的 k-子集。也就是说，这些子集中的第一个是 S0=(0,1,2...,k-1)，最后一个是 Slast=(n-k,n-k+1,...,n-1)。对于任何 k-子集 S 和任何 0例如，如果 n=10 并且 k=4，则 S0=(0,1,2,3)，Slast=(6,7,8,9)。请注意，例如，没有组合可以具有 S[1]>7（在这种情况下，我们将具有 S[j]> n+j-k），因为然后将没有足够的值剩余来填补 j=2..3 的其他位置。
该算法的思想是从第一个组合S0开始，然后重复调用next()函数以生成下一个k子集。函数next()从当前k子集向后遍历，从最后一个位置j=k-1到0，直到找到一个条目S[j]，它尚未达到其允许的最大值n+j-k，因此可以增加。然后它将此位置增加一，并使用连续的值从S[j]+1填充剩余的位置j+1..k-1。当没有位置可以进一步增加时，算法停止。
例如，假设我们有S=(3,7,8,9)。从j=3开始，我们看到S[3]、S[2]、S[1]已经达到了它们的最大值。因此，仍然可以增加的最右边的位置是S[0]。这个值更新为S[0]+1=4，接下来的位置更新为5、6、7。因此，下一个k子集将是S=(4,5,6,7)。
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
bool next(int *S, int k, int n) {
int j = k-1;
while (j >= 0 && S[j] == n + j - k)
j--;
if (j < 0) return false;
S[j] += 1;
for (int i = j+1; i < k ; i++)
S[i] = S[i-1] + 1;
return true;
}
int main(int argc, char *argv[])
{
int n = 10;
int k = 4;
int *S = (int *)calloc(k, sizeof(int));
for (int j = 0; j < k; S[++j] = j); //first k-subset
int no = 0;
do {
printf("subset #%d: ",no++);
for (int j=0; j < k; j++) {
printf("%d ", S[j]);
}
printf("\n");
} while(next(S, k, n));
return 0;
}
- Paulo
1
另一个有趣的解决方案。
#include<bits/stdc++.h>
using namespace std;
long factorial(int n) { return (n==1|| n==0|| n < 0) ? 1 : n *factorial(n-1) ;}
void printS(int set[],int n,int k)
{
long noofsubset = factorial(n) / (factorial(n-k)*factorial(k));
bitset<32> z ((1 << (k)) - 1);
string s = z.to_string();
int i = 0;
while(i<noofsubset)
{
for (int j = 0; j < n;j++)
{
if(s[(32-n)+j] == '1')
cout << set[j]<<" ";
}
cout << endl;
next_permutation(s.begin(),s.end());
i++;
}
}
void printSubsetsOfArray(int input[], int size) {
int k = 3;
printS(input,size,k) ;
}
- Sanjib Giri
1
检查我的解决方案。
我正在为测试目的工作，使用k=2的4元素集。我的目标是最初生成一个二进制字符串，其中k位被设置，n-k位未被设置。现在，使用这个字符串，我找到了这个字符串的所有可能排列。然后，使用这些排列，我输出了集合中相应的元素。如果有人能告诉我这个问题的复杂度就好了。
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
public class Subset_K {
public static void main(String[]args)
{
Set<String> x;
int n=4;
int k=2;
int arr[]={1,2,3,4};
StringBuilder sb=new StringBuilder();
for(int i=1;i<=(n-k);i++)
sb.append("0");
for(int i=1;i<=k;i++)
sb.append("1");
String bin=sb.toString();
x=generatePerm(bin);
Set<ArrayList <Integer>> outer=new HashSet<ArrayList <Integer>>();
for(String s:x){
int dec=Integer.parseInt(s,2);
ArrayList<Integer> inner=new ArrayList<Integer>();
for(int j=0;j<n;j++){
if((dec&(1<<j))>0)
inner.add(arr[j]);
}
outer.add(inner);
}
for(ArrayList<?> z:outer){
System.out.println(z);
}
}
public static Set<String> generatePerm(String input)
{
Set<String> set = new HashSet<String>();
if (input == "")
return set;
Character a = input.charAt(0);
if (input.length() > 1)
{
input = input.substring(1);
Set<String> permSet = generatePerm(input);
for (String x : permSet)
{
for (int i = 0; i <= x.length(); i++)
{
set.add(x.substring(0, i) + a + x.substring(i));
}
}
}
else
{
set.add(a + "");
}
return set;
}
}
我正在为测试目的工作，使用k=2的4元素集。我的目标是最初生成一个二进制字符串，其中k位被设置，n-k位未被设置。现在，使用这个字符串，我找到了这个字符串的所有可能排列。然后，使用这些排列，我输出了集合中相应的元素。如果有人能告诉我这个问题的复杂度就好了。
- Abhiroop Sarkar
1
对 @amit 最受欢迎的答案稍作改进:
即使不可能达到所需的长度，他的代码仍会继续检查组合。我们可以更早地停止创建组合：
例如，对于 [1,2,3,4,5,6,7,8,9,10]，长度为 8，尽管很明显它们只会被丢弃，但代码仍将尝试所有长度为 7、6、5、4、3、2、1 的组合，仅在 idx 到达列表结尾时才停止。
当我们已经知道构建的集合+可选剩余数字仍然太短时，我们可以通过提前停止来提高运行时间。
更改:
//unsuccessful stop clause
if (idx == superSet.size()) return;
转化为：
// unsuccessful stop clause
Integer maxFutureElements = superSet.size() - idx;
if (current.size() + maxFutureElements < length) return;
- dudibl
0
这是一个 F# 的实现：
// allSubsets: int -> int -> Set<Set<int>>
let rec allSubsets n k =
match n, k with
| _, 0 -> Set.empty.Add(Set.empty)
| 0, _ -> Set.empty
| n, k -> Set.union (Set.map (fun s -> Set.add n s) (allSubsets (n-1) (k-1)))
(allSubsets (n-1) k)
你可以在 F# REPL 中尝试它：
> allSubsets 3 2;;
val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [2; 3]]
> allSubsets 4 2;;
val it : Set<Set<int>> = set [set [1; 2]; set [1; 3]; set [1; 4]; set [2; 3]; set [2; 4]; set [3; 4]]
这个Java类实现了相同的算法：
import java.util.HashSet;
import java.util.Set;
public class AllSubsets {
public static Set<Set<Integer>> allSubsets(int setSize, int subsetSize) {
if (subsetSize == 0) {
HashSet<Set<Integer>> result = new HashSet<>();
result.add(new HashSet<>());
return result;
}
if (setSize == 0) {
return new HashSet<>();
}
Set<Set<Integer>> sets1 = allSubsets((setSize - 1), (subsetSize - 1));
for (Set<Integer> set : sets1) {
set.add(setSize);
}
Set<Set<Integer>> sets2 = allSubsets((setSize - 1), subsetSize);
sets1.addAll(sets2);
return sets1;
}
}
如果您不喜欢F#或Java，那么请访问这个网站。它列出了各种编程语言中解决您特定问题的解决方案：
- Olaf
0
JavaScript 实现：
var subsetArray = (function() {
return {
getResult: getResult
}
function getResult(array, n) {
function isBigEnough(value) {
return value.length === n;
}
var ps = [
[]
];
for (var i = 0; i < array.length; i++) {
for (var j = 0, len = ps.length; j < len; j++) {
ps.push(ps[j].concat(array[i]));
}
}
return ps.filter(isBigEnough);
}
})();
var arr = [1, 2, 3, 4,5,6,7,8,9];
console.log(subsetArray.getResult(arr,2));
- Thillai Narayanan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接