22
给定n个元素的集合{1,2,3,4,5...n}，我们需要查找长度为k的所有子集。查找数组中长度为k的所有子集
例如，如果n = 4且k = 2，则output将是{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}。
我甚至无法弄清楚如何开始。我们不必使用像next_permutation等内置库函数。
需要C/C++或Java中的算法和实现。
A
回答
38
递归是你完成这项任务的朋友。
对于每个元素 - “猜测”是否在当前子集中，并递归调用猜测和一个较小的超集，您可以从中选择。对“是”和“否”猜测都这样做 - 将导致所有可能的子集。
限制自己到一定的长度可以很容易地在停止条款中完成。
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]]
3
使用集的位向量表示，并使用类似的算法是什么std :: next_permutation在0000.1111上进行（nk为零，k为1）。每个置换对应于大小k的子集。
+0
请解释更多... – tomasyany
+3
这是一个非常无益的答案。它没有足够的信息可以让任何人实际实现草图的算法。 –
+0
他的回答非常好，但你是对的@NickBailey - 没有足够的细节。我在另一个线程中实现了这个（但是我直到现在才看到这个线程）http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n/42190945 ＃42190945 – jacoblambert
1
查看我的溶液
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;
}
}
我正在测试的目的设置一个4元件上，并使用K = 2。我试图做的是最初生成一个二进制串，其中设置了k位并且未设置n-k位。现在使用这个字符串，我找到了这个字符串的所有可能的排列。然后使用这些排列，我输出集合中的各个元素。如果有人能够告诉我这个问题的复杂性，那将会很棒。
0
请检查我的解决方案： -
private static void printPermutations(List<Integer> list, int subSetSize) {
List<Integer> prefixList = new ArrayList<Integer>();
printPermutations(prefixList, list, subSetSize);
}
private static void printPermutations(List<Integer> prefixList, List<Integer> list, int subSetSize) {
if (prefixList.size() == subSetSize) {
System.out.println(prefixList);
} else {
for (int i = 0; i < list.size(); i++) {
Integer removed = list.remove(i);
prefixList.add(removed);
printPermutations(prefixList, list, subSetSize);
prefixList.remove(removed);
list.add(i, removed);
}
}
}
这类似于字符串排列： -
private static void printPermutations(String str) {
printAllPermutations("", str);
}
private static void printAllPermutations(String prefix, String restOfTheString) {
int len = restOfTheString.length();
System.out.println(prefix);
for (int i = 0; i < len; i++) {
printAllPermutations(prefix + restOfTheString.charAt(i), restOfTheString.substring(0, i) + restOfTheString.substring(i + 1, len));
}
}
+0
如果你添加了一些关于你所做的事情的解释，以及为什么 –
+0
@UriAgassi现在可以按照解决方案来做？ –
+0
口头解释比更多代码更好......您花时间回答了一个老问题 - 让我们了解您的答案比其他问题更好。 –
0
这是F＃的implemation：
// 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然后访问这个网站。它列出了解决您的特定问题，在不同的编程语言：
1
这是蟒蛇。对不起，西班牙）
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]))
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));
0
这里是在Python迭代版本。它的实质是increment_counters（）函数，它返回所有可能的组合。我们知道它需要被称为C（n，r）次。
def nchooser(n,r):
"""Calculate the n choose r manual way"""
import math
f = math.factorial
return f(n)/f(n-r)/f(r)
def increment_counters(rc,r,n):
"""This is the essense of the algorithm. It generates all possible indexes.
Ex: for n = 4, r = 2, rc will have values (0,1),(0,2),(0,3),(1,2),(1,3),(2,3).
You may have better understanding if you print all possible 35 values for
n = 7, r = 3."""
rc[r-1] += 1 # first increment the least significant counter
if rc[r-1] < n: # if it does not overflow, return
return
# overflow at the last counter may cause some of previous counters to overflow
# find where it stops (ex: in n=7,r=3 case, 1,2,3 will follow 0,5,6)
for i in range(r-2,-1,-1): # from r-2 to 0 inclusive
if rc[i] < i+n-r:
break
# we found that rc[i] will not overflow. So, increment it and reset the
# counters right to it.
rc[i] += 1
for j in range(i+1,r):
rc[j] = rc[j-1] + 1
def combinations(lst, r):
"""Return all different sub-lists of size r"""
n = len(lst)
rc = [ i for i in range(r) ] # initialize counters
res = []
for i in range(nchooser(n,r)): # increment the counters max possible times
res.append(tuple(map(lambda k: lst[k],rc)))
increment_counters(rc,r,n)
return res
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;
}
}
0
这里是什么，我想简单的讲，使用的发电机组所有集合的二进制表示的Java版本。这与Abhiroop Sarkar如何做相似，但我认为布尔数组比字符串更有意义，因为只是表示二进制值。
private ArrayList<ArrayList<Object>> getSubsets(int m, Object[] objects){
// m = size of subset, objects = superset of objects
ArrayList<ArrayList<Object>> subsets = new ArrayList<>();
ArrayList<Integer> pot = new ArrayList<>();
int n = objects.length;
int p = 1;
if(m==0)
return subsets;
for(int i=0; i<=n; i++){
pot.add(p);
p*=2;
}
for(int i=1; i<p; i++){
boolean[] binArray = new boolean[n];
Arrays.fill(binArray, false);
int y = i;
int sum = 0;
for(int j = n-1; j>=0; j--){
int currentPot = pot.get(j);
if(y >= currentPot){
binArray[j] = true;
y -= currentPot;
sum++;
}
if(y<=0)
break;
}
if(sum==m){
ArrayList<Object> subsubset = new ArrayList<>();
for(int j=0; j < n; j++){
if(binArray[j]){
subsubset.add(objects[j]);
}
}
subsets.add(subsubset);
}
}
return subsets;
}
+0
谢谢，但这里有一些错误。对于m == 0或m == n，应返回包含原始列表的单个条目。您可以在开始时将其添加为检查。如果m == n，您的版本实际上会返回原始列表的2^n个副本。另外一个检查m> n是一个好主意。修正版本在这里：http://tinybrain.de/1010466 –
0
如果您正在寻找Iterator模式答案，那么在这里你去。
public static <T> Iterable<List<T>> getList(final Iterable<? extends T> list) {
List<List<T>> listOfList = new ArrayList<>();
for (T t: list)
listOfList.add(Collections.singletonList(t));
return listOfList;
}
public static <T> Iterable<List<T>> getIterable(final Iterable<? extends T> list, final int size) {
final List<T> vals = new ArrayList<>();
int numElements = 0;
for (T t : list) {
vals.add(t);
numElements++;
}
if (size == 1) {
return getList(vals);
}
if (size == numElements) {
return Collections.singletonList(vals);
}
return new Iterable<List<T>>() {
@Override
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int currPos = 0;
Iterator<List<T>> nextIterator = getIterable(
vals.subList(this.currPos + 1, vals.size()), size - 1).iterator();
@Override
public boolean hasNext() {
if ((this.currPos < vals.size()-2) && (this.currPos+size < vals.size()))
return true;
return false;
}
@Override
public List<T> next() {
if (!nextIterator.hasNext()) {
this.currPos++;
nextIterator = getIterable(vals.subList(this.currPos+1, vals.size()), size-1).iterator();
}
final List<T> ret = new ArrayList<>(nextIterator.next());
ret.add(0, vals.get(this.currPos));
return ret;
}
};
}
};
}
相关问题
- 1. 查找长度为k的所有递减序列的列表？
- 2. 从长度为k的数组获得n上的所有组
- 3. 序言：长度为k的子集
- 4. 查找所有周期的长度的有向图<= K
- 5. 发现列表的所有K-长度子集在序言
- 6. 查找以K为因子的最小长度间隔
- 7. 长度为k
- 8. 长度为k
- 9. 查找最大总数连续子数组，使得子数组的长度小于等于k？
- 10. 查找数组中的所有子集，递归不工作，JavaScript
- 11. 在图中查找长度为k的派系
- 12. 如何在Perl中生成长度为k的所有有序组合？
- 13. 回溯并找到等于某个值的数组的所有子集k
- 14. 在mongodb中查找数组的长度
- 15. 查找字符串中所有子字符串的长度
- 16. 子集可能有长度为1的R数组
- 17. 查找集合的所有子集
- 18. 为所有k句子执行K组合的算法
- 19. 查找DNA字符串集合中的所有（k，d） - 基元
- 20. 使用Ruby查找数组中大小为N的所有子集
- 21. Scala函数获取大小为k的所有排序子集
- 22. 在postgres中查找数组长度
- 23. 长度有序的子集？
- 24. 查找序列中长度为n的所有连续子序列
- 25. 查找最-K记录数据集中
- 26. 获取数组中特定长度的所有子阵列
- 27. 在Python中生成大小为k（包含k个元素）的所有子集
- 28. c，查找指针数组的长度
- 29. 如何查找char数组的长度？
- 30. 如何查找数组类的长度？
请参阅同样的问题另一个线程和一个替代方法将溶液：http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-从-n/42190945＃42190945（可以从C＃转换为Java） – jacoblambert