给定一个包含 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个回答
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
- Naci Ishakbeyoglu
0
这是一个简短的Python算法。我没有使用任何预定义的函数，因此我相信它可以很容易地转换成Java/C。
def subs(l,n):
if(len(l)<k):
return []
elif(k==0):
return [[]]
else:
lis=[[l[0]]+b for b in (subs(l[1:],k-1))]
return (lis+subs(l[1:],k))
这里 l 是列表 [1,2,...,m]
- Darth jedi
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));
}
}
- Balaji Gandhi
3
如果您能添加一些关于您所做的事情以及为什么这样做的解释，那就太好了。 - Uri Agassi
@UriAgassi，你现在能够理解这个解决方案了吗？ - Balaji Gandhi
口头解释比更多的代码好得多...您花时间回答了一个老问题 - 让我们了解一下您的答案如何比其他答案更好。 - Uri Agassi
0
这是我认为Simple在谈论的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;
}
- jimboweb
1
我尝试使用这个，但是对于更大的数组它返回错误的结果并变得极其缓慢。我在这里提供了一个替代方案，它是正确的、快速的，并且提供了一个迭代器而不是列表（节省内存）：http://code.botcompany.de/1027914（点击“Pure Java version”）。 - Stefan Reich
0
如果您正在寻找迭代器模式的答案，那么这里就有了。
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;
}
};
}
};
}
- peeyush
0
#include <bits/stdc++.h>
using namespace std;
void findAllSubsetOfSizeK(int ind, vector<int> &arr, vector<int> temp, int k, set<vector<int>> &st)
{
if (temp.size() == k)
{
st.insert(temp);
return;
}
for (int i = ind; i < arr.size(); i++)
{
temp.push_back(arr[i]);
findAllSubsetOfSizeK(i + 1, arr, temp, k, st);
temp.pop_back();
}
}
vector<vector<int>> solve(int n, int k)
{
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
arr[i] = i + 1;
}
set<vector<int>> st;
findAllSubsetOfSizeK(0, arr, {}, k, st);
vector<vector<int>> res;
for (auto i : st)
{
res.push_back(i);
}
return res;
}
int main()
{
int n, k;
cin >> n >> k;
vector<vector<int>> res = solve(n, k);
for (auto i : res)
{
for (auto j : i)
{
cout << j << " ";
}
cout << "\n";
}
return 0;
}
- Lalit Kishor
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接