发现长度为k的所有子集以阵列(Find all subsets of length k in an

给定一组{1,2,3,4,5...n} n个元素，我们需要找到一个长度为k的所有子集。

例如，如果n = 4且k = 2时， output将是{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} 。

我甚至无法弄清楚如何下手。 我们没有使用内置的库函数像next_permutation等。

需要用C / C ++或Java的算法和实现。

Answer 1:

递归是你的朋友对这个任务。

对于每一个元素 - “猜测”，如果它是在目前的子集，并与猜测，更小的超可供选择的递归调用。 这样做既为“是”和“否”的猜测 - 将导致所有可能的子集。
限制自己一定长度可在停止子句中轻松完成。

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]]

Answer 2:

使用集的位向量表示，并使用类似于的std :: next_permutation确实在0000.1111算法（NK零，K的）。 每个排列对应于大小为k的子集。

Answer 3:

看看我的解决办法

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位设置和nk位未设置。 现在用这个字符串我觉得这个字符串的所有可能的排列。 然后使用这些排列I输出该组中的相应的元件。 将是巨大的，如果有人能告诉我有关这个问题的复杂性。

Answer 4:

这是蟒蛇。 遗憾的西班牙语）

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]))

Answer 5:

   #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;
 }
}

Answer 6:

请检查我的解决方案： -

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));
    }
}

Answer 7:

这是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然后访问这个网站。 它列出了解决方案，以各种编程语言的特定问题：

http://rosettacode.org/wiki/Combinations

Answer 8:

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));

Answer 9:

这里是一个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

Answer 10:

这里是什么，我想简单的讲，使用的发电机组所有集合的二进制表示的Java版本。 它类似于Abhiroop萨卡是如何做到的，但我认为一个布尔阵列更有意义比当你只是表示二进制值的字符串。

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;
}

Answer 11:

如果您正在寻找迭代器模式的答案，然后在这里你去。

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;
                }
            };
        }
    };
}

文章来源: Find all subsets of length k in an array